スタックとキュー：SwiftにStack型がない理由

データ構造の勉強を始めると、最初に出会う二人の兄弟がスタックとキューです。

概念自体は5分で理解できます。しかし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()は先頭要素を取り除き、**残りすべてを1つ前へ移動します。**要素が10万個あると、dequeue一回で10万回の移動が起きます。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します。各要素の移動は最大2回なので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)

ArrayとAPIがほぼ同じで、置き換えコストも低くなります。実務でキューが必要なら、自作せずこれを使うべきです。

---

どちらを使うか判断する基準

迷ったら、次の質問一つで整理できます。「後から来たものを先に処理するか、先に来たものを先に処理するか？」

• 取り消し、括弧の対応確認、訪問経路の逆追跡、深さ優先探索 → 新しいものを優先 → スタック
• タスク待ち行列、イベント処理、プリンター出力、幅優先探索 → 到着順を保証 → キュー

括弧の対応確認はスタックの代表的な利用例なので、一行だけ触れておきます。開き括弧ならpush、閉じ括弧ならpopして対応を確認します。最後にスタックが空なら式は有効です。コンパイラーがコードの波括弧を検査する仕組みも同じです。

---

まとめ

• スタックはLIFO、キューはFIFO。皿の山とレジの列を思い浮かべれば、概念は終わりです。
• コールスタック・ナビゲーションスタック・undoはスタック、DispatchQueue・イベント処理・BFSはキュー。iOS開発の至る所にすでに存在します。
• SwiftにStack型がないのは、Arrayのappend/popLastがすでにO(1)のスタックだからです。
• キューを配列で作るとremoveFirst()はO(n)。コーディングテストで時間切れになる定番の原因です。
• 解決策はheadインデックス方式、二つのスタック方式、そして実務ならswift-collectionsのDequeです。
• スタックかキューかは、「新しいものを優先するか、到着順を優先するか」という一つの質問で決まります。

次の記事では、この二つの応用であるヒープ（Heap）と優先度付きキュー、そしてDictionaryの背後にあるハッシュテーブルへ続きます。