3.1 堆疊的實作與應用#

概念說明#

堆疊（stack）的 ADT 只有三個核心操作：

push(x)：把 x 放到頂端。
pop()：取出並回傳頂端元素（空堆疊則報錯）。
peek()：看頂端但不取出。

最後放入的最先出來，即 LIFO。在 Python 中 list 就是現成的堆疊：append 是 push、pop()（無參數）是 pop、lst[-1] 是 peek，全部 O(1)。

應用一：括號配對#

演算法步驟：

由左至右掃描字元。
遇到開括號 ([{ 就 push。
遇到閉括號就 pop，檢查是否為對應的開括號；不對或堆疊已空則不合法。
掃完後堆疊必須是空的。

def is_balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

print(is_balanced("{[()]}"))     # True
print(is_balanced("{[(])}"))     # False
print(is_balanced("((()))"))     # True
print(is_balanced("(()"))        # False（左括號多）

應用二：後序運算式求值#

後序（postfix）如 3 4 + 2 * 表示 (3+4)*2。步驟：遇到數字就 push；遇到運算子就 pop 兩個數字計算後 push 回去。掃完時堆疊中剩下的唯一數字即答案。

def eval_postfix(expr):
    stack = []
    for tok in expr.split():
        if tok in '+-*/':
            b = stack.pop()          # 注意順序：先 pop 的是右運算元
            a = stack.pop()
            stack.append({'+': a + b, '-': a - b,
                          '*': a * b, '/': a / b}[tok])
        else:
            stack.append(float(tok))
    return stack.pop()

print(eval_postfix("3 4 + 2 *"))          # 14.0
print(eval_postfix("5 1 2 + 4 * + 3 -"))  # 14.0，即 5+(1+2)*4-3

編譯器把中序轉成後序（shunting-yard 演算法）同樣靠堆疊暫存運算子，可見堆疊是「處理巢狀與優先權」的通用工具。

自製堆疊類別#

需要自訂行為（如容量上限、型別檢查）時可包一層：

class Stack:
    def __init__(self, cap=None):
        self._items = []
        self._cap = cap

    def push(self, x):
        if self._cap is not None and len(self._items) >= self._cap:
            raise OverflowError("堆疊已滿")
        self._items.append(x)

    def pop(self):
        if not self._items:
            raise IndexError("堆疊為空")
        return self._items.pop()

    def peek(self):
        return self._items[-1]

    def is_empty(self):
        return not self._items

    def __len__(self):
        return len(self._items)

複雜度分析#

push、pop、peek 都是 O(1)（攤攤，理由同 2.1 節的 append）。空間 O(n)。深度優先搜尋（第9章）用堆疊時，空間為 O(路徑長度)，這也是堆疊與佇列在圖搜尋中的本質差異。

練習#

寫一個函式檢查 HTML 標籤是否正確巢狀，如 x 合法、x 不合法。
把中序運算式 "3 + 4 * 2" 轉成後序（實作 shunting-yard 的簡化版：只有 + - * / 與數字）。
用兩個堆疊實作一個佇列（push、pop），分析攤攤複雜度為何仍是 O(1)。