スタックとキューの違い｜FIFO・LIFOの意味と言語別の実装・落とし穴

スタックとキューは、どちらもデータを入れて取り出すための基本的なデータ構造ですが、取り出す順番が正反対です。スタックは最後に入れた要素から取り出すLIFO（Last In, First Out：後入れ先出し）、キューは最初に入れた要素から取り出すFIFO（First In, First Out：先入れ先出し）で動きます。本記事では、この違いを早見表で押さえたうえで、FILO・LILOとの関係、会計やLinuxでの別の意味のFIFO、各言語で実装するときの落とし穴を、実際に動かした結果とあわせて解説します。メモリのスタック領域や「技術スタック」ではなく、データ構造のスタックを扱います。

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

判断の軸は1つです。直近に入れたものから処理したいならスタック、入れた順に処理したいならキューを選びます。関数呼び出し・取り消し（Undo）・括弧の対応チェック・深さ優先探索はスタック、順番待ちの処理・バッファ・幅優先探索はキューが定石です。

FIFO・LIFOとスタック・キューの対応関係

取り出し口の位置で決まる順番

順番の違いは、取り出し口がどこにあるかで決まります。スタックは入れる口と出す口が同じ端にあるため、積み重ねた皿を上から取るように、最後に置いた要素が最初に出てきます。キューは入れる口と出す口が反対の端にあるため、行列の先頭に並んだ人から順に呼ばれるように、最初に入れた要素が最初に出てきます。FIFOとLIFOはこの「取り出す順番の規則」を指す言葉で、スタックやキューはその規則を実装したデータ構造です。つまりスタック＝LIFO、キュー＝FIFOと1対1に対応します。

操作名も対になっています。スタックはpush（積む）・pop（取り出す）・peek／top（見るだけ）、キューはenqueue（末尾に加える）・dequeue（先頭を取り出す）・peek／frontが基本です。言語のライブラリでは名前が変わることが多く、Javaのキューはoffer／poll、C++のstd::queueはpush／popと、スタックと同じ名前で逆の端を操作します。

FILO＝LIFO・LILO＝FIFOの対応関係

FILO（First In, Last Out：先入れ後出し）はLIFOと、LILO（Last In, Last Out：後入れ後出し）はFIFOと同じ規則です。LIFOは「最後に入れた要素が最初に出る」、FILOは「最初に入れた要素が最後に出る」と、同じ順番を最後の要素と最初の要素のどちらに着目して言うかの違いです。検索では「queue filo」「stack fifo or lifo」のように組み合わせを確かめる人がいますが、スタックはLIFO（＝FILO）、基本のキューはFIFO（＝LILO）です。ただし名前に「キュー」が付いていても、優先度付きキューやPythonのLifoQueueのようにFIFOでない順で取り出す型もあります。文書や試験ではLIFO・FIFOの2語が使われるのが普通なので、自分で書くときもこの2語にそろえると誤読を防げます。

FIFO・LIFOが別の意味になる分野

会計・在庫管理の先入先出法と後入先出法

「FIFO LIFO」で検索すると、データ構造ではなく会計や倉庫管理の解説が並びます。在庫の評価方法としての先入先出法（FIFO）は先に仕入れた商品から払い出したとみなして原価を計算する方法、後入先出法（LIFO）は後から仕入れた商品から払い出したとみなす方法です。順番の考え方はスタック・キューと同じですが、扱うのは実物の在庫ではなく原価の計算上の流れです。

日本の会計基準では、後入先出法はすでに選べません。企業会計基準委員会（ASBJ）は2008年9月26日に企業会計基準第9号「棚卸資産の評価に関する会計基準」の改正を公表し、国際的な会計基準との整合を図るため「選択できる棚卸資産の評価方法から後入先出法を削除すること」としました。適用は2010年4月1日以後に開始する事業年度からです。税法でも、2009年度（平成21年度）の税制改正で法人税法施行令第28条の評価方法から後入先出法と単純平均法が除かれました。国際会計基準のIAS第2号も、通常相互に交換可能な棚卸資産の原価算定方式を「first-in, first-out or weighted average cost formula」としています。会計の文脈で「LIFO」を見かけたら、現行の制度の話か、米国基準などほかの制度の話かを確かめてください。

