FIFO（FIFO: ファイフォ）

2025年10月21日

FIFO（FIFO: ファイフォ）

英語表記: FIFO (First-In, First-Out)

概要

FIFO（ファイフォ）とは、「先入れ先出し」を意味するデータ処理の原則です。この原則は、データ構造の中でも特に「キュー」を定義する上で最も重要な基本ルールとなっています。最初に投入されたデータが、最初に処理される（または取り出される）ことを保証する仕組みであり、公平な順番待ちを実現するために不可欠な考え方だと理解してください。

このルールによって、データ構造（リスト, スタック, キュー, ツリー）における「キュー」は、日常の行列と同じように、投入された順序を厳密に保ちながらデータを管理できるのです。

詳細解説

データ構造におけるFIFOの位置づけ

私たちが今学んでいるのは、データ構造（リスト, スタック, キュー, ツリー）の中のキューというカテゴリです。キューの最大の特徴は、データの出し入れの順序が厳密に定められている点にあります。この順序性を実現しているのが、まさにFIFO原則なのです。

FIFOは、データが挿入された時間的な順序と、データが取り出される時間的な順序が一致することを意味します。つまり、データが列の「後ろ」から入り、列の「先頭」から出ていくという、一方向の流れを確立します。これにより、データは不公平なく、投入された順番通りに処理されることが保証されます。

キューの主要な操作と動作原理

キューにおいて、FIFOを機能させるためには、データの出し入れに関する二つの主要な操作が必要です。

エンキュー（Enqueue / 挿入）:
これはデータをキューに「入れる」操作です。FIFOの原則により、新しいデータは必ずキューの末尾（リア、Rear）に追加されます。まるで、行列の最後尾に並ぶ人のようなイメージです。既存のデータに影響を与えることなく、公平に待ち列に加わります。
デキュー（Dequeue / 取り出し）:
これはキューからデータを「取り出す」操作です。FIFOの原則に従い、取り出しは必ずキューの先頭（フロント、Front）から行われます。一番長く待っていたデータ、つまり最初に入ったデータが優先的に取り出されるわけです。

この二つの操作が、それぞれ異なる端（末尾と先頭）で行われることで、データは一列に並び、途中での割り込みや、順番を無視した取り出しが発生しない仕組みになっています。この厳格な順序管理こそが、キューがデータ構造（リスト, スタック, キュー, ツリー）の中で特別な役割を持つ理由です。システムがタスクを公平に処理したり、リソースへのアクセスを順番待ちさせたりする場合に、このFIFOの仕組みが非常に役立つのです。

LIFOとの対比

FIFOを理解する上で、対義語とも言える「LIFO」（Last-In, First-Out：後入れ先出し）と比較すると、その特徴が際立ちます。LIFOはスタック（Stack）というデータ構造で採用される原則で、最後に入れたデータが最初に取り出されます。

FIFO（キュー）: 公平な行列。入った順に出る。
LIFO（スタック）: 積み重ねた皿。最後に置いた皿を最初に取る。

キューが時間の公平性を重視するのに対し、スタックは直近の操作の履歴を重視します。この違いを明確に理解することが、データ構造（リスト, スタック, キュー, ツリー）の分類をマスターする鍵となります。

具体例・活用シーン

FIFO原則は、コンピューティングの世界だけでなく、私たちの日常生活にも深く根付いた、非常に分かりやすい概念です。

1. パン屋の行列（アナログな比喩）

最も分かりやすいFIFOの比喩は、パン屋さんのレジの行列です。

行列（キュー）: パンを買いたい人が並んでいる列そのものです。
エンキュー（挿入）: お客様が列の最後尾に並ぶ行為です。
デキュー（取り出し）: レジで会計を済ませたお客様が、列の先頭から解放される行為です。

もしこの行列がFIFO（先入れ先出し）でなかったらどうなるでしょうか？後から来た人が先に会計を済ませてしまうと、待っている人は不満を感じますよね。システムも同じで、FIFO原則があるからこそ、処理の順序が保証され、公平性が保たれるのです。

2. プリンタのスプール（コンピューティングの例）

実際のITシステムでは、プリンタの印刷待ち行列（スプール）が典型的なFIFOの活用シーンです。

複数のユーザーが同時にプリンタに印刷ジョブを送信した場合、これらのジョブは印刷待ちのキューに格納されます。このキューはFIFOで管理されます。

Aさんが最初にジョブを送信
Bさんが次にジョブを送信
Cさんが最後にジョブを送信

プリンタは必ずAさんのジョブから処理を開始し、次にBさん、最後にCさんのジョブを印刷します。もしこれがLIFOだったら、後から送信したCさんのジョブが先に印刷されてしまい、待ち時間の予測ができず、システム運用が困難になってしまいます。FIFOは、共有リソース（この場合はプリンタ）へのアクセスを公平に制御するために欠かせない仕組みなのです。

3. オペレーティングシステムにおけるタスクスケジューリング

OSが複数のタスク（プログラム）を処理する際にもFIFOは使われます。特にシンプルなスケジューリング方式（FCFS: First-Come, First-Served）では、OSに実行を要求した順にタスクが処理されます。これにより、どのタスクもいつかはCPUによる処理を受けることが保証されます。

資格試験向けチェックポイント

ITパスポート試験や基本情報技術者試験、応用情報技術者試験において、FIFOはデータ構造の基礎として頻出します。特に、スタック（LIFO）との違いを問う問題は鉄板です。

| 試験レベル | 問われ方と対策 |
| :— | :— |
| ITパスポート | 定義と概念理解：「キュー」の処理方式として「FIFO」が正しいか、という基礎的な知識が問われます。日常の行列の例と結びつけて理解できていれば十分です。 |
| 基本情報技術者 | 操作のトレースとLIFOとの比較：配列や連結リストを用いたキューの具体的な操作（エンキュー、デキュー）のシミュレーション（トレース）問題が出ます。「データを入れた順序」と「取り出す順序」を正確に追う練習が必要です。また、LIFO（スタック）との違いを明確に答えられるようにしておきましょう。 |
| 応用情報技術者 | アルゴリズムと効率性：キューの実装方法（線形キュー、環状キュー）や、特定の処理におけるFIFOの計算量（時間複雑度）に関する深い理解が求められることがあります。特に、配列で実装した場合のオーバーフローや、効率的な管理（ポインタの移動）について問われることがあります。 |

試験対策のコツ：

図で覚える: キューの先頭（フロント）と末尾（リア）が、デキューとエンキューでそれぞれどう動くかを、矢印を使って図示する癖をつけましょう。
対比を明確に: FIFO（キュー）は「待ち行列」、LIFO（スタック）は「積み重ね」と、具体的なイメージで区別することが大切です。
文脈の確認: 問題文が「データ構造（リスト, スタック, キュー, ツリー）」のどの部分について聞いているのかを必ず確認し、「キューの基本」の文脈で回答するように意識しましょう。