FIFO / LIFO

computer-sciencedata-structurealgorithm

データの挿入と取り出しの順序を定める二つの基本原則。あらゆるバッファ、スケジューラ、メモリ管理の設計基盤になる。

定義

略称正式名順序対応するデータ構造
FIFOFirst In, First Out先入れ先出しキュー (Queue)
LIFOLast In, First Out後入れ先出しスタック (Stack)
graph LR
    subgraph FIFO["FIFO (Queue)"]
        direction LR
        IN1["enqueue →"] --> Q1["A"] --> Q2["B"] --> Q3["C"] --> OUT1["→ dequeue"]
    end
graph TB
    subgraph LIFO["LIFO (Stack)"]
        direction TB
        IN2["push ↓"] --> S1["C (top)"]
        S1 --> S2["B"]
        S2 --> S3["A"]
        S1 --> OUT2["↑ pop"]
    end

FIFO は「行列」。先に並んだ人が先にサービスを受ける。LIFO は「皿の積み重ね」。最後に載せた皿を最初に取る。

計算量

操作FIFO (Queue)LIFO (Stack)
挿入O(1)O(1)
取り出しO(1)O(1)
先頭/末尾の参照O(1)O(1)
任意要素の探索O(n)O(n)

どちらも挿入・取り出しは O(1)。違いは順序だけ。

実装の変種

FIFO の実装

実装特徴
リングバッファ固定長。配列ベースでキャッシュ効率が高い
連結リスト動的長。head から dequeue、tail に enqueue
VecDeque (Rust)リングバッファベースの両端キュー
std::collections::LinkedList (Rust)双方向連結リスト。通常 VecDeque を推奨

LIFO の実装

実装特徴
配列/Vec末尾に push/pop。最もシンプルで高速
連結リスト先頭に push/pop
コールスタックCPU が関数呼び出しに使うハードウェアスタック

両端キュー (Deque)

FIFO と LIFO の両方を統合した構造。両端から挿入・取り出しが可能。

graph LR
    L["← push_front / pop_front"] --- D["A | B | C | D"] --- R["push_back / pop_back →"]

使われている場所

FIFO

用途例
タスクスケジューリングOS のプロセスキュー、ジョブキュー
メッセージパッシングチャネル、メッセージキュー (RabbitMQ, SQS)
バッファリングI/O バッファ、パイプ、ネットワークパケットキュー
BFS (幅優先探索)グラフ探索でキューを使用
プリンタキュー先に送った印刷ジョブが先に印刷される

LIFO

用途例
関数呼び出しコールスタック。最後に呼んだ関数が最初に返る
Undo 操作操作履歴をスタックに積み、Undo で pop
構文解析括弧の対応、式の評価 (逆ポーランド記法)
DFS (深さ優先探索)グラフ探索でスタックを使用
メモリ管理スタック領域の確保・解放
ブラウザの戻るボタン履歴をスタックとして管理

FIFO + LIFO の組み合わせ

用途構造説明
work-stealingDequeオーナーは LIFO (キャッシュ局所性)、スティーラーは FIFO (大タスク獲得)
優先度付きキューヒープFIFO でも LIFO でもなく、優先度順。別の原則

Rust での使い分け

use std::collections::VecDeque;

// FIFO (Queue)
let mut queue = VecDeque::new();
queue.push_back(1);    // enqueue
queue.push_back(2);
queue.push_back(3);
let first = queue.pop_front();  // dequeue → Some(1)

// LIFO (Stack) — Vec で十分
let mut stack = Vec::new();
stack.push(1);         // push
stack.push(2);
stack.push(3);
let last = stack.pop();         // pop → Some(3)

// Deque (両端)
let mut deque = VecDeque::new();
deque.push_back(1);
deque.push_front(0);
deque.pop_back();      // LIFO 的
deque.pop_front();     // FIFO 的

Rust では LIFO (スタック) には Vec を使うのがイディオマティック。FIFO やデックには VecDeque。

押さえどころ（カード化候補）

関連

Graph

Backlinks