[資料結構] Stacks and Queues
- 相較於 array 和 linked-list，stack 和 queue 只支援 pop 或 shift 這類的方法（只能從頭或尾取資料），而不能直接取出中間的項目，目的是要限制開發者的操作，以避免對該資料結構做了不適當的操作。
- 只要符合定義的都可以稱作是 Stack 或 Queue
Stacks
定義
- 先進後出（FILO），很像在洗盤子，先被疊上的盤子會最後被洗到，最後被疊上的盤子則會先被洗到。
- 使用情境像是在編輯照片或寫程式時「上一步」的功能，或者瀏覽器上一頁的功能。
提供的方法與 Time Complexity
- Lookup: O(n)
- Pop: O(1)
- Push: O(1)
- Peek: O(1)，顯示下一個會出來的元素，但不會實際把它取出
使用 Array 或 Linked List 來實作 Stack 的優缺點
- 除非是 Doubly Linked List，否則 Singly Linked List 在資料結構中並沒有保存 previous 的 item，這會使得「上一步」是沒有效率的
- 相較之下，Array 可以非常容易的操作 Push 和 Pop 而不會動到整個 Array 的 index。
- 另外，Array 會配置在一連串的記憶體空間中（cache locality），但 Linked List 是散落在不同的記憶體位置，因此 Array 通常效率會比較好。
- 但 Array 有一個需要考量的是它是有固定 size 的，如果超過了該 size，他會需要 copy 整份到新的位置，這是有可能使得效能下降的原因，但 Linked List 則不會有這個問題。
實作
- 在 JavaScript 中使用 Array 的
push和pop即可實作 Stack
Queues
定義
- 先進先出（FIFO），類似平常在排隊，第一個排隊的人可以第一個進場
- 使用情境像是購票平台、Uber、印表機列印任務、KTV 點歌
提供的方法與 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 中，使用 Array 的
push和shift即可實作 queue
JavaScript 中 Array 的效能
Array > Performance @ JavaScript.info
在 JavaScript 中 shift 和 unshift 的效能較差；push 和 pop 的效能較好。
圖片來源：https://javascript.info/array/article/array/array-speed.svg
