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!