Linuxの名前付きパイプとメッセージキューのFIFO

Linuxで「FIFO」と書かれたら、多くは名前付きパイプを指します。マニュアルのfifo(7)は「A FIFO special file (a named pipe) is similar to a pipe, except that it is accessed as part of the filesystem.」と定義しており、mkfifoコマンドで作ったファイルに一方のプロセスが書き込み、別のプロセスが書いた順に読み出します。クラウドのメッセージキューにも順序を保証する「FIFOキュー」があり、Amazon SQSでは標準キューと順序・重複の扱いが異なります（詳しくはAmazon SQSの標準キューとFIFOの違いで解説しています）。どちらも「先に入ったデータが先に出る」という意味はデータ構造のキューと同じで、違うのは使われる場所です。

スタック（LIFO）の操作と使いどころ

push・pop・peekの動作と空のときの扱い

pushで要素を一番上に積み、popで一番上を取り出します。1・2・3の順にpushしてからpopを3回呼ぶと、3・2・1の順に返ります。どの操作も一番上の1か所しか触らないため、要素数に比例して時間が延びることはありません。ただし配列で実装した場合、容量が足りなくなると配列を広げ直し、実装によっては要素が減ったときに縮め直すこともあるため、計算量は平均すると定数（償却O(1)）という言い方になります。JavaのArrayDequeも公式に「amortized constant time」と書いています。実装で必ず決めておくのは空のスタックからpopしたときの扱いです。Pythonのlist.pop()はIndexError、JavaのArrayDeque.pop()はNoSuchElementExceptionを投げ、C++のstd::stack::pop()は空のときに呼ぶと未定義動作です（C++26では、堅牢化された実装なら契約違反として扱われます）。呼び出す前に空かどうかを確かめる処理を入れてください。

括弧の対応チェックで見るスタックの使いどころ

スタックが向くのは「直前に開いたものを、次に閉じる」構造です。括弧の対応はその典型で、開き括弧を積み、閉じ括弧が来たら一番上と対になっているかを確かめます。

def is_balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)          # 開き括弧を積む（push）
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:  # 直前に開いた括弧と照合（pop）
                return False
    return not stack                  # 閉じ忘れが残っていれば False

for s in ["(a[b]{c})", "(a[b)]", "((a)"]:
    print(s, is_balanced(s))

(a[b]{c}) True
(a[b)] False
((a) False

2つ目は[を閉じる前に)が来たため、3つ目は閉じ忘れの(が残ったためにFalseになります。同じ仕組みは、HTMLタグの入れ子チェックやエディタの取り消し（Undo）にも使われています。

コールスタックと再帰呼び出し

プログラムが関数を呼ぶと、戻り先や局所変数が「コールスタック」に積まれ、関数が終わると一番上から取り除かれます。後から呼んだ関数ほど先に終わるので、構造はLIFOそのものです。再帰呼び出しが深くなりすぎると積み上がった分が上限を超え、スタックオーバーフローになります。再帰とコールスタックの関係は再帰関数とは？自分を呼ぶ関数の仕組みとスタック・末尾再帰・実務判断を解説で、メモリのスタック領域とヒープ領域の違いはRustのスタックとヒープ｜値がヒープへ脱出する条件とスタックオーバーフローの防ぎ方で扱っています。

キュー（FIFO）の操作と派生データ構造

enqueue・dequeueの動作と順番待ち処理

enqueueで末尾に加え、dequeueで先頭から取り出します。1・2・3の順に入れると1・2・3の順で出るので、到着順を崩したくない処理に使います。印刷ジョブ、バックグラウンドジョブの順番待ち、ネットワーク機器の送信バッファなどが代表例です。キューの操作も先頭と末尾しか触らないため、配列の先頭を詰め直さない実装（リングバッファや連結リスト）であれば、要素数に比例して遅くなることはありません。動的配列を使う実装では、容量を広げる回を含めて平均すると定数時間（償却O(1)）です。先頭を詰め直す実装がどれほど遅くなるかは、後の言語別の章で実測します。

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

キューには用途に合わせた派生形があります。両端キュー（deque、デック）は先頭と末尾の両方で追加・取り出しができ、片側だけ使えばスタックに、反対側から出せばキューになります。Pythonのcollections.dequeやC++のstd::dequeがこれです。優先度付きキューは入れた順ではなく優先度の高い要素から取り出す構造で、内部はヒープで実装するのが一般的です。「優先度が高い」が値の小さい方か大きい方かはライブラリで違い、PythonのheapqやPriorityQueueは最小値から、C++のstd::priority_queueは既定で最大値から取り出します。リングバッファは固定長の配列の末尾と先頭をつなげて輪のように使うキューで、確保したメモリを使い回せるため、組み込み機器や音声・通信のバッファに使われます。Pythonではdeque(maxlen=N)が近い動きをし、満杯のときに追加すると反対側の古い要素が捨てられます。

取り出し口だけで変わる探索順（深さ優先と幅優先）

スタックとキューの違いがいちばんはっきり出るのがグラフの探索です。次のコードは、これから調べる頂点を入れておく箱から、どちらの端で取り出すかだけを切り替えています。訪問済みかどうかは取り出した時点で判定するので、途中で枝が合流するグラフでも正しい深さ優先・幅優先の順になります。

from collections import deque

def walk(graph, start, use_stack):
    box, seen, order = deque([start]), set(), []
    while box:
        node = box.pop() if use_stack else box.popleft()  # ここだけが違う
        if node in seen:
            continue                     # 取り出した時点で訪問済みなら飛ばす
        seen.add(node)
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                box.append(nxt)
    return order

graph = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [], "E": ["F"], "F": []}
print("スタック(pop)    :", walk(graph, "A", True))
print("キュー(popleft)  :", walk(graph, "A", False))

スタック(pop)    : ['A', 'C', 'F', 'B', 'E', 'D']
キュー(popleft)  : ['A', 'B', 'C', 'D', 'E', 'F']

スタックで取り出すと、最後に積んだCからFまで一気に潜ってからBへ戻ります。これが深さ優先探索（DFS）です。キューで取り出すと、Aから1歩のB・C、2歩のD・E・Fと、近い順に1層ずつ広がります。これが幅優先探索（BFS）で、辺に重みのないグラフでは最初に到達した経路が最短経路になります。

箱に入れる時点で訪問済みの印を付ける書き方はBFSでは正しく動きますが、スタックと組み合わせると、枝が合流するグラフ（A→B・D・C、C→B、B→E）でA・C・D・B・Eとなり、Cの先のBを後回しにしてしまいます。上のコードならA・C・B・E・Dと正しく潜ります。グラフそのものの基礎はグラフ理論とは？頂点と辺の基礎から最短経路・グラフDB・GNNの実装応用までにまとめています。

言語別のスタック・キュー実装と落とし穴

Python・Java・C++・JavaScript・C#のAPI対応表

主要な言語で、スタックとキューに使う標準の型と操作をまとめます。注意点は言語ごとに違い、PythonとJavaScriptは先頭から取り出す操作の遅さ、Javaは古いStackクラス、C++とC#は空のときの取り出しが落とし穴になります。

C#のStack<T>は公式に「last-in-first-out (LIFO) collection」、Queue<T>は「first-in, first-out collection」と説明されています。空のときにStack<T>.PopやQueue<T>.Dequeueを呼ぶとInvalidOperationExceptionになるため、取り出せたかどうかを戻り値で受け取るStack<T>.TryPop／Queue<T>.TryDequeueを使うと例外処理を書かずに済みます。

Python：list.pop(0)による全件取り出しの遅さと実測値

Pythonのlistはスタックとしてはそのまま使えますが、キューとして先頭から取り出すpop(0)は、残りの要素をすべて1つ前へずらします。collections.dequeの公式ドキュメントも、listは「incur O(n) memory movement costs for pop(0) and insert(0, v) operations」と書き、dequeは両端の追加・取り出しが「approximately the same O(1) performance」だと説明しています。n件を全部取り出すとlistでは合計O(n²)になるため、件数が増えると差が急に開きます。

2026年10月時点の最新版Python 3.15.0（macOS）で、n件入ったlistとdequeを先頭から全部取り出す時間を測りました。listやdequeを作る処理は計測から外し、timeit.repeatで取り出しのループだけを3回測った最小値です（x86_64版macOS 26.6.2上のHomebrewのPython 3.15.0。数値は実行環境で変わります）。計測コードは次のとおりです。

import timeit

for n in (10_000, 100_000, 200_000):
    t_list = min(timeit.repeat("while a: a.pop(0)", setup=f"a=list(range({n}))", number=1, repeat=3))
    t_dq = min(timeit.repeat("while d: d.popleft()",
                             setup=f"from collections import deque; d=deque(range({n}))", number=1, repeat=3))
    print(n, t_list, t_dq)

今回の計測では、10万件から20万件へ2倍にしたときlistは約4.0倍に延び、1回O(n)の操作をn回繰り返す合計O(n²)の見込みどおりでした。dequeは同じ区間で約2.9倍で、1件あたり1マイクロ秒に届きません。1万件ならlistでも約11ミリ秒で終わりますが、件数の上限が読めないキューには最初からdequeを使ってください。pop()の引数ごとの挙動はPythonのpop()の使い方：リスト・辞書・dequeの違いとpop(0)が遅い理由で詳しく解説しています。

from collections import deque

stack = []                 # スタック：末尾で出し入れ
stack.append(1); stack.append(2); stack.append(3)
print(stack.pop())         # 3

queue = deque()            # キュー：末尾に入れて先頭から出す
queue.append(1); queue.append(2); queue.append(3)
print(queue.popleft())     # 1

Python：スレッド間のqueueモジュールと優先度付きのheapq

複数のスレッドで受け渡すなら、標準ライブラリのqueueモジュールを使います。公式ドキュメントは「It is especially useful in threaded programming when information must be exchanged safely between multiple threads.」と説明しており、FIFOのQueue、LIFOのLifoQueue、値の小さい順に出すPriorityQueueなどがあります（ほかに機能を絞ったSimpleQueueもあります）。これらはスレッド間の待ち合わせやロックを内部で持つための型なので、1つのスレッドで完結する処理なら、その機能が要らないdequeで十分です。

import queue, heapq

q = queue.Queue(); s = queue.LifoQueue(); p = queue.PriorityQueue()
for x in (3, 1, 2):
    q.put(x); s.put(x); p.put(x)
print("Queue        :", [q.get() for _ in range(3)])
print("LifoQueue    :", [s.get() for _ in range(3)])
print("PriorityQueue:", [p.get() for _ in range(3)])

h = []
for pri, task in [(2, "通常"), (1, "緊急"), (3, "後回し")]:
    heapq.heappush(h, (pri, task))
print("heapq        :", [heapq.heappop(h) for _ in range(3)])

Queue        : [3, 1, 2]
LifoQueue    : [2, 1, 3]
PriorityQueue: [1, 2, 3]
heapq        : [(1, '緊急'), (2, '通常'), (3, '後回し')]

優先度付きキューを1スレッドで使うならheapqが基本です。heapqは最小ヒープなので、以前は大きい値から取り出したいときに値の符号を反転させて入れるのが定番でした。Python 3.14で最大ヒープ用のheapify_max・heappush_max・heappop_maxなどが追加されたため（公式ドキュメントに「Added in version 3.14」と明記）、3.14以降は符号の反転が要りません。Python 3.15.0で2・1・3をheappush_maxで入れてheappop_maxで取り出すと、3・2・1の順に返りました。

Java：StackクラスからArrayDequeへの置き換えとtoStringの並び

Javaには古くからあるjava.util.Stackがありますが、Java SE 27のStackのJavadocは「A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.」と、Dequeの実装を使うよう案内しています。ArrayDequeのJavadocも「likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue」としており、1つのスレッドで使うなら、スタックにもキューにもArrayDequeを選ぶのが現在の定石です。ただしStackはVectorを継承していてメソッドが同期化されているのに対し、ArrayDequeは公式に「they do not support concurrent access by multiple threads」とされています。複数スレッドから触るStackを置き換えるときは、java.util.concurrentのConcurrentLinkedDequeやLinkedBlockingDequeを選んでください。

置き換えるときに見落としやすいのが、中身を表示したときの並び順が逆になる点です。現行のJDK 27と、LTSのOpenJDK 25.0.4.1の両方で、同じ1・2・3を積んで表示しました（出力は同じです）。

import java.util.*;

public class Order {
    public static void main(String[] args) {
        Stack<Integer> legacy = new Stack<>();
        Deque<Integer> stack = new ArrayDeque<>();
        Deque<Integer> queue = new ArrayDeque<>();
        for (int x : new int[]{1, 2, 3}) {
            legacy.push(x);
            stack.push(x);
            queue.offer(x);
        }
        System.out.println("Stack     toString: " + legacy + "  pop: " + legacy.pop());
        System.out.println("ArrayDeque(push) toString: " + stack + "  pop: " + stack.pop());
        System.out.println("ArrayDeque(offer) toString: " + queue + "  poll: " + queue.poll());
    }
}

Stack     toString: [1, 2, 3]  pop: 3
ArrayDeque(push) toString: [3, 2, 1]  pop: 3
ArrayDeque(offer) toString: [1, 2, 3]  poll: 1

popで返る値はどちらも3で同じですが、StackはVectorを継承しているため底から順に、ArrayDequeは先頭（スタックの一番上）から順に並びます。ログの出力やテストの期待値を文字列で比べているコードは、置き換えると失敗します。もう1つの違いはnullで、Stackはnullを積めますが、ArrayDequeは公式に「Null elements are prohibited」とされ、push(null)でNullPointerExceptionになります。既存コードがnullを積んでいないかも確かめてください。for文で回したときの順番も同じく逆になります。

JavaScript：shift()で作るキューの速度低下と実測値

JavaScriptの配列はpush／popでそのままスタックになり、push／shiftでキューにもなります。ただしECMAScript仕様のArray.prototype.shiftは、2番目以降の要素を1つずつ前の添字へ移す手順で動作が定義されています。仕様が決めるのは結果であって速度ではないため、実際の速さはエンジン次第です。Node.js v26.5.0で、n件の配列から全件を取り出して合計する処理を2通り書き、各3回測った最小値を比べました。1つはshift()で取り出す方法、もう1つは先頭の位置を添字で持ち、値を読んだ要素をundefinedで上書きしながら添字を進める方法です（どちらも合計値が一致することを確認済み）。

測った5点では、1万件までは数ミリ秒に収まり、3万件で約0.17秒、10万件で約2.5秒、30万件で約25秒と、件数の増え方を大きく上回って延びました。どこから急に遅くなるかの境目は、この5点からは特定できません。キューに溜まる件数の上限と許容できる処理時間を先に見積もり、上限が数万件を超えうるならshiftを避けてください。先頭の添字を持つ自作キューは添字を進めるだけでは配列が縮まないため、使用済みの領域が一定量たまったら詰め直すか、固定長のリングバッファにします。長時間動かす処理なら、そこまで管理済みの両端キューのライブラリを使う方が安全です。

C++：std::dequeを包むstd::stack・std::queueのアダプタ構造

C++のstd::stackとstd::queueは、それ自体がデータを持つコンテナではなく、別のコンテナの操作を絞り込んで見せる「コンテナアダプタ」です。cppreferenceのstd::stackの宣言はtemplate< class T, class Container = std::deque<T> > class stack;で、std::queueも既定の下位コンテナはstd::dequeです。Apple clang 21（C++20）でcontainer_typeがstd::deque<int>と一致することを確かめました。スタックならstd::stack<int, std::vector<int>>のように下位コンテナを差し替えられます。pop()は値を返さないので、先にtop()（キューはfront()）で読んでから取り除く2段階になる点が、ほかの言語と違います。コンテナの種類全体はC++のコンテナクラスとは？種類一覧とvector・mapの使い分け【C++23・C++26対応】で比較しています。

スタックとキューの選び方と誤りやすいケース

選ぶ基準は「処理の順番をどう決めたいか」です。直前の状態に戻りたい、入れ子を内側から片付けたい、行けるところまで進んで戻りたい、のどれかに当てはまるならスタックです。到着順を守りたい、近いものから順に調べたい、作る側と使う側の速度差を吸収したい、のどれかならキューです。重要度で順番を変えたいときは、どちらでもなく優先度付きキューを選びます。

誤りやすいのは次の4つのケースです。

• 最短経路をスタックで探す：DFSは最初に見つけた経路が最短とは限りません。重みのないグラフの最短手数はキュー（BFS）で求めます。
• 深い再帰をそのまま書く：コールスタックの上限に当たります。標準ビルドのCPythonでは再帰の上限が既定で1000（sys.getrecursionlimit()で確認できます）なので、深さが読めない探索は自前のスタックを使ったループに書き換えます。
• 「緊急」を普通のキューに割り込ませる：FIFOのキューに途中から割り込ませる処理を書くと、順番の保証が崩れます。最初から優先度付きキューにします。
• 上限のないキューを放置する：取り出す側が止まると、キューはメモリを使い切るまで伸び続けます。Pythonのqueue.Queue(maxsize=N)のように上限を決め、満杯のときに待たせるか捨てるかを決めておきます。

業務システムでジョブの順番待ちや非同期処理の設計まで含めて相談したい場合は、フルスクラッチ開発の支援で要件の整理から対応しています。

よくある質問

スタック操作の特徴を表す用語はどれですか？

答えはLIFO（後入れ先出し）です。IPAが問題を提供し、2024年1月28日に行われた修了認定に係る試験（基本情報技術者試験に係る問題）の問5は、まさにこの文言で、選択肢は「ア FIFO　イ LIFO　ウ LILO　エ LRU」でした。FIFOとLILOは同じ規則（キュー）なので両方を消せ、LRU（Least Recently Used）はキャッシュの入れ替え方式なので外れます。

スタックとキューの覚え方はありますか？

英単語の意味から覚えるのが確実です。stack は「積み重ね」なので上に積んだ皿から取る後入れ先出し（LIFO）、queue は「順番待ちの列」なので先に並んだ人から呼ばれる先入れ先出し（FIFO）です。

キューとは待ち行列のことですか？

はい。queue の訳語が「待ち行列」で、情報処理の教科書や試験でもキューを待ち行列と呼びます。待ち時間を計算する「待ち行列理論」は同じ考え方に立ちますが、データ構造ではなく性能を見積もる理論です。

FIFOとLIFOの読み方は？

FIFOは「ファイフォ」、LIFOは「ライフォ」と読むのが一般的で、アルファベットのまま「エフアイエフオー」「エルアイエフオー」と読む人もいます。日本語では、FIFOを先入れ先出し（先入先出）、LIFOを後入れ先出し（後入先出）と書きます。

エンキュー・デキューと両端キューのdequeは同じですか？

別の言葉です。エンキュー（enqueue）はキューの末尾に要素を加える操作、デキュー（dequeue）は先頭から取り出す操作を指します。一方、deque（デック）は double-ended queue の略で、先頭と末尾の両方から出し入れできるデータ構造の名前です。Pythonの公式ドキュメントも deque の読みを「deck」と説明しています。綴りと読みが似ているため、操作の話か型の話かを文脈で見分けてください。

関連記事

• 再帰関数とは？自分を呼ぶ関数の仕組みとスタック・末尾再帰・実務判断を解説
• Pythonのpop()の使い方：リスト・辞書・dequeの違いとpop(0)が遅い理由
• グラフ理論とは？頂点と辺の基礎から最短経路・グラフDB・GNNの実装応用まで
• JavaScriptの探索アルゴリズム｜二分探索・線形探索の実装と計算量で選ぶ基準
• Amazon SQSとは？標準キューとFIFOの違い・可視性タイムアウトとDLQ設計を解説