堆疊與佇列教學：LIFO 與 FIFO 的差別與 Python 範例

堆疊與佇列解決什麼問題

許多程式需要先記住一些項目，稍後再依固定順序處理。堆疊先給你最新的項目，適合處理巢狀的工作：函式呼叫、復原歷史、括號配對與深度優先搜尋。佇列先給你最舊的項目，適合公平的等待順序：列印工作、工作排程器、訊息佇列與廣度優先搜尋。

兩者都是抽象資料型別（abstract data type）：由它支援的操作來定義，而不是由儲存方式決定。你可以用陣列或鏈結串列來實作任何一種。

操作與名稱

實例演練：逐步看 push 與 pop

把 1、2、3 依序放進兩種結構，再各移除兩個項目。

Python 實作

Python 的 list 本身就是很好的堆疊：append 與 pop() 操作串列的尾端，均攤時間為 O(1)。至於佇列，不要使用 list.pop(0)，因為它會搬移所有剩下的元素，成本是 O(n)。請改用 collections.deque，兩端操作都是 O(1)。

from collections import deque
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop(), stack[-1])   # 3 2
queue = deque()
queue.append("a")
queue.append("b")
queue.append("c")
print(queue.popleft(), queue[0])  # a b
print(len(stack), len(queue))     # 2 2

如果你想要有名稱清楚的方法和明確的錯誤訊息，可以用一個小類別包裝這些內建型別：

from collections import deque
class Queue:
    def __init__(self):
        self._items = deque()
    def enqueue(self, item):
        self._items.append(item)
    def dequeue(self):
        if not self._items:
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()
    def __len__(self):
        return len(self._items)
q = Queue()
q.enqueue("job1")
q.enqueue("job2")
print(q.dequeue(), len(q))  # job1 1

經典堆疊問題：括號配對

要檢查每個括號是否都以正確順序閉合，只要把每個左括號 push 進去。遇到右括號時，堆疊頂端必須是與它配對的左括號。

def is_balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack
print(is_balanced("f(a[1], {b: 2})"))  # True
print(is_balanced("(]"))               # False
print(is_balanced("(("))               # False

同樣的想法也能用來計算後序表示式（逆波蘭表示法）、把遞迴改寫成迴圈，以及實現深度優先搜尋：用你自己的串列取代呼叫堆疊。

經典佇列問題：廣度優先搜尋

廣度優先搜尋會一層一層地走訪圖。佇列正好做到這一點：先被發現的節點先被處理。

from collections import deque
def bfs_order(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(bfs_order(graph, "A"))  # ['A', 'B', 'C', 'D']

時間與空間複雜度

均攤（amortized）的意思是：偶爾某次 append 會調整底層陣列的大小，成本為 O(n)，但平均分攤到大量操作上，每次仍是 O(1)。

變體與常見錯誤

• 雙端佇列（deque）：兩端都能新增與移除。collections.deque 就是一種，它既能當堆疊也能當佇列。
• 優先佇列（priority queue）：先移除最小（或最大）的項目，而不是最舊的。請使用 heapq，詳見二元堆積那一頁。
• 環形緩衝區（circular buffer）：以環繞索引存放在陣列中的固定大小佇列。deque(maxlen=n) 在滿了之後會丟掉最舊的項目。
• 執行緒安全佇列：queue.Queue 用於執行緒，asyncio.Queue 用於協程，等待項目時會阻塞。
• 用兩個堆疊做出佇列：push 到輸入堆疊，當輸出堆疊為空時，再把全部項目倒過去。每個項目只會搬移一次，所以操作為均攤 O(1)。