堆疊與佇列：Swift 為何沒有 Stack 型別

開始學習資料結構時，最先遇到的兩兄弟就是堆疊（Stack）與佇列（Queue）。

概念本身五分鐘就能學會。但到了 Swift，會看到一個疑問：標準函式庫有 Array、Dictionary、Set，卻沒有 **Stack或 Queue 型別。**本文說明原因，以及沒有它們時該怎麼使用。

用陣列模擬佇列時遇到的效能地雷（removeFirst()），是程式解題中經常超時的原因，因此會另外詳細說明。

本文的堆疊是資料結構，不是記憶體配置區域。同名概念的差異見記憶體堆疊 vs 堆積；佇列具備優先順序的下一階段則見堆積與優先佇列。

---

概念就是盤子與排隊

堆疊是 LIFO（Last In, First Out）。最後放入的會最先取出。想像盤子堆：從頂端 push，也從頂端 pop。從中間取出是不合規則的。

佇列是 FIFO（First In, First Out）。最先放入的會最先取出。就像結帳排隊：從後方 enqueue，從前方 dequeue。

每種結構都只有兩個操作。

	放入	取出	查看
堆疊	push	pop	peek(top)
佇列	enqueue	dequeue	front

這麼簡單，為什麼重要？因為這項規則是 iOS 開發許多部分的骨架。

• 呼叫堆疊：函式呼叫與返回正是 push/pop。遞迴太深時發生的崩潰稱為 stack overflow，並非沒有原因。
• UINavigationController：pushViewController／popViewController——畫面轉換本質上就是堆疊。
• 復原（undo）：將命令堆入堆疊，再依反向順序復原。
• GCD（Grand Central Dispatch）的 DispatchQueue：如名稱所示，它就是佇列。放入 serial queue 的工作會依放入順序執行。
• BFS/DFS：圖形走訪使用佇列就是 BFS（Breadth-First Search，廣度優先搜尋），使用堆疊就是 DFS（Depth-First Search，深度優先搜尋）。選擇資料結構就是選擇演算法。

---

Swift 為何沒有 Stack

先說結論：因為Array 已經是完美的堆疊。

var stack: [Int] = []
stack.append(3)      // push — O(1)
stack.append(7)
let top = stack.last // peek — O(1)
let popped = stack.popLast() // pop — O(1), 為空時 nil

在陣列尾端放入與取出的操作都是 O(1)；更精確地說是 amortized O(1)，只有內部緩衝區填滿時才需付出擴充成本。另做型別也只是包住 Array，因此標準函式庫選擇不新增它。

若想表達意圖，慣例上會加一層薄薄的包裝。

struct Stack<Element> {
    private var storage: [Element] = []
    var isEmpty: Bool { storage.isEmpty }
    var top: Element? { storage.last }
    mutating func push(_ element: Element) { storage.append(element) }
    mutating func pop() -> Element? { storage.popLast() }
}

它會阻擋subscript，透過型別強制堆疊「禁止存取中間元素」的規則。

---

用陣列建立佇列會掉進陷阱

用與堆疊相同的邏輯建立佇列，會變成這樣。

var queue: [Int] = []
queue.append(1)              // enqueue — O(1), 沒有問題
let first = queue.removeFirst() // dequeue — O(n), 陷阱就在這裡

removeFirst()會移除最前面的元素，並將**其餘元素全部向前移一格。**若有十萬個元素，一次 dequeue 就會發生十萬次移動。在 BFS 這類反覆 dequeue 數萬次的演算法中，整體會變成 O(n²)，程式解題便會超時。

解法有三種。

1. 用索引推進前端（程式解題標準作法）

var queue: [Int] = []
var head = 0
// enqueue
queue.append(5)
// dequeue
let value = queue[head]
head += 1

不實際移除元素，只移動讀取位置。dequeue 變成 O(1)；前方已用過的記憶體仍會保留，但在程式解題中幾乎總是足夠。

2. 用兩個堆疊建立佇列（面試常見題）

放入時堆到 in 堆疊；取出時若 out 堆疊為空，就把 in 整個反轉搬過去，再 pop。每個元素最多移動兩次，因此是 amortized O(1)。這也是「用堆疊實作佇列」面試題的標準答案。

3. swift-collections 的 Deque（實務解答）

Apple 維護的swift-collections套件，其Deque採用環形緩衝區，因此兩端插入與刪除都是 O(1)。

import DequeModule

var queue: Deque<Int> = []
queue.append(1)            // enqueue
let v = queue.popFirst()   // dequeue — O(1)

它的 API 幾乎與 Array 相同，因此替換成本低。實務需要佇列時，直接使用它，不要自行實作。

---

選擇哪一種的判斷標準

感到混淆時，問自己一個問題即可：「要先處理後來的，還是先處理先來的？」

• 復原、括號配對檢查、回溯走訪路徑、深度優先搜尋 → 最新者優先 → 堆疊
• 工作等待列、事件處理、列印輸出、廣度優先搜尋 → 保證抵達順序 → 佇列

括號配對檢查是堆疊的代表應用，簡單說明一下：遇到左括號就 push，遇到右括號就 pop 並確認是否配對；結束時堆疊為空，表示運算式有效。編譯器檢查程式碼大括號的原理也相同。

---

總結

• 堆疊是 LIFO，佇列是 FIFO——盤子堆與結帳排隊就能說明全部概念。
• 呼叫堆疊、導覽堆疊、undo 是堆疊；DispatchQueue、事件處理、BFS 是佇列——它們早已遍布 iOS 開發。
• Swift 沒有 Stack 型別，是因為Array 的 append/popLast 已經是 O(1) 堆疊。
• 用陣列建立佇列時，removeFirst()是 O(n)——程式解題超時的常見原因。
• 解法是 head 索引、兩個堆疊，或實務上使用 swift-collections 的Deque。
• 選堆疊還是佇列，只取決於一個問題：「最新者優先，還是抵達順序優先？」

下一篇將接著介紹兩者的應用版本：堆積與優先佇列，以及 Dictionary 背後的雜湊表。