堆疊與佇列

為什麼瀏覽器的「上一頁」永遠記得你剛剛在哪裡？

想像你在網路上連點了十幾個頁面，從首頁逛到某篇文章，再點進作者介紹，又跳到一張地圖。這時候你按下「上一頁」，瀏覽器精準地把你帶回上一個畫面；再按一次，又回到更早的那一頁。它怎麼總是「記得」你來時的路？

答案藏在一種叫做堆疊(stack) 的資料結構裡。每進入一個新頁面，瀏覽器就把它「疊」上去；每按一次上一頁，就把最上面那一個「拿」下來。最後放上去的，最先被取走。

與堆疊相對的，是日常生活中更熟悉的佇列(queue)：排隊買飲料時，先到的人先買到，後到的人乖乖排在後面。這兩種看似簡單的結構，是電腦科學裡使用頻率最高的工具之一，從函數呼叫、括號檢查，到搜尋一張地圖的最短路徑，背後都有它們的身影。

堆疊：後進先出(LIFO)

堆疊的核心規則只有一句話：後進先出(Last In, First Out, LIFO)。最晚放進去的元素，會最先被拿出來。你可以把它想像成一疊盤子——你只能從最上面拿，也只能往最上面放。

堆疊提供兩個基本操作：

• push（推入）：把一個元素放到堆疊頂端。
• pop（彈出）：把頂端的元素取出並移除。

通常還會附帶一個 peek（或 top） 操作，只看頂端是什麼但不取走。理想情況下，這三個操作都是 $O(1)$ 的常數時間，因為我們永遠只碰「頂端」這一個位置。

下面用文字模擬一個堆疊的變化過程。假設我們依序 push 進 A、B、C，再 pop 兩次：

push(A):  [A]              ← 頂端在右
push(B):  [A, B]
push(C):  [A, B, C]
pop():    [A, B]      回傳 C
pop():    [A]         回傳 B

注意彈出的順序是 C、B，恰好與推入順序 A、B、C 相反。這個「反轉」的特性，正是堆疊許多應用的關鍵。

佇列：先進先出(FIFO)

佇列的規則同樣只有一句話：先進先出(First In, First Out, FIFO)。最早進入的元素，最早離開。這完全對應排隊的直覺：先排的人先走。

佇列的兩個基本操作分別發生在「兩端」：

• enqueue（入列）：把元素加到佇列的尾端。
• dequeue（出列）：從佇列的前端取出並移除元素。

同樣依序加入 A、B、C，再取出兩次：

enqueue(A):  front[A]back
enqueue(B):  front[A, B]back
enqueue(C):  front[A, B, C]back
dequeue():   front[B, C]back     回傳 A
dequeue():   front[C]back        回傳 B

這次取出的順序是 A、B，與加入順序完全一致。堆疊「反轉」，佇列「保序」——這是兩者最本質的差異。

動手看一個例子：括號是否成對？

堆疊有一個非常經典的應用：檢查一段程式碼或數學式中的括號是否正確配對。例如 ([]{}) 是合法的，而 ([)] 則不是——雖然每種括號的左右數量都相等，但交錯了。

它的核心想法是：遇到左括號就 push，遇到右括號就檢查堆疊頂端是不是「對應的」左括號，若是就 pop。為什麼用堆疊？因為最近一個還沒被關閉的左括號，一定是最先需要被關閉的——這正是 LIFO。

def is_balanced(s: str) -> bool:
    """檢查字串中的括號是否正確配對"""
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)            # push 左括號
        elif ch in ')]}':
            # 堆疊為空，或頂端不匹配 → 失敗
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack                    # 最後堆疊須為空

我們用 ([)] 走一次流程：

程式在第三步就正確判定 ([)] 不合法。同理，([]{}) 會一路順利配對到最後，堆疊清空，回傳 True。整個演算法只掃描字串一次，時間複雜度 $O(n)$，空間複雜度最壞 $O(n)$。

函數呼叫：藏在語言背後的堆疊

堆疊還有一個你每天都在用、卻看不見的應用：程式語言的呼叫堆疊(call stack)。當函數 A 呼叫函數 B、B 又呼叫 C，系統會把每一層的「現場」（區域變數、回傳位址）push 進呼叫堆疊。C 執行完畢就 pop 回 B，B 完成再 pop 回 A。

這也解釋了一個常見的錯誤訊息：堆疊溢位(stack overflow)。當遞迴沒有正確的終止條件，函數一層層呼叫自己而不返回，呼叫堆疊不斷增長，最終耗盡記憶體而崩潰。理解了堆疊，這個錯誤就不再神秘。

佇列與廣度優先搜尋(BFS)

佇列最有代表性的應用是廣度優先搜尋(Breadth-First Search, BFS)——從一個起點出發，像漣漪一樣「由近而遠」逐層探索一張圖或迷宮，常用來尋找最短路徑（以邊數計算）。

BFS 的關鍵在於：先發現的節點要先被展開。把「待探索」的節點放進佇列，每次從前端 dequeue 一個出來處理，並把它尚未拜訪過的鄰居 enqueue 到尾端。因為佇列保持先進先出，距離起點越近的節點越早被處理，自然就保證了「逐層擴散」。

from collections import deque

def bfs(graph, start):
    """從 start 出發，回傳拜訪節點的順序"""
    visited = {start}
    queue = deque([start])      # deque 適合兩端操作
    order = []
    while queue:
        node = queue.popleft()  # dequeue：取出前端
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)   # enqueue：加到尾端
    return order

