Skip to main content

[資料結構] Stacks and Queues

  • 相較於 array 和 linked-list,stack 和 queue 只支援 pop 或 shift 這類的方法(只能從頭或尾取資料),而不能直接取出中間的項目,目的是要限制開發者的操作,以避免對該資料結構做了不適當的操作。

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 有一個需要考量的是它是有固定 size 的,如果超過了該 size,他會需要 copy 整份到新的位置,這是有可能使得效能下降的原因,但 Linked List 則不會有這個問題。

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 直接往後找下一個是誰。

參考#

Last updated on