Stack 和 Queue

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

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

Stack：後進先出（LIFO, Last-In-First-Out）
Queue：先進先出（FIFO, First-In-First-Out）

白話理解

Stack 就像洗碗時疊起來的盤子，最後放上去的盤子一定要最先被拿起來，才拿得到下面的盤子。
Queue 則像排隊買飲料，先來的人先領到、先離開，後來的人只能排在隊伍最後面等。

兩者都只開放「一端」或「兩端固定的方式」進出，這也是它們比 Array 多了限制、卻換來更清楚語意的原因。

複雜度

操作種類	Stack	Queue	說明
新增資料	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)。

Python
JavaScript
Java

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

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

import java.util.ArrayDeque;
import java.util.Deque;

Deque<String> stack = new ArrayDeque<>();
stack.push("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；在 JavaScript 則比較麻煩，沒有原生的 deque，需要用 Linked List 手刻實作。

Python
JavaScript
Java

使用內建 deque
from collections import deque

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

items.append(4)     # [1, 2, 3, 4]
items.popleft()      # Output: 1，剩下 [2, 3, 4]

用 Linked List 手刻 Queue
// 定義 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 資料值
  }
}

使用內建 Deque（ArrayDeque）
import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> items = new ArrayDeque<>(java.util.List.of(1, 2, 3));

items.addLast(4);     // [1, 2, 3, 4]
items.pollFirst();    // Output: 1，剩下 [2, 3, 4]

常見誤區

用原生 Array 的 shift() 實作 Queue：雖然 shift() 語意上很直覺，但每次都要把剩下所有元素往前搬一格，時間複雜度是 O(n)。如果資料量大、又頻繁 dequeue，效能會明顯變差，這也是為什麼 Queue 常改用 Linked List 或 deque 實作的原因。
搞混 Stack 和 Queue 的取出順序：可以用「洗碗疊盤子（Stack，後放的先拿）」和「排隊買東西（Queue，先排的先拿到）」這兩個畫面來記憶，避免解題時邏輯顛倒。
忘記檢查空的 Stack / Queue 就直接操作：對空的 Stack 呼叫 pop()，或對空的 Queue 呼叫 dequeue()，如果沒有先做長度檢查，容易回傳 undefined 卻沒被妥善處理，進而在後續程式碼引發錯誤。

複雜度​

Stack​

適用情況​

實作​

Queue​

適用情況​

實作​

常見誤區​

複雜度

Stack

適用情況

實作

Queue

適用情況

實作

常見誤區