跳至主要内容

Stack 和 Queue

堆疊（Stack）與佇列（Queue）是兩種非常經典且特殊的線性資料結構，像 Array 那樣隨意讀取任意位置的資料，而是嚴格限制了資料進出的通道與順序。

兩者的資料進出邏輯相反，也都可以當成是 Array 的延伸結構，時常被一起介紹。

  • Stack
    • 後進先出（LIFO, Last-In-First-Out）
    • 如洗碗時疊盤子，最後放上去的盤子必須最先拿起來。
  • Queue
    • 先進先出（FIFO, First-In-First-Out）
    • 就像排隊消費，先排隊的人先拿到東西離開。

複雜度​

操作種類StackQueue說明
新增資料O(1)O(1)Stack 稱為 push（推入頂端）；Queue 稱為 enqueue（排入尾端）。
刪除資料O(1)O(1)Stack 稱為 pop（彈出頂端）；Queue 稱為 dequeue（移出開頭）。
查看頂端/前端O(1)O(1)稱為 peek，只看最上面的或排最前面的人是誰，不移出。
尋找資料 (Search)O(n)O(n)因為不能隨機存取，必須從頭到尾搜尋。
空間複雜度O(n)O(n)記憶體空間與存放的資料量 n 成正比。

Stack​

Stack - 圖源：programiz

適用情況​

有「需要回復到上一步」、「追蹤最近一次的操作」或「括號/標籤必須成對對齊」之類的需求，就可以用 Stack 來處理。

  • 瀏覽器的「上一頁」功能：每當你點擊新分頁，網址就被 Push 進 Stack；點擊回上一頁，就 Pop 出最近一次的網址。
  • 軟體的「復原」功能（Ctrl + Z）：文字編輯器或繪圖軟體（如 Photoshop）會把你每次的操作丟進 Stack，按復原時就倒退回最近的操作。
  • 程式語言的 Call Stack：程式在執行 function 時，func A 呼叫 func B，B 再呼叫 C，電腦會用 Stack 記錄現在執行到哪，C 執行完才退回 B。這也是「Stack Overflow」這個知名網站的由來。
  • 語法解析與括號匹配：編譯器檢查程式碼裡的括號是否有成對（例如：{[]}），或是 HTML 標籤（<div><p></p></div>）是否正確閉合。

實作​

你或許已經注意到了，JavaScript 的 Array 或是 Python 中的 List，其實可以直接當作 Stack 來使用，因為原生的資料結構就是只處理資料在結構最末端的進出，而且時間複雜度就是 O(1)。

// JavaScript
const stack = []
stack.push('data') // 加入一筆資料
stack.pop() // 拿出最後一筆資料
# Python
stack = []
stack.append('data') # 加入一筆資料
stack.pop() # 拿出最後一筆資料

Queue​

Queue - 圖源：programiz

適用情況​

符合「先來後到」、「先處理舊請求，再處理新請求」的資源分配需求，就該使用 Queue。

  • 排隊與預約系統：演唱會搶票、餐廳線上候位系統。
  • 印表機列印文件：大家同時傳送檔案給印表機，印表機一定是用 Queue 依照收到的先後順序排隊列印。
  • JavaScript 的 Event Loop：非同步任務（如 setTimeout、點擊事件、API 回傳）完成後，Callback 會被丟進「Task Queue」中排隊，等 Main Thread 有空時依序執行。
  • 伺服器請求處理（Buffer/Message Queue）：當網站瞬間湧入大量流量時，Server 會把 requests 先塞進 Queue（如 RabbitMQ, Kafka）排隊處理，避免伺服器直接過載當機。

實作​

原生的 Array 可以拿出第一筆資料，但是資料拿出來之後，後面的資料都要往前移動，所以時間複雜度會是 O(n)。

如果想要得到 O(1)，Python 可以引入 deque

from collections import deque

items = deque([1, 2, 3])

items.append(4) # [1, 2, 3, 4]
items.popoleft() # Output: 1 
# [2, 3, 4]

在 JavaScript 則比較麻煩，需要手刻實作

// 定義 linked list 的 node
class Node {
  constructor(val) {
    this.val = val;     // 儲存該節點的資料值
    this.next = null;   // 指向下一個節點的指標，預設為空（null）
  }
}

// 使用 linked list 實作的 queue
class Queue {
  constructor() {
    this.first = null;  // 指向隊頭的 node
    this.last = null;   // 指向隊尾的 node
    this.size = 0;      // 記錄目前元素總數
  }

  // 將資料排入隊尾：O(1)
  enqueue(val) {
    const newNode = new Node(val);
    
    if (this.size === 0) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode; // 1. 讓原本最後一個 node 的 next 指向 new node
      this.last = newNode;      // 2. 更新隊尾指標
    }
    
    this.size++;
  }

  // 將資料移出隊頭：O(1)
  dequeue() {
    if (this.size === 0) return null;
    
    // 暫存目前的隊頭節點，最後回傳它
    const targetNode = this.first;
    
    // 如果只有一筆資料（隊頭跟隊尾是同一個 node）
    if (this.first === this.last) {
      this.last = null; // 將隊尾清空（隊頭則會在下方那行被更新為 null）
    }
    
    // 將隊頭指標指向下一個 node，成功斷開並移除原本的隊頭
    this.first = targetNode.next;
    
    this.size--; // 長度減 1
    
    return targetNode.val; // 回傳被移除 node 資料值
  }
}
最後於 更新