Stack 堆疊 & Queue 佇列
Stack 堆疊 & Queue 佇列
定義
- 相較於 array 和 linked-list，stack 和 queue 只支援 pop 或 shift 這類的方法（只能從頭或尾取資料），而不能直接取出中間的項目，目的是要限制開發者的操作，以避免對該資料結構做了不適當的操作。
- 只要符合定義的都可以稱作是 Stack 或 Queue
Stack 堆疊
- 後進先出 (LIFO, Last in First out)
- 在 JavaScript 中使用 Array 的 push 和 pop 即可實作 Stack
使用情境
- 洗盤子，先被疊上的盤子會最後被洗到，最後被疊上的盤子則會先被洗到。
- 編輯照片或寫程式時「上一步」的功能
- 瀏覽器上一頁的功能。
時間複雜度 Time Complexity
| 操作 | Time Complexity 時間複雜度 |
|---|---|
| Lookup | O(n) |
| Pop | O(1) |
| Push | O(1) |
| Peek | O(1)，顯示下一個會出來的元素，但不會實際把它取出 |
使用 Array 或 Linked List 來實作 Stack 的優缺點
| 功能 | Array | Linked List |
|---|---|---|
| 上一步 | 效能很好 | 除非是 Doubly Linked List，否則 Singly Linked List 在資料結構中並沒有保存 previous 的 item，這會使得「上一步」是沒有效率的 |
| Push / Pop | 可以非常容易的操作 Push 和 Pop 而不會動到整個 Array 的 index | 操作較複雜 |
| 資料存取效率 | 效能較好，配置在一連串的記憶體空間中（cache locality） | 效能較差，散落在不同的記憶體位置 |
| 記憶體使用 | 有固定 size 的，如果超過了該 size，他會需要 copy 整份到新的位置，這是有可能使得效能下降的原因 | 資料散落在各個不同記憶體互相連結，沒有大小問題 |
Queue 佇列
- 先進先出 (FIFO, First in first out)
- 在 JavaScript 中，使用 Array 的 push 和 shift 即可實作 queue
使用情境
- 類似平常在排隊，第一個排隊的人可以第一個進場
- 購票平台、Uber、印表機列印任務、KTV 點歌
時間複雜度 Time Complexity
| 操作 | Time Complexity 時間複雜度 |
|---|---|
| Lookup | O(n) |
| Enqueue | O(1) |
| Dequeue | O(1) |
| Peek | O(1)，檢視下一個會出來的元素，但不會實際將它移除 |
為什麼用 Linked List 而不要用 Array 來實作 Queue
- Array 的所有元素都有 index，當我們在進行 Queue 常用的 Dequeue（shift）時，所有陣列元素的 index 都需要一起被改變，因此會非常沒有效率。
- Linked List 可以從 head 開始，透過 next 直接往後找下一個是誰。
JavaScript 效能
在 JavaScript 中 shift 和 unshift 的效能較差；push 和 pop 的效能較好。
