Featured image of post 【資料結構 Data Structure】Array 陣列:Stack 堆疊 & Queue 佇列

【資料結構 Data Structure】Array 陣列:Stack 堆疊 & Queue 佇列

【資料結構 Data Structure】Array 陣列:Stack 堆疊 & Queue 佇列

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

Stack 堆疊 & Queue 佇列

使用情境

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

時間複雜度 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

Stack 堆疊 & 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 的效能較好。

Stack 堆疊 & Queue 佇列

參考資料

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!
方式 Method 贊助 Donate
PayPal https://paypal.me/kejyun
綠界 ECPay https://p.ecpay.com.tw/AC218F1
歐付寶 OPay https://payment.opay.tw/Broadcaster/Donate/BD2BD896029F2155041C8C8FAED3A6F8
All rights reserved,未經允許不得隨意轉載
Built with Hugo
Theme Stack designed by Jimmy