若把這裡的佇列換成堆疊（改用 push/pop），整個演算法就會變成深度優先搜尋(DFS)——一路鑽到底再回頭。光是「換一種資料結構」，搜尋的行為就徹底不同，這正是資料結構選擇的威力。

重點回顧

• 堆疊是 LIFO（後進先出），操作為 push／pop，最晚放入的最先取出；典型應用有函數呼叫、括號匹配、運算式求值、瀏覽器上一頁。
• 佇列是 FIFO（先進先出），操作為 enqueue／dequeue，最早放入的最先取出；典型應用有 BFS、工作排程、緩衝區(buffer)。
• 兩者的基本操作理想上都是 $O(1)$，差別只在「從哪一端取出」。
• 同一個演算法骨架，把堆疊換成佇列就從 DFS 變 BFS，凸顯資料結構選擇的決定性影響。
• 遞迴失控會造成呼叫堆疊的堆疊溢位，這是堆疊概念在實務中的直接體現。

深入探討（研究所視角）

用陣列還是串列實作？兩種取捨

堆疊與佇列是抽象資料型別(Abstract Data Type, ADT)——它們定義「行為」，但不規定「實作」。實務上最常見的兩條路是動態陣列(dynamic array) 與鏈結串列(linked list)，各有取捨。

堆疊用陣列實作相當自然：維護一個陣列與一個 top 索引，push 就是寫入 arr[top] 並 top += 1，pop 反之。陣列的記憶體連續，快取局部性(cache locality) 良好，實際執行速度往往優於串列。代價是容量固定，滿了需要擴容(resizing)——通常採取「容量加倍」策略。單次擴容是 $O(n)$ 的複製，但因為擴容不常發生，攤還分析(amortized analysis) 顯示每次 push 的攤還成本仍是 $O(1)$。

用鏈結串列實作則天生支援動態大小，不需擴容，且最壞情況下每次操作都是嚴格 $O(1)$（適合對延遲敏感的即時系統）。但每個節點都要額外存放指標，記憶體開銷較大，且節點散落各處，快取命中率較差。

佇列用陣列實作會遇到一個額外難題：dequeue 從前端移除元素後，若把後面所有元素往前搬，單次操作就退化為 $O(n)$。若改成只移動 front 指標而不搬資料，陣列前段的空間就「浪費」掉了，front 與 rear 會不斷向右漂移，直到撞上陣列邊界——這就引出了下面的環狀佇列。

環狀佇列(circular queue)

環狀佇列用「取模」的技巧，把一維陣列在邏輯上首尾相接成一個環，讓被 dequeue 釋放出的前段空間能被後續的 enqueue 重複利用，達到固定容量下的 $O(1)$ 操作而無需搬移資料。

核心是兩個索引 front、rear，每次前進都對容量取模：

$$\text{rear} \leftarrow (\text{rear} + 1) \bmod N$$

其中 $N$ 為陣列容量。如此一來索引走到陣列末端時會自動「繞回」開頭。一個微妙的問題是：佇列為空與佇列為滿時，front 與 rear 可能指向同一位置，難以區分。常見的兩種解法是：(1) 額外維護一個 count 計數器記錄目前元素數量；(2) 刻意「浪費」一個格子，規定當 (rear + 1) mod N == front 即視為滿，這樣空與滿就能用不同條件區分。

class CircularQueue:
    def __init__(self, capacity: int):
        self.data = [None] * capacity
        self.capacity = capacity
        self.front = 0
        self.count = 0              # 用計數器區分空與滿

    def enqueue(self, x) -> bool:
        if self.count == self.capacity:
            return False            # 已滿
        rear = (self.front + self.count) % self.capacity
        self.data[rear] = x
        self.count += 1
        return True

    def dequeue(self):
        if self.count == 0:
            return None             # 已空
        x = self.data[self.front]
        self.front = (self.front + 1) % self.capacity
        self.count -= 1
        return x

環狀佇列在系統層面無所不在：作業系統的鍵盤輸入緩衝區、網路封包的接收緩衝、串流音訊的 ring buffer、生產者—消費者(producer-consumer)模型中的有界緩衝區，幾乎都採用這個結構。它的優勢在於固定且可預測的記憶體用量——對嵌入式系統與即時系統而言至關重要。

延伸的變體與連結

從這兩個基礎結構出發，可以延伸出許多重要變體：

• 雙端佇列(deque, double-ended queue)：兩端都能 push／pop，是堆疊與佇列的超集。Python 的 collections.deque 即是高效實作，前述 BFS 範例正是用它。
• 優先佇列(priority queue)：出列順序由「優先級」而非到達順序決定，通常以堆積(heap) 實作，是 Dijkstra 最短路徑、Huffman 編碼等演算法的核心。
• 單調堆疊／單調佇列(monotonic stack/queue)：維護元素單調性，能在 $O(n)$ 時間解決「下一個更大元素」「滑動視窗最大值」等問題，是競賽與面試的高頻技巧。

理論上，堆疊與佇列也是計算理論的基石：下推自動機(pushdown automaton)正是「有限狀態機加上一個堆疊」，其辨識能力恰好對應上下文無關文法(context-free grammar)——這也是為什麼編譯器的語法剖析(parsing)離不開堆疊。從最樸素的「一疊盤子」，一路通向形式語言理論的深處，這正是基礎資料結構之美。