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 的效能较好。
