キューのFIFO原則を解説

FIFO原則

キューは**先入れ先出し（FIFO: First In, First Out）**原則に従う抽象データ型です。最初に追加された要素が最初に取り出されます。カウンターで待つ人の列のようなものです。

コア操作

操作	説明	時間計算量
enqueue(x)	要素xを後方に追加	O(1)
dequeue()	前方の要素を削除して返す	O(1)
front()	前方の要素を削除せずに確認	O(1)
isEmpty()	キューが空か確認	O(1)

FIFOの動作

enqueue(A): [A]           <- Aが先頭
enqueue(B): [A, B]        <- Aがまだ先頭、Bが後方
enqueue(C): [A, B, C]     <- Aが先頭、Cが後方
dequeue():  [B, C]        <- Aが削除（先入れ先出し）
dequeue():  [C]           <- Bが削除

最新の要素が最初に処理されるスタックとは異なり、キューは公平性を保証します — 要素は到着順に処理されます。

実装戦略

1. 配列ベース（循環バッファ）：2つのポインタ（frontとrear）がラップアラウンド。dequeue後の要素シフトを回避。すべての操作がO(1)。
2. 連結リストベース：head（先頭）とtail（後方）ポインタを維持。enqueueはtailに追加、dequeueはheadから削除。常にO(1)。
3. 2スタック実装：2つのスタックを使用してキューをシミュレート。操作あたり償却O(1)。これはクラシックな面接問題です。

キュー vs スタック

特性	スタック	キュー
順序	LIFO	FIFO
追加	Push（トップ）	Enqueue（後方）
削除	Pop（トップ）	Dequeue（先頭）
ユースケース	再帰、元に戻す	スケジューリング、BFS

バリアント

• 双方向キュー（deque）：両端での挿入と削除を許可。
• 優先度キュー：挿入順ではなく優先度に基づいてdequeue。通常ヒープで実装。
• 循環キュー：無駄なスペースを避けるためにラップアラウンドする固定サイズキュー。