第3章 堆疊與佇列#

本章目標#

• 用陣列與串列實作堆疊，並應用於括號配對與運算式求值。
• 理解佇列與環形緩衝的實作，體會 deque 的價值。
• 建立優先權佇列的觀念，為第7章堆積鋪路。

章前言#

堆疊與佇列是「限制最嚴格」的線性結構：它們只允許在特定端點存取資料。堆疊是後進先出（LIFO）——像一疊盤子，只能從最上面放與拿；佇列是先進先出（FIFO）——像排隊買票，先來的先服務。這些限制看似不便，實際上正是它們的力量：介面簡單、行為可預測、操作全是 O(1)，而且是許多複雜演算法的底層骨架。

堆疊最經典的應用包括：括號配對檢查、運算式求值與轉換、瀏覽器的上一頁、程式語言的函式呼叫堆疊、深度優先搜尋。佇列則是：列印排程、工作排程、廣度優先搜尋、訊息系統的緩衝。環形緩衝進一步解決「固定大小、持續吐納」的串流問題；優先權佇列再放寬規則——不是看誰先來，而是看誰最急，成為作業系統排程與 Dijkstra 最短路徑的關鍵零件。

本章策略是「先用現成的、再懂內部的」：堆疊用 Python list 即可（append/pop 都是 O(1)）；佇列則要用 deque，因為 list.pop(0) 是 O(n)。接著自製環形緩衝與優先權佇列，理解「限制」如何換來效率與清晰。