Docker
Network
RxJS
Nginx
TypeScript
Data Structure And Algorithm
JavaScript
PostgreSQL
React
Git資料結構筆記-堆疊(Stack)&佇列(Queue)
堆疊 (Stack)
堆疊屬於 LIFO (Last In, First Out) 的線性資料結構: 也就是最後新增 (add) 的 Stack 的資料，在移除 (remove) 時也會是第一個被移出的。常見的 Stack 例子如
-
JavaScript 中的函式在執行環境 (Execution Stack) 中堆疊的過程。
-
網頁的瀏覽紀錄 (上一頁&下一頁)。
堆疊可以簡單的透過 JavaSciprt 的 Array 來執行，將資料加在陣列最尾端可透過 Array.push() 實現、將最後加入的資料移除則可以透過 Array.pop() 來實現，且時間複雜度都是 O (1);
若要讓資料從前端開始堆疊， Array.shift() 以及 Array.unshift() 也可以達到一樣的效果，但是會改變陣列內資料的次序 (index)，因此時間複雜度會變為 O (n) ，若想讓時間複雜度降至 O (1) ，我們可以透過 JavaScript 中的 Class 實現，由於是線性結構，方法與 Singly Linked List 中的 shift 以及 unshift 相同，如下方程式碼。
佇列 (Queue)
佇列 (Queu) 與堆疊 (Stack) 的特性相反，屬於 FIFO (First In, First Out) 的線性結構，最先加入的資料也會在移除階段優先被移出，類似排隊的概念，在許多系統中的背景程式會用到佇列的概念來處理，又或是商城訂單系統，先下訂的買家可以優先被商家處理訂單。
佇列同樣的可以透過JavaScript的Array來實現，加入資料時透過 Array.push() 或 Array.unshift() 實現，移除資料透過 Array.shift()或 Array.pop() 實現。
然而，透過 1.前端加入後端移除 (unshift, pop) 或是 2. 後端加入前端移除 (push, shift) ，兩者的其中一種方法都會使時間複雜度變為 O (n) ，為了將時間複雜度降至 O (1) ，同樣可以透過 Class 來達到。方法與 Singly Linked List 中的 push 以及 pop 相同，如下方程式碼。
堆疊 (Stack) & 佇列 (Queue) 的時間複雜度
| Data Structure | Insertion | Removal | Searching | Access |
|---|---|---|---|---|
| Stack | O(1) | O(1) | O(n) | O(n) |
| Queue | O(1) | O(1) | O(n) | O(n) |