Image by macrovector on Freepik

定義

• 相較於 array 和 linked-list，stack 和 queue 只支援 pop 或 shift 這類的方法（只能從頭或尾取資料），而不能直接取出中間的項目，目的是要限制開發者的操作，以避免對該資料結構做了不適當的操作。
• 只要符合定義的都可以稱作是 Stack 或 Queue

Stack 堆疊

• 後進先出 (LIFO, Last in First out)
• 在 JavaScript 中使用 Array 的 push 和 pop 即可實作 Stack

使用情境

• 洗盤子，先被疊上的盤子會最後被洗到，最後被疊上的盤子則會先被洗到。
• 編輯照片或寫程式時「上一步」的功能
• 瀏覽器上一頁的功能。

時間複雜度 Time Complexity

使用 Array 或 Linked List 來實作 Stack 的優缺點

Queue 佇列

• 先進先出 (FIFO, First in first out)
• 在 JavaScript 中，使用 Array 的 push 和 shift 即可實作 queue

使用情境

• 類似平常在排隊，第一個排隊的人可以第一個進場
• 購票平台、Uber、印表機列印任務、KTV 點歌

時間複雜度 Time Complexity

為什麼用 Linked List 而不要用 Array 來實作 Queue

• Array 的所有元素都有 index，當我們在進行 Queue 常用的 Dequeue（shift）時，所有陣列元素的 index 都需要一起被改變，因此會非常沒有效率。
• Linked List 可以從 head 開始，透過 next 直接往後找下一個是誰。

JavaScript 效能

在 JavaScript 中 shift 和 unshift 的效能較差；push 和 pop 的效能較好。

參考資料

• [資料結構] Stacks and Queues | PJCHENder 未整理筆記
• Stack 堆疊 / Queue 佇列 / Heap 堆 | Node.js 菜雞修煉場
• Array > Performance @ JavaScript.info

Donate KJ 贊助作者喝咖啡

如果這篇文章對你有幫助的話，可以透過下面支付方式贊助作者喝咖啡，如果有什麼建議或想說的話可以贊助並留言給我

If this article has been helpful to you, you can support the author by treating them to a coffee through the payment options below. If you have any suggestions or comments, feel free to sponsor and leave a message for me!