スタックとキューの違い｜FIFO・LIFOと使い分け・Python実装を図解

スタックとキューは、どちらもデータを一時的に「入れて」「取り出す」ための基本データ構造だが、取り出す順序が正反対になる。スタックは最後に入れた要素から取り出すLIFO（後入れ先出し）、キューは最初に入れた要素から取り出すFIFO（先入れ先出し）だ。この一点が用途を分ける。以下では両者の違いを操作・仕組み・使い分けの判断基準・Pythonでの実装まで、具体例とコードで整理する。なお「スタック」にはメモリ領域（スタック領域）や技術スタックといった別の意味もあるが、本記事はデータ構造のスタックを扱う。

まとめ：スタックとキューの違い早見表

迷ったときの判断はシンプルだ。直近に入れたものを先に処理したいならスタック、入れた順に処理したいならキューを選ぶ。再帰・取り消し（Undo）・深さ優先探索はスタック、順番待ちの処理・バッファ・幅優先探索はキューが定石になる。

スタックとキューを分ける「取り出し順」と基本操作

後入れ先出し（LIFO）と先入れ先出し（FIFO）

この順序の差は「取り出し口の位置」から生まれる。スタックは入れる口と取り出す口が同じ端にあるため、積み重ねた皿を上から取るように、最後に置いた要素が最初に出てくる。1・2・3の順に入れると3・2・1の順で出る。キューは入れる口と取り出す口が反対の端にあるため、レジの行列のように先に並んだ要素から出る。1・2・3の順に入れると1・2・3の順で出る。FIFOとLIFOはこの取り出し順を指す用語で、スタック＝LIFO、キュー＝FIFOと対応する。

操作名の対応（push・pop と enqueue・dequeue）

操作の呼び名も対になっている。スタックは要素を積むpushと、一番上を取り出すpop、先頭を見るだけのpeek（top）を持つ。キューは末尾に加えるenqueueと、先頭から取り出すdequeueを持つ。名前は違っても「追加」と「取り出し」の2操作が基本である点は共通する。

共通点と、どちらも向かない場面

両者とも、途中の要素を直接指定して取り出す用途には向かない。「3番目の要素だけ欲しい」「値で検索したい」といったランダムアクセスが必要なら、配列（インデックス参照）やハッシュ、探索木を選ぶ。スタックとキューが強いのは、処理の順序そのものに意味があるケースだ。

スタック（LIFO）の仕組みと使いどころ

push・pop・peekの動作

スタックの操作は末端（トップ）だけで完結し、追加・取り出しはいずれも定数時間で行える。要素をpushするたびにトップが上がり、popするとトップが1つ下がる。直近の状態を覚えておき、後で逆順にたどりたいときに向く。

コールスタックと再帰処理

プログラムの関数呼び出しは、内部的にスタック（コールスタック）で管理される。関数を呼ぶと戻り先やローカル変数がpushされ、関数を抜けるとpopされる。再帰関数が「一番深い呼び出しから順に戻る」のは、コールスタックがLIFOだからだ。この積み上げが深すぎると発生するのがスタックオーバーフローで、再帰の停止条件を誤ったときに起きる。再帰の具体的な組み立てはPythonでのフィボナッチ数を求める再帰関数の実装と解説で確認できる。

スタックの代表的な用途（Undo・DFS）

取り消し（Undo）機能は、操作を1つずつpushし、Ctrl+Zで直近の操作をpopして元に戻す。ブラウザの「戻る」も訪問履歴をスタックで持つ。ほかに、括弧の対応チェック、逆ポーランド記法の式評価、グラフやツリーを深く潜って探索する深さ優先探索（DFS）がスタックの典型例だ。なお「スタック」はC言語やRustなどでメモリ領域（スタック領域）を指すこともあり、データ構造とは別概念になる。メモリ側の話はRustのメモリ管理におけるスタックとヒープの基本概念を理解するで整理している。

キュー（FIFO）の仕組みと派生データ構造

enqueue・dequeueの動作

キューは末尾に加え（enqueue）、先頭から取り出す（dequeue）。列に並ぶ順番がそのまま処理順になるため、到着順・受付順を崩さずに処理したい場面に向く。先頭と末尾を別々に管理すれば、追加も取り出しも定数時間で行える。

派生キュー（両端キュー・優先度付きキュー・リングバッファ）

基本のキューには、目的に応じた派生形がある。

• 両端キュー（デキュー／deque）：先頭と末尾の両方で追加・削除ができるキュー。スタックとしてもキューとしても使え、実装のベースに使われることが多い。
• 優先度付きキュー：入れた順ではなく、優先度の高い要素から取り出すキュー。緊急タスクを先に処理する用途などで使い、内部はヒープで実装するのが一般的だ。
• リングバッファ（循環バッファ）：固定長の配列を輪のように使い回すキュー。末尾に達したら先頭へ戻るため、メモリを再確保せずに一定サイズで動く。ストリーミングやセンサーデータの一時保持など、キューバッファとして使われる。

キューの代表的な用途（順次実行・BFS）

印刷ジョブやジョブスケジューラのように「受け付けた順に処理する」仕組みはキューそのものだ。生産と消費の速度差を吸収するバッファ（データを一時的にためる緩衝）もキューで実現する。グラフやツリーを近いところから順に探索する幅優先探索（BFS）もキューを使う。DFSとBFSの位置づけはJavaScriptで学ぶ基本的なアルゴリズムの全体像と実用性で全体像をつかめる。

Pythonでのスタック・キュー実装

Pythonでは標準ライブラリだけでスタックもキューも書ける。リストでも動くが、キューの用途ではリストの先頭削除が遅くなるため、collections.dequeを使うのが定石だ。

スタックの実装（list と deque）

スタックはリストのappendとpopで素直に書ける。末尾での追加・削除はどちらも高速だ。

stack = []
stack.append("A")   # push
stack.append("B")
top = stack.pop()   # pop：最後に入れた "B" が返る
print(top)          # B

キューの実装（deque の popleft）

キューはdequeのappendとpopleftで書く。リストでpop(0)すると先頭削除に要素数ぶんの時間がかかる（O(n)）が、dequeの両端操作はいずれも定数時間（O(1)）で済む。

from collections import deque

queue = deque()
queue.append("A")   # enqueue
queue.append("B")
head = queue.popleft()  # dequeue：最初に入れた "A" が返る
print(head)             # A

優先度付きキューの実装（heapq）

優先度付きキューはheapqで実装する。タプルの先頭を優先度にすると、値の小さい順に取り出せる。挿入・取り出しはいずれもO(log n)だ。heapqは最小値を先に返すため、「大きい数ほど優先」にしたい場合は優先度を負数（-priority）にして入れる。

import heapq

pq = []
heapq.heappush(pq, (2, "通常タスク"))
heapq.heappush(pq, (1, "緊急タスク"))
first = heapq.heappop(pq)  # 優先度の小さい (1, "緊急タスク") が返る
print(first)

スレッド間で安全にやり取りしたい場合は、ロックを内蔵したqueue.Queueやqueue.PriorityQueueを使う。単一スレッドで速さを優先するならdequeとheapqで十分だ。

配列と連結リスト、どちらで実装するか

スタックとキューは「振る舞い（インターフェース）」の定義であり、内部の実装は配列でも連結リストでも作れる。どちらを選んでも、基本操作は定数時間に収められる。

配列キューを素朴に「先頭を削って詰め直す」で書くと先頭削除がO(n)になり遅い。これを避けるのがリングバッファで、先頭・末尾の位置だけを進めて配列を輪状に使い回すことでO(1)を保つ。要素数の上限が事前に読めるなら配列（リングバッファ）、読めず動的に伸ばしたいなら連結リストが無難だ。Pythonのdequeは内部でこの種の効率的な両端操作を提供しているため、多くの場合そのまま使えばよい。

使い分けの判断基準（実務での選び方）

スタックかキューかは「処理したい順序」で一意に決まる。曖昧な要件のまま選ぶと、後から順序が逆で作り直すことになる。次の基準で切り分けたい。

スタックを選ぶ判断基準

「直前の状態に戻す」「深く潜って引き返す」処理はスタックだ。Undo・Redo、ネストした構造（括弧・タグ）の対応検証、木やグラフのDFS、電卓の式評価がこれにあたる。共通点は、最後の操作を最初に取り消す・たどり直すという逆順性がある点だ。

キューを選ぶ判断基準

「受け付けた順に公平に処理する」「速度差を吸収する」処理はキューだ。ジョブの順次実行、リクエストの受付処理、ストリームの一時バッファ、BFSがこれにあたる。到着順を守ること自体が仕様になっているなら、迷わずキューでよい。

選択を誤りやすいケース

典型的な失敗は、順番待ちをスタックで作ってしまい、後から来たリクエストが先に処理される「割り込み」が発生することだ。逆に、Undoをキューで作ると古い操作から取り消されて直感に反する。また「最新のものを優先」ではなく「重要なものを優先」なら、通常のスタックやキューではなく優先度付きキューを選ぶ。順序の要件を「入れた順か・逆順か・重要度順か」で言語化してから実装に落とすと、この種の取り違えを防げる。

よくある質問（FAQ）

「スタック操作の特徴を表す用語はどれか」の答えは？

基本情報技術者試験などで問われるこの設問の答えはLIFO（後入れ先出し）だ。スタックは最後に入れたデータを最初に取り出す。対してキューはFIFO（先入れ先出し）で問われることが多い。

FIFOとLIFOの違いは何ですか？

FIFO（First In, First Out）は最初に入れた要素を最初に取り出す方式でキューが該当する。LIFO（Last In, First Out）は最後に入れた要素を最初に取り出す方式でスタックが該当する。データを入れる操作は同じでも、取り出す順序が正反対になる。

優先度付きキューとは何ですか？

入れた順ではなく、要素ごとに設定した優先度が高い（または値が小さい）ものから取り出すキューだ。緊急度の高いタスクを先に処理したい場合などに使い、内部はヒープで実装するのが一般的で、Pythonならheapqで書ける。

デキュー（deque）とは何ですか？

両端キュー（double-ended queue）の略で、先頭と末尾の両方から追加・削除できるキューを指す。スタックとしてもキューとしても使えるため実装の土台に向く。なお、キューから要素を取り出す操作「dequeue（デキュー）」と読みが同じで紛らわしいが、両端キューのdequeとは別の言葉だ。

「技術スタック」とデータ構造のスタックは同じですか？

別物だ。技術スタックは、あるシステムで使う言語・フレームワーク・ミドルウェアの組み合わせを指すビジネス／開発用語で、LIFOのデータ構造とは関係しない。同様に、メモリ管理で出てくる「スタック領域」も、関数呼び出し時に使われるメモリの区画を指す用語で、データ構造のスタックとは文脈が異なる。

関連記事

• Pythonでのフィボナッチ数を求める再帰関数の実装と解説
• JavaScriptで学ぶ基本的なアルゴリズムの全体像と実用性
• Rustのメモリ管理におけるスタックとヒープの基本概念を理解する