スタックとキュー — LIFO vs FIFO
このトピックを終えると
スタックとキューの原理を説明でき、それぞれがどこで使用されるかを理解できるようになります。
スタック — お皿の積み重ね
スタック（Stack）は、上からのみ要素を追加および削除するデータ構造です。
text
┌─────┐
push → │ 30 │ ← pop (最後に挿入されたものを最初に取り出す)
├─────┤
│ 20 │
├─────┤
│ 10 │
└─────┘レストランでお皿を積み重ねるのと同じです。最後に置いたお皿を最初に取り出します。これをLIFO（Last In, First Out） — 後入れ先出しと呼びます。
python
stack = []
# push — 上に積み重ねるstack.append(10)stack.append(20)stack.append(30)print(stack) # [10, 20, 30]
# pop — 上から取り出すtop = stack.pop()print(top) # 30 (最後に挿入されたもの)print(stack) # [10, 20]
# peek — 取り出さずに一番上を確認print(stack[-1]) # 20スタックが使用される場所
| 活用 | 説明 |
|---|---|
| 巻き戻し（Ctrl+Z） | 最後の操作からキャンセル |
| ブラウザの「戻る」ボタン | 最後に訪問したページへ |
| 関数呼び出しスタック | 最後に呼び出された関数から戻る |
| 括弧の検証 | ({[]}) のペアをチェック |
キュー — 列に並ぶ
キュー（Queue）は、最後から要素を追加し、最初から要素を取り出すデータ構造です。
text
enqueue → ┌────┬────┬────┐ → dequeue
│ 10 │ 20 │ 30 │
└────┴────┴────┘
先頭(front) 末尾(rear)コンビニのレジの列と同じです。最初に来た人が最初に会計を済ませます。これをFIFO（First In, First Out） — 先入れ先出しと呼びます。
python
from collections import deque
queue = deque()
# enqueue — 最後に挿入queue.append(10)queue.append(20)queue.append(30)print(queue) # deque([10, 20, 30])
# dequeue — 先頭から取り出すfront = queue.popleft()print(front) # 10 (最初に挿入されたもの)print(queue) # deque([20, 30])Pythonのlistでもキューを実装できますが、list.pop(0)はすべての要素を前に移動する必要があるため、処理速度が遅くなります。dequeは両端の操作がすべてO(1)です。
キューが使用される場所
| 活用 | 説明 |
|---|---|
| プリンターの待機列 | 最初に送信されたドキュメントから印刷 |
| タスクのスケジューリング | 最初に要求されたタスクから処理 |
| BFS（幅優先探索） | 近くのノードから訪問 |
| メッセージキュー | サーバー間のメッセージの順序を保証 |
スタックとキューの比較
| 特性 | スタック | キュー |
|---|---|---|
| 原則 | LIFO（後入れ先出し） | FIFO（先入れ先出し） |
| 例え | お皿の積み重ね | 列に並ぶ |
| 挿入 | push（上） | enqueue（最後） |
| 削除 | pop（上から） | dequeue（先頭から） |
| Python | list.append() + list.pop() | deque.append() + deque.popleft() |
実践的な例：括弧の検証（スタックの活用）
python
def is_valid_brackets(s): stack = [] pairs = {')': '(', ']': '[', '}': '{'}
for char in s: if char in '([{': stack.append(char) elif char in ')]}': if not stack or stack[-1] != pairs[char]: return False stack.pop()
return len(stack) == 0
print(is_valid_brackets("({[]})")) # Trueprint(is_valid_brackets("([)]")) # Falseprint(is_valid_brackets("((")) # False開く括弧が見つかると、スタックにプッシュします。閉じる括弧が見つかると、ポップしてペアが一致するかどうかを確認します。スタックのLIFOの特性は、「最も最近開いた括弧から閉じる必要がある」というルールと完全に一致します。