堆疊與佇列 — Stack、Queue、Deque 完整教學與實作 | 資料結構與演算法
2026/06/17
堆疊（Stack） 與 佇列（Queue） 是兩種最基礎的線性資料結構，也是面試中必考的核心概念。前者遵循 LIFO（後進先出）原則，後者遵循 FIFO（先進先出）原則。從瀏覽器的上一頁按鈕、函式呼叫堆疊，到作業系統的任務排程、Kafka 訊息佇列，這兩種結構無所不在。
前言
想像你正在洗碗：你把碗一個個疊起來，洗的時候也從最上面開始拿——這就是 Stack（堆疊），後放的先取，即 LIFO。
再想像你在便利商店排隊結帳：先到的人先結帳，後到的人排在後面等——這就是 Queue（佇列），先進的先出，即 FIFO。
這兩個看似簡單的比喻，卻支撐著程式世界中無數重要的機制：
- Stack 驅動函式呼叫、括號匹配、瀏覽器歷史、DFS 遍歷、撤銷（Undo）功能
- Queue 驅動 BFS 廣度優先搜尋、作業系統行程排程、訊息佇列（Kafka/RabbitMQ）、列印任務
本篇文章涵蓋的學習要點：
- Stack 與 Queue 的核心差異 — LIFO vs FIFO 原理與圖解
- Deque 雙端佇列 — 結合兩者特性的萬用工具
- JavaScript/TypeScript 完整實作 — 從基礎到進階（MinStack、環形佇列、單調棧）
- C++ STL 對照 —
std::stack、std::queue、std::deque - 單調棧與單調佇列 — 解鎖 O(n) 滑動視窗最大值、Next Greater Element
- 面試必考題型 — LeetCode 20、155、232、239、84 詳解
一、核心概念
LIFO vs FIFO 原理對比
| 特性 | Stack（堆疊） | Queue（佇列） |
|---|---|---|
| 原則 | LIFO — 後進先出 | FIFO — 先進先出 |
| 生活類比 | 疊盤子、書堆 | 排隊買票 |
| 插入端 | 頂端（top） | 尾端（rear/back） |
| 刪除端 | 頂端（top） | 前端（front） |
| 主要應用 | 函式呼叫堆疊、括號匹配、DFS | BFS、任務排程、訊息佇列 |
| JS 原生支援 | Array.push / Array.pop | 需自行實作（shift() 有效能問題） |
用 ASCII 圖示幫助理解兩者的操作方向：
Stack（LIFO）— 垂直堆疊，從頂端存取：
push(3) push(5) pop()
-------- -------- --------
| | | [5] | | | <-- 5 被移除
| [3] | | [3] | | [3] |
|______| |______| |______|
top=3 top=5 top=3
Queue（FIFO）— 水平管道，從前端取出：
enqueue(A) enqueue(B) dequeue()
front->[A]<-back front->[A][B]<-back front->[B]<-back
A 被移除
Deque（雙端佇列）
Deque（Double-ended Queue） 結合了 Stack 與 Queue 的特性，允許在兩端進行 O(1) 的插入與刪除操作。它是實作**單調棧（Monotonic Stack）與單調佇列（Monotonic Queue）**的核心基礎。
Deque（雙端操作）:
pushFront(X) --- [X][A][B][C] --- pushBack(Y) → [X][A][B][C][Y]
popFront() ← 從前端移除 popBack() → 從後端移除
Priority Queue（優先佇列）簡介
優先佇列（Priority Queue） 讓出隊順序由「優先級」決定，而非插入順序。底層通常以二元堆積（Binary Heap） 實作，支援 O(log n) 的插入與取最值操作。C++ 的 std::priority_queue、Java 的 PriorityQueue 均屬此類。本系列將在後續「堆積」章節深入介紹。
二、JavaScript / TypeScript 實作
Stack — 陣列實作
JavaScript 的 Array 天生支援 push 與 pop，Stack 的實作極為直觀：
class Stack<T> {
private data: T[] = [];
// 推入元素到頂端 — O(1) amortized
push(item: T): void {
this.data.push(item);
}
// 取出頂端元素 — O(1)
pop(): T | undefined {
return this.data.pop();
}
// 查看頂端元素但不移除 — O(1)
peek(): T | undefined {
return this.data[this.data.length - 1];
}
isEmpty(): boolean {
return this.data.length === 0;
}
size(): number {
return this.data.length;
}
}
// 使用範例
const stack = new Stack<number>();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 輸出：3（LIFO，最後進的最先出）
console.log(stack.peek()); // 輸出：2（只查看，不移除）
console.log(stack.size()); // 輸出：1
Queue — 效能陷阱與正確實作
JavaScript 沒有內建的 Queue。初學者常用 Array.shift() 模擬出隊，但這有嚴重的效能問題：
// 效能陷阱版本：shift() 每次需要將所有元素向前移動，時間複雜度 O(n)
class NaiveQueue<T> {
private data: T[] = [];
enqueue(item: T): void {
this.data.push(item); // O(1) amortized
}
dequeue(): T | undefined {
return this.data.shift(); // O(n)！不適合大量操作
}
}
正確做法是使用 head 指標 追蹤隊列頭部，避免元素移位：
// 正確版本：head 指標讓 dequeue 達到 O(1)
class Queue<T> {
private data: T[] = [];
private head = 0; // 指向第一個有效元素的索引
enqueue(item: T): void {
this.data.push(item); // O(1) amortized
}
dequeue(): T | undefined {
if (this.isEmpty()) return undefined;
const item = this.data[this.head];
this.head++;
// 定期清理已消費的空間，防止記憶體洩漏
if (this.head > 1000 && this.head > this.data.length / 2) {
this.data = this.data.slice(this.head);
this.head = 0;
}
return item;
}
peek(): T | undefined {
return this.data[this.head];
}
isEmpty(): boolean {
return this.head >= this.data.length;
}
size(): number {
return this.data.length - this.head;
}
}
// 使用範例
const queue = new Queue<string>();
queue.enqueue("Alice");
queue.enqueue("Bob");
queue.enqueue("Carol");
console.log(queue.dequeue()); // 輸出：Alice（FIFO，先進先出）
console.log(queue.peek()); // 輸出：Bob
console.log(queue.size()); // 輸出：2
Deque — 雙端佇列實作
// 注意：Array.unshift() 與 Array.shift() 均為 O(n)
// 以下為展示用途；生產環境建議以雙向鏈結串列實作兩端 O(1) 操作
class Deque<T> {
private data: T[] = [];
// 從前端插入 — Array 版本為 O(n)（展示用）
pushFront(item: T): void {
this.data.unshift(item);
}
// 從後端插入 — O(1) amortized
pushBack(item: T): void {
this.data.push(item);
}
// 從前端移除 — Array 版本為 O(n)（展示用）
popFront(): T | undefined {
return this.data.shift();
}
// 從後端移除 — O(1)
popBack(): T | undefined {
return this.data.pop();
}
peekFront(): T | undefined {
return this.data[0];
}
peekBack(): T | undefined {
return this.data[this.data.length - 1];
}
isEmpty(): boolean {
return this.data.length === 0;
}
size(): number {
return this.data.length;
}
}
最小堆疊（MinStack）
最小堆疊在一般堆疊的基礎上，能以 O(1) 時間回傳目前堆疊中的最小值。關鍵在於使用一個同步輔助棧，記錄每個時刻的最小值快照：
// LeetCode 155 — Min Stack
// 輔助棧的大小與主棧同步：每次 push 都同步記錄當下的最小值
class MinStack {
private data: number[] = [];
private minData: number[] = []; // 輔助棧：記錄對應時刻的最小值
push(val: number): void {
this.data.push(val);
// 輔助棧：將當前最小值快照壓入
const currentMin = this.minData.length === 0
? val
: Math.min(val, this.minData[this.minData.length - 1]);
this.minData.push(currentMin);
}
pop(): void {
this.data.pop();
this.minData.pop(); // 兩棧同步彈出
}
top(): number {
return this.data[this.data.length - 1];
}
// O(1) 取得當前最小值
getMin(): number {
return this.minData[this.minData.length - 1];
}
}
// 操作範例
const minStack = new MinStack();
minStack.push(5);
minStack.push(3);
minStack.push(7);
console.log(minStack.getMin()); // 輸出：3
minStack.pop(); // 移除 7
console.log(minStack.getMin()); // 輸出：3
minStack.pop(); // 移除 3
console.log(minStack.getMin()); // 輸出：5（正確！因為輔助棧記錄了快照）
單調棧（Monotonic Stack）
單調棧 是一種保持棧內元素單調遞增或遞減的特殊堆疊，能在 O(n) 時間內解決「每個元素的下一個更大/更小值」類問題。
核心思路：從左到右掃描，維護一個單調遞減棧（棧底最大）。當新元素比棧頂大時，棧頂元素找到了它的「下一個更大值」，此時彈出並記錄答案。
// 通用單調棧模板 — 找每個元素右側第一個更大值
function nextGreaterElements(nums: number[]): number[] {
const n = nums.length;
const result = new Array(n).fill(-1);
const stack: number[] = []; // 儲存索引（重要：存索引才能計算距離）
for (let i = 0; i < n; i++) {
// 當前元素比棧頂元素大：棧頂找到了它的「下一個更大值」
while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
const idx = stack.pop()!;
result[idx] = nums[i]; // 記錄答案
}
stack.push(i); // 壓入當前索引
}
// 棧中剩餘元素：右側無更大值，result 保持 -1
return result;
}
// 範例：nums = [2, 1, 5, 3, 6]
// 輸出： [5, 5, 6, 6, -1]
三、C++ STL 對照
C++ 標準庫提供了完整的 Stack、Queue 與 Deque 容器，是競程與系統程式設計的標準工具：
#include <stack>
#include <queue>
#include <deque>
#include <iostream>
void cppContainersDemo() {
// std::stack — 預設底層為 std::deque，可明確指定為 vector
std::stack<int, std::vector<int>> stk; // 效能敏感時指定 vector 底層
stk.push(1);
stk.push(2);
stk.push(3);
std::cout << stk.top() << "\n"; // 輸出：3
stk.pop();
std::cout << stk.top() << "\n"; // 輸出：2
// std::queue — 底層為 std::deque，front()/back() 查看兩端
std::queue<int> que;
que.push(1);
que.push(2);
que.push(3);
std::cout << que.front() << "\n"; // 輸出：1（先進）
que.pop();
std::cout << que.front() << "\n"; // 輸出：2
// std::deque — 兩端操作均為 O(1)，支援隨機存取
std::deque<int> deq;
deq.push_front(0);
deq.push_back(1);
deq.push_front(-1);
// deq: [-1, 0, 1]
std::cout << deq.front() << " " << deq.back() << "\n"; // 輸出：-1 1
deq.pop_front();
deq.pop_back();
std::cout << deq.front() << "\n"; // 輸出：0
}
C++ 與 JavaScript 的主要差異：
| 操作 | C++ | JavaScript/TypeScript |
|---|---|---|
| Stack push | stk.push(x) | arr.push(x) |
| Stack pop | stk.pop() | arr.pop() |
| Stack peek | stk.top() | arr[arr.length-1] |
| Queue enqueue | que.push(x) | 自行實作 |
| Queue dequeue | que.pop() | 自行實作（避免 shift()） |
| Deque front push | deq.push_front(x) | arr.unshift(x)（O(n)！） |
四、複雜度分析
| 操作 | Stack | Queue（head 指標版） | Deque（鏈結串列底層） | 備註 |
|---|---|---|---|---|
| push / enqueue | O(1) amortized | O(1) amortized | O(1) | 陣列動態擴容時偶發 O(n) |
| pop / dequeue | O(1) | O(1) | O(1) | — |
| peek / front | O(1) | O(1) | O(1) | 僅讀取，不移除 |
| isEmpty | O(1) | O(1) | O(1) | — |
| size | O(1) | O(1) | O(1) | 需維護計數器 |
Array shift() dequeue | — | O(n) | — | 陷阱！ 避免使用 |
| MinStack getMin | O(1) | — | — | 輔助棧空間換時間 |
五、變體與延伸
單調佇列（Monotonic Queue）— 滑動視窗最大值
單調佇列 使用 Deque 維護滑動視窗內的最大（或最小）值，讓每次滑動的查詢達到 O(1) 攤銷時間：
// LeetCode 239 — Sliding Window Maximum
// 維護一個單調遞減 Deque（front 永遠是當前視窗最大值的索引）
function maxSlidingWindow(nums: number[], k: number): number[] {
const result: number[] = [];
const deque: number[] = []; // 儲存索引
for (let i = 0; i < nums.length; i++) {
// 步驟一：移除超出視窗範圍的舊索引（從 front 移除）
while (deque.length > 0 && deque[0] < i - k + 1) {
deque.shift();
}
// 步驟二：維護單調遞減 — 移除比當前元素小的索引（從 back 移除）
// 這些被移除的元素永遠不可能成為視窗最大值
while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
deque.pop();
}
// 步驟三：加入當前索引
deque.push(i);
// 步驟四：視窗大小達到 k 後，front 即為當前視窗最大值
if (i >= k - 1) {
result.push(nums[deque[0]]);
}
}
return result;
}
// 時間：O(n)（每個元素至多入隊一次、出隊一次）
// 空間：O(k)
// 範例：nums = [1,3,-1,-3,5,3,6,7], k = 3
// 輸出： [3,3,5,5,6,7]
雙 Stack 實作 Queue
用兩個 Stack 模擬 Queue 的 FIFO 行為：pushStack 負責接收新元素，popStack 負責提供元素。當 popStack 為空時，才將 pushStack 的全部元素轉移（每個元素只轉移一次，攤銷後 pop 為 O(1)）：
// LeetCode 232 — Implement Queue using Stacks
class MyQueue {
private pushStack: number[] = []; // 接收新元素
private popStack: number[] = []; // 提供元素（已反轉順序）
push(x: number): void {
this.pushStack.push(x);
}
pop(): number {
this.migrate();
return this.popStack.pop()!;
}
peek(): number {
this.migrate();
return this.popStack[this.popStack.length - 1];
}
empty(): boolean {
return this.pushStack.length === 0 && this.popStack.length === 0;
}
// 只有 popStack 為空時才轉移，保證每個元素只移動一次
private migrate(): void {
if (this.popStack.length === 0) {
while (this.pushStack.length > 0) {
this.popStack.push(this.pushStack.pop()!);
}
}
}
}
// 攤銷複雜度：push O(1)，pop/peek O(1) amortized，empty O(1)
// 操作示意：
// push(1), push(2), push(3) → pushStack: [1,2,3], popStack: []
// peek() → migrate → pushStack: [], popStack: [3,2,1]
// → popStack.peek() = 1（正確 FIFO！）
// pop() → 移除 1，回傳 1
六、面試考點
括號匹配（LeetCode 20 — Valid Parentheses）
括號匹配是 Stack 最經典的應用。遇到左括號時推入棧，遇到右括號時驗證棧頂是否為對應的左括號：
// LeetCode 20 — Valid Parentheses（Easy）
function isValid(s: string): boolean {
const stack: string[] = [];
const pairs: Record<string, string> = {
')': '(',
']': '[',
'}': '{'
};
for (const char of s) {
if ('([{'.includes(char)) {
stack.push(char); // 左括號：推入棧
} else {
// 右括號：棧頂必須是對應的左括號，且棧不能為空
if (stack.length === 0 || stack[stack.length - 1] !== pairs[char]) {
return false;
}
stack.pop();
}
}
return stack.length === 0; // 棧清空代表完全匹配
}
// 測試：
console.log(isValid("()[]{}")); // 輸出：true
console.log(isValid("([)]")); // 輸出：false
console.log(isValid("{[]}")); // 輸出：true
延伸思路：相同的 Stack 邏輯可應用於 HTML 標籤匹配、程式碼 Linter 的巢狀作用域追蹤，任何「需要匹配對應關係」的問題都可優先考慮 Stack。
七、LeetCode 練習題
LeetCode 20 — Valid Parentheses（Easy）
見上方括號匹配範例，Stack 的入門必練題。
LeetCode 155 — Min Stack（Medium）
見上方 MinStack 實作，核心是同步輔助棧記錄最小值快照。
LeetCode 232 — Implement Queue using Stacks（Easy）
見上方雙 Stack 實作，理解攤銷分析的好題目。
LeetCode 239 — Sliding Window Maximum（Hard）
見上方單調佇列實作，單調 Deque 的代表題。
LeetCode 84 — Largest Rectangle in Histogram（Hard）
思路：對每個柱子，找左右兩側第一個比它矮的柱子，以確定最大矩形的寬度。使用單調遞增棧（棧底最小），當新柱子比棧頂矮時，棧頂柱子確定了右邊界，同時新的棧頂是左邊界。在首尾各插入高度 0 的哨兵柱，能簡化邊界處理：
// LeetCode 84 — Largest Rectangle in Histogram（Hard）
function largestRectangleInHistogram(heights: number[]): number {
// 加入哨兵：左右各一根高度為 0 的柱子，確保所有柱子都能被彈出並計算
const h = [0, ...heights, 0];
const stack: number[] = []; // 單調遞增棧，儲存索引
let maxArea = 0;
for (let i = 0; i < h.length; i++) {
// 當前柱子比棧頂矮：棧頂柱子確定了右邊界
while (stack.length > 0 && h[stack[stack.length - 1]] > h[i]) {
const height = h[stack.pop()!];
// 彈出後，新棧頂是左邊界；當前 i 是右邊界
const width = i - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}
// 時間：O(n)，空間：O(n)
// 範例說明：heights = [2, 1, 5, 6, 2, 3]
// 加哨兵： [0, 2, 1, 5, 6, 2, 3, 0]
// 最大矩形：高度 5，寬度 2 → 面積 10
console.log(largestRectangleInHistogram([2, 1, 5, 6, 2, 3])); // 輸出：10
C++ 解法：
// C++ 解法 — Largest Rectangle in Histogram
#include <vector>
#include <stack>
int largestRectangleArea(std::vector<int> heights) {
// 加入哨兵
heights.insert(heights.begin(), 0);
heights.push_back(0);
std::stack<int> stk;
int maxArea = 0;
for (int i = 0; i < (int)heights.size(); ++i) {
while (!stk.empty() && heights[stk.top()] > heights[i]) {
int height = heights[stk.top()];
stk.pop();
int width = i - stk.top() - 1;
maxArea = std::max(maxArea, height * width);
}
stk.push(i);
}
return maxArea;
}
// 時間：O(n)，空間：O(n)
八、常見陷阱整理
在實作 Stack/Queue 相關題目時，以下是最容易犯的錯誤，務必牢記：
陷阱一：用 Array.shift() 模擬 dequeue
shift()需要移動所有元素，時間複雜度為 O(n)，資料量大時效能會急速下降- 改用 head 指標或鏈結串列實作
陷阱二：單調棧只儲存值而非索引
- 解決「寬度計算」類問題（如柱狀圖最大矩形）時，必須儲存索引才能計算距離
- 規則：需要計算距離或位置時，棧存索引；只需要比較大小時，棧可存值
陷阱三：滑動視窗 Deque 忘記移除超出範圍的舊索引
- 單調佇列必須同時維護兩件事：①從 back 移除比當前元素小的索引；②從 front 移除超出視窗的索引
- 漏掉任一步都會導致錯誤結果
陷阱四：MinStack 只記錄一個全域最小值
- 當最小值被 pop 之後，無法得知次小值
- 必須使用同步輔助棧，記錄每個時刻的最小值快照
陷阱五：雙 Stack 模擬 Queue 時，每次 pop 都強制 migrate
- 只有在
popStack為空時才能 migrate；若popStack仍有元素就轉移，會破壞 FIFO 順序
總結
本文從生活類比出發，系統介紹了 Stack（堆疊） 與 Queue（佇列） 的核心差異、JavaScript/TypeScript 完整實作，以及 C++ STL 的對應容器。更進一步地，我們探討了：
- Deque（雙端佇列）：一個結合 Stack 與 Queue 特性的萬用工具
- MinStack：以輔助棧換取 O(1) 查詢最小值的巧妙設計
- 雙 Stack 模擬 Queue：理解攤銷分析的經典習題
- 單調棧與單調佇列：解鎖 O(n) 解法的進階技巧，應用於 Next Greater Element、柱狀圖最大矩形、滑動視窗最大值等 Hard 題型
這兩種資料結構看似簡單，但在面試中以各種形式出現。真正的關鍵不是背誦程式碼，而是理解「什麼時候用 Stack，什麼時候用 Queue」——前者適合「需要反向處理、追蹤最近狀態」的場景，後者適合「按順序處理、保持到達順序」的場景。
下一篇將進入**雜湊表（Hash Table）**的世界，探索 JavaScript 的 Map 與 Set 底層原理，以及如何用 O(1) 查找解決兩數之和、字母異位詞等常見面試題。如有任何問題或疑惑，歡迎透過 聯絡頁面 與我交流！