スタックとキュー：LIFOとFIFO

配列や連結リストは、どこからでも自由にデータを読み書きできる万能な構造でした。しかし、あえて「入れ方と取り出し方」に厳しいルールを課すことで、特定の処理を驚くほどシンプルにこなせるデータ構造があります。「スタック」と「キュー」です。それぞれの動作ルールと応用例を見ていきましょう。

1. スタック（Stack）：後入れ先出し（LIFO）

スタック（Stack）は、データを縦に積み重ねるように配置していくデータ構造です。

机の上に本を高く積み上げる様子や、狭い筒の中にボールを落とし込んでいく様子を想像してください。本を積むときは一番上に置きますし、本を取るときも一番上（最後に置いたもの）から取るしかありません。

このルールを「後入れ先出し」、英語で LIFO（Last-In First-Out）と呼びます。

図 5-3：スタックのプッシュ（挿入）とポップ（取り出し）

スタックに対する基本操作は以下の2つだけです。

スタックは、テキストエディタの「元に戻す（Undo）」機能に使われています。文字を入力するたびに操作履歴がスタックにプッシュされ、Ctrl+Z（Undo）を押すと最新の操作がポップされて一つ前の状態に戻ります。

ブラウザの「戻る」ボタンも、訪問ページのURL履歴をスタックで管理することで実現しています。

キュー（Queue）は、データの追加を「後ろ」から行い、取り出しを「先頭」から行うデータ構造です。

人気店のレジに並ぶ「行列」を想像してください。新しく来た人は一番後ろに並び、先に並んでいた人から順に対応されます。割り込みは禁止です。

このルールを「先入れ先出し」、英語で FIFO（First-In First-Out）と呼びます。

図 5-4：キューのエンキュー（追加）とデキュー（取り出し）

キューに対する基本操作は以下の2つだけです。

キューは、処理を公平に順番通り実行したいときに多用されます。例えば、オフィスのプリンタに複数のPCから一斉に印刷指示が出たとき、プリンタは届いた順にタスクをキューへエンキューし、先頭から順番にデキューして印刷を実行します。

Webサーバーが大量のアクセスを受けた際も、処理が追いつかなくなるのを防ぐため、リクエストを一時的にキュー（待ち行列）へ溜めて順次処理します。

項目	スタック（Stack）	キュー（Queue）
別名・動作モデル	LIFO（Last-In First-Out / 後入れ先出し）	FIFO（First-In First-Out / 先入れ先出し）
挿入操作	プッシュ（一番上に追加）	エンキュー（一番後ろに追加）
取り出し操作	ポップ（一番上から取り出す）	デキュー（一番前から取り出す）
身近な比喩	本の山、筒の中のボール	レジの行列、電車の乗降列
代表的な用途	関数の実行（コールスタック）、履歴（Undo）	印刷処理、イベント処理、アクセス順次待ち

整理のポイント：データ構造の操作と応用

データ構造の基本的な性質と、それぞれで使われる操作名を正しく整理しておきましょう。

スタック（LIFO / 後入れ先出し）：
- 操作名：プッシュ（Push） / ポップ（Pop）
- 応用例：再帰呼び出しの管理、数式の構文解析、深さ優先探索（DFS）
キュー（FIFO / 先入れ先出し）：
- 操作名：エンキュー（Enqueue） / デキュー（Dequeue）
- 応用例：プリンタの印刷待ち、通信パケットのバッファ、幅優先探索（BFS）

データ構造の基礎知識では「スタックに A, B, C の順でデータをプッシュしたとき、ポップされる順序はどうなるか（答え：C, B, A）」といった、取り出しのルールを順番通りになぞるトレースがよく用いられます。

次のセクションでは、アルゴリズムの効率を評価する最大の基準「計算量（O記法）」と、それを活かして超高速にデータを検索する「二分探索」について学びます。