堆疊 Stack · 資料結構 Data Structures

堆疊

後進先出：只能在頂端放和拿。函式呼叫、括號配對、復原上一步，都是它。

示範

0A
1B
2C← top
3

剛放上去／正在讀的字元peek 看到的配不上已配置但沒用到

只能動最上面那一個：push 放上去、pop 拿下來、peek 只看不拿。

元素

容量

頂端

亮起來的是這一步執行的程式碼

1class Stack<T> {
2  private data: T[] = new Array(4);
3  private size = 0;
4 
5  push(value: T): void {
6    if (this.size === this.data.length) {
7      const bigger = new Array<T>(this.data.length * 2);
8      for (let i = 0; i < this.size; i++) bigger[i] = this.data[i];
9      this.data = bigger;
10    }
11    this.data[this.size++] = value;
12  }
13 
14  pop(): T | undefined {
15    if (this.size === 0) return undefined;
16    return this.data[--this.size];
17  }
18 
19  peek(): T | undefined {
20    return this.size === 0 ? undefined : this.data[this.size - 1];
21  }
22 
23  isEmpty(): boolean {
24    return this.size === 0;
25  }
26}
27 
28const PAIRS: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
29 
30function isBalanced(text: string): boolean {
31  const stack = new Stack<string>();
32  for (const ch of text) {
33    if (ch === "(" || ch === "[" || ch === "{") {
34      stack.push(ch);
35    } else if (ch in PAIRS) {
36      if (stack.pop() !== PAIRS[ch]) return false;
37    }
38  }
39  return stack.isEmpty();
40}

模型假設與範圍

Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

什麼時候用

後來的要先處理：函式呼叫、復原（undo）、瀏覽器的上一頁。
配對與巢狀結構：括號、HTML 標籤、運算式求值。
把遞迴改成迴圈：DFS（Depth-First Search，深度優先搜尋）用自己的堆疊取代呼叫堆疊，就不會因為遞迴太深而 stack overflow。

和其他主題的關係

由這些組成: 動態陣列
被這些用到: 單調堆疊與單調佇列演算法 · BFS 與 DFS 演算法 · 回溯演算法 · 強連通分量
延伸閱讀: 佇列與雙端佇列

語言內建的版本

Array<T>

操作	寫法	成本
推入	`stack.push(3)`	O(1) amortised
彈出	`stack.pop()`	O(1)
看頂端	`stack.at(-1)`	O(1)
是否為空	`stack.length === 0`	O(1)

const stack: number[] = [];
stack.push(1);
stack.push(2);
stack.push(3);                 // → 3
stack.at(-1);                  // → 3
stack[stack.length - 1];       // → 3
stack.pop();                   // → 3
stack;                         // → [1, 2]
stack.pop();                   // → 2
stack.pop();                   // → 1
stack.length === 0;            // → true
stack.pop();                   // → undefined
stack.at(-1);                  // → undefined
 
// Balanced brackets: push openers, pop on a closer.
const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
const balanced = (s: string) => {
  const open: string[] = [];
  for (const c of s) {
    if (!(c in pairs)) open.push(c);
    else if (open.pop() !== pairs[c]) return false;
  }
  return open.length === 0;
};
balanced("([]{})");            // → true
balanced("(]");                // → false

每個 → 後面的結果都是實際執行這段程式碼驗證過的。

JavaScript 沒有獨立的 stack 型別，陣列的 push／pop 就是。空陣列 pop() 不會丟錯，而是回傳 undefined，記得自己檢查 length。
別用 shift()／unshift() 從頭端當堆疊，那是 O(n)。

時間與空間複雜度（Big O）

操作	平均	最差
push 均攤 O(1)：只有擴容的那一次要複製	O(1)	O(n)
pop	O(1)	O(1)
peek	O(1)	O(1)
檢查長度 n 的括號字串每個字元最多 push 或 pop 一次	O(n)	O(n)

空間：O(n)，括號檢查最差時，整串都是左括號

Big O 實測：n 變大時步數怎麼長

數的是：寫入的格子數，或括號檢查做的 push＋pop 次數

	Big O	n = 1,000	n = 10,000	n = 100,000	成長倍數：實測（理論）
push（平均，含擴容）	O(1)	2.0	2.6	2.3	×1.1 (×1.0)
檢查長度 n 的括號字串	O(n)	1,000	10,000	100,000	×100 (×100)

真實世界裡的它

每個執行緒的呼叫堆疊：區域變數和返回位址都疊在上面，遞迴太深就是 stack overflow。
編輯器的復原和重做，是兩個堆疊互相倒來倒去。
JVM（Java Virtual Machine，Java 虛擬機）和 Python 的位元組碼都是堆疊機：a + b 會編譯成 push a、push b、add。

取捨與陷阱

對空堆疊 pop 一定要處理：先檢查，或像這裡回傳 undefined／None／null。
JavaScript 陣列的 push／pop 就是堆疊，但 shift／unshift 是在開頭動，每次都要搬動整個陣列（見佇列）。
只檢查「左右括號數量一樣」不夠：([)] 數量相等但交錯了，要靠堆疊才抓得到順序。

資料結構