演算法圖鑑
Stack & Queue · 01 / 04

Stack堆疊

push / pop / peek，呼叫堆疊與括號配對。

用在：undo、括號檢查、運算式求值、DFS

時間複雜度O(1)
空間複雜度O(n)
難度入門
前置知識Array & Dynamic Array

01為什麼需要它

編輯器的括號檢查與 Ctrl+Z

程式碼裡的括號要成對，而且「最近打開的必須最先關閉」。undo 也一樣：最後做的操作要最先被撤銷。

為什麼用它堆疊只允許從同一端進出，天生就是「後進先出」。左括號推入、右括號彈出比對；每個操作推入、undo 就彈出。結構本身就表達了規則。

函式呼叫怎麼記得「回到哪裡」

A 呼叫 B、B 呼叫 C，C 結束後要回到 B 的哪一行、B 結束後回到 A 的哪一行？遞迴時同一個函式還有幾十層。

為什麼用它呼叫堆疊：每次呼叫推入一層紀錄，返回就彈出。遞迴那篇看到的 call stack 就是堆疊。DFS 用堆疊、BFS 用佇列，也是同一個道理。

計算機怎麼算 3 + 4 × 2

運算式有優先順序和括號，從左到右直接算會錯。編譯器、試算表、計算機都要正確處理。

為什麼用它把運算式轉成後綴（逆波蘭）表示法，用一個堆疊就能從左到右一次算完：數字推入、遇到運算子彈兩個算完推回去。

看到這些關鍵字就想到它：後進先出、最近的先處理、配對、undo、巢狀結構、運算式求值、DFS 的迭代版。

02核心概念

堆疊只有三個操作：push 放到頂端、pop 從頂端拿走、peek 看頂端。後進先出（LIFO）：最後放進去的最先被拿出來。全部 O(1)。它簡單到用陣列的尾端就能做（尾端增刪 O(1)），Python 的 list、C++ 的 std::stack 都是這樣。

堆疊的價值不在操作多快，而在它記住了順序。任何「最近打開的要最先關閉」「進入後要能原路退回」的問題，堆疊的結構就是答案的一半：括號配對、巢狀標籤、函式呼叫、路徑的 ..、undo/redo、DFS 的迭代寫法。

一個常見的擴充是每一層多存一點資訊。Min Stack 在每個元素旁邊記「到這裡為止的最小值」，pop 之後最小值自動回到上一層的紀錄，不用重算。下一篇的單調堆疊則是對「什麼時候該 pop」加上條件，把 O(n²) 的問題壓成 O(n)。

03演算法步驟

  1. 1辨認問題有沒有「最近的先處理」的結構：巢狀、配對、回溯、需要記得走過的路。
  2. 2決定堆疊裡存什麼：字元、索引、還是 (值, 附加資訊) 的組合。存索引通常比存值靈活。
  3. 3從左到右掃輸入。遇到「開啟」就 push；遇到「關閉」先檢查堆疊是否為空，再和頂端比對後 pop。
  4. 4掃完後檢查堆疊是否清空：剩東西通常代表有未關閉的項目。
  5. 5用三種輸入驗證：空輸入、只有關閉沒有開啟、只有開啟沒有關閉。

04互動示範

選一個字串逐步看括號配對：左括號推入，右括號和頂端比對後彈出。三種不合法的情況分別在哪一步被抓到。

輸入字串
([{}])
堆疊（頂 → 底）
空
步驟 0/7堆疊是空的。從左到右讀每個字元：左括號推入，右括號就和頂端比對。

05程式碼

基本操作、括號配對、後綴表達式求值、以及每層多存一個最小值的 Min Stack。C++ 注意 pop() 不回傳值，要先 top()。

# Python 的 list 就是堆疊：append 推入、pop 彈出、[-1] 看頂端，全部 O(1)
stack = []
stack.append(1)
stack.append(2)
stack[-1]          # 2（peek）
stack.pop()        # 2
len(stack) == 0    # 是否為空


# 括號配對（LeetCode 20）
def is_valid(s):
    pair = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c in pair:                          # 右括號
            if not stack or stack[-1] != pair[c]:
                return False
            stack.pop()
        else:                                  # 左括號
            stack.append(c)
    return not stack                           # 剛好全部配完


# 後綴表達式求值（LeetCode 150）："2 1 + 3 *" → (2+1)*3 = 9
def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in "+-*/":
            b, a = stack.pop(), stack.pop()    # 注意順序：先彈出的是右運算元
            if t == "+": stack.append(a + b)
            elif t == "-": stack.append(a - b)
            elif t == "*": stack.append(a * b)
            else: stack.append(int(a / b))     # 向零截斷
        else:
            stack.append(int(t))
    return stack[0]


# Min Stack（LeetCode 155）：多存一個「到目前為止的最小值」
class MinStack:
    def __init__(self):
        self.stack = []        # (值, 當時的最小值)

    def push(self, x):
        cur_min = min(x, self.stack[-1][1]) if self.stack else x
        self.stack.append((x, cur_min))

    def pop(self):
        self.stack.pop()

    def top(self):
        return self.stack[-1][0]

    def get_min(self):
        return self.stack[-1][1]

06練習題

  • LeetCode 20Valid ParenthesesEasy
  • LeetCode 155Min StackMedium
  • LeetCode 150Evaluate Reverse Polish NotationMedium
  • LeetCode 71Simplify PathMedium
  • LeetCode 394Decode String（巢狀）Medium
  • LeetCode 224Basic CalculatorHard
上一篇—下一篇Queue & Deque