【C#】QueueとStackの違いと使い分け | コーディングライフスタイル

Queue<T>（FIFO: 先入れ先出し）と Stack<T>（LIFO: 後入れ先出し）は、基本アルゴリズム・状態管理・タスクスケジューリングなど多くの場面で登場するコレクションです。見た目はシンプルですが、内部はリングバッファで O(1) 操作が保証されており、List.RemoveAt(0)（O(n)）との性能差は劇的です。

本記事では内部構造から始まり、TryDequeue/TryPop・PriorityQueue（.NET 6+）・Immutable 版・ConcurrentQueue/ConcurrentStack・System.Threading.Channels・BFS / DFS / Undo-Redo の実践パターンまで体系的に解説します。

Queue と Stack の内部構造
Queue の基本操作
Stack の基本操作
Queue vs Stack 一覧比較
優先度付きキュー — PriorityQueue（.NET 6+）
不変版 — ImmutableQueue と ImmutableStack
スレッドセーフ版 — ConcurrentQueue と ConcurrentStack
非同期キュー — System.Threading.Channels
実践パターン — BFS・DFS・Undo/Redo
よくある落とし穴と対処法
よくある質問
まとめ

Queue と Stack の内部構造

両方ともジェネリックコレクションで、内部実装は配列ベースです。Queue<T> はリングバッファ（循環配列）で、head と tail のインデックスを進めて O(1) で追加・削除を行います。Stack<T> は単純な配列＋size 変数で、末尾への追加・削除を O(1) で実装しています。

操作	時間計算量	備考
`Enqueue` / `Push`	O(1)	容量超過時のリサイズで O(n)
`Dequeue` / `Pop`	O(1)
`Peek`	O(1)	空ならば InvalidOperationException
`Contains`	O(n)	線形探索（HashSet を併用するのが定石）
`Count`	O(1)	プロパティで保持
foreach	O(n)	Queue は FIFO 順、Stack はLIFO 順（上から）

容量管理と初期化

// ① デフォルト初期化
var q = new Queue<string>();
var s = new Stack<int>();

// ② 初期容量を指定（リサイズコストを抑制）
var largeQueue = new Queue<int>(capacity: 100_000);
var largeStack = new Stack<int>(capacity: 100_000);

// ③ 既存コレクションから作成
var nums = new[] { 1, 2, 3 };
var fromArray = new Queue<int>(nums);  // 先頭から enqueue された状態
var stackFrom = new Stack<int>(nums);  // 順に push → Pop は 3, 2, 1 の順

// ④ EnsureCapacity（.NET 5+）— 必要な容量を予約
var cache = new Queue<string>();
cache.EnsureCapacity(10_000);

// ⑤ TrimExcess — 余分な容量を切り詰める
cache.TrimExcess();

Queue は List.RemoveAt(0) の代わりに使う
「先頭から要素を取り出す」操作を List<T>.RemoveAt(0) で実装すると、残り全要素を1つずつ左にシフトするため O(n) になります。同じ処理を Queue.Dequeue にすればリングバッファの head を進めるだけで O(1) です。1万件規模のキュー処理ではこの差が数百倍の性能差になります。

Queue の基本操作

Queue の CRUD と安全な取り出し

var q = new Queue<string>();

// 追加（末尾へ）
q.Enqueue("A");
q.Enqueue("B");
q.Enqueue("C");

// 先頭を確認（取り出さない）
Console.WriteLine(q.Peek());    // "A"

// 先頭を取り出す（削除される）
Console.WriteLine(q.Dequeue()); // "A"
Console.WriteLine(q.Count);     // 2

// NG: 空の Queue に Dequeue / Peek → InvalidOperationException
var empty = new Queue<int>();
// empty.Dequeue(); // 例外

// OK: TryDequeue / TryPeek（.NET Core 2.0+）— 例外を使わない
if (empty.TryDequeue(out int value))
    Console.WriteLine(value);
else
    Console.WriteLine("キューは空です");

if (q.TryPeek(out string? top))
    Console.WriteLine($"次に処理するのは {top}");

// 存在確認・全削除
bool hasB = q.Contains("B"); // O(n) の線形探索
q.Clear();
Console.WriteLine(q.Count);  // 0

// foreach は FIFO 順（列挙中の変更は InvalidOperationException）
foreach (var item in new Queue<int>(new[] { 1, 2, 3 }))
    Console.Write($"{item} "); // 1 2 3

Stack の基本操作

Stack の CRUD と安全な取り出し

var s = new Stack<string>();

// 追加（末尾＝頂点へ）
s.Push("A");
s.Push("B");
s.Push("C");

// 頂点を確認（取り出さない）
Console.WriteLine(s.Peek());    // "C"

// 頂点を取り出す（削除される）
Console.WriteLine(s.Pop());     // "C"
Console.WriteLine(s.Count);     // 2

// TryPop / TryPeek（.NET Core 2.0+）
var empty = new Stack<int>();
if (!empty.TryPop(out int value))
    Console.WriteLine("スタックは空です");

// foreach は LIFO 順（頂点から底へ向かって列挙される）
var loggedStack = new Stack<string>();
loggedStack.Push("first");
loggedStack.Push("second");
loggedStack.Push("third");
foreach (var item in loggedStack)
    Console.Write($"{item} "); // third second first（Push の逆順）

// ToArray も LIFO 順（頂点が [0]）
string[] arr = loggedStack.ToArray();
Console.WriteLine(arr[0]);     // "third"

foreach の順序を取り違えると致命的なバグに
Stack<T> の foreach は Push の逆順（頂点から底）で列挙されます。「追加した順」ではありません。ログや履歴を扱うコードでこの仕様を見落とすと表示順が逆転するバグが発生します。追加順で列挙したい場合は Reverse() か ToArray().Reverse() を使うか、そもそも Queue か List を使ってください。

Queue vs Stack 一覧比較

項目	Queue<T>	Stack<T>
順序	先入れ先出し（FIFO）	後入れ先出し（LIFO）
追加	`Enqueue(item)`	`Push(item)`
取り出し	`Dequeue()`	`Pop()`
参照	`Peek()`（先頭）	`Peek()`（頂点）
空チェック付き	`TryDequeue` / `TryPeek`	`TryPop` / `TryPeek`
foreach 順序	FIFO（先頭から）	LIFO（頂点から＝Pushの逆順）
内部構造	リングバッファ	配列＋サイズ
典型用途	BFS・タスク処理・メッセージ順序	DFS・Undo/Redo・式評価・再帰の反復化

優先度付きキュー — PriorityQueue（.NET 6+）

PriorityQueue<TElement, TPriority> は .NET 6 で追加された最小ヒープ（min-heap）ベースの優先度付きキューです。「優先度が最も小さい要素」から先に取り出されます。Dijkstra 法・A* 探索・イベントスケジューラなど、優先度に従って処理する場面で活躍します。

PriorityQueue の基本

// 要素＋優先度のペアを持つ
var pq = new PriorityQueue<string, int>();

pq.Enqueue("通常タスク",     priority: 5);
pq.Enqueue("緊急タスク",     priority: 1);  // 優先度が小さいほど先に出る
pq.Enqueue("バックグラウンド", priority: 10);

while (pq.Count > 0)
{
    var task = pq.Dequeue();
    Console.WriteLine(task);
}
// 緊急タスク → 通常タスク → バックグラウンド の順で取り出される

// TryDequeue: 要素と優先度を同時に取得
if (pq.TryDequeue(out string? element, out int priority))
    Console.WriteLine($"{element} (優先度 {priority})");

// EnqueueRange: 複数要素を一括追加
var tasks = new[]
{
    ("A", 3), ("B", 1), ("C", 2)
};
pq.EnqueueRange(tasks); // タプル (要素, 優先度) の列挙を受け付ける

カスタム比較器で最大ヒープ・複合優先度

// デフォルトは小さい方が高優先度（最小ヒープ）
// 最大ヒープにするには比較器を反転する
var maxHeap = new PriorityQueue<string, int>(
    Comparer<int>.Create((a, b) => b.CompareTo(a)));

maxHeap.Enqueue("A", 1);
maxHeap.Enqueue("B", 5);
maxHeap.Enqueue("C", 3);
Console.WriteLine(maxHeap.Dequeue()); // "B"（優先度 5 が先に出る）

// 複合優先度: レコード型を優先度として使う
public sealed record class TaskPriority(int Urgency, DateTime EnqueuedAt)
    : IComparable<TaskPriority>
{
    public int CompareTo(TaskPriority? other) =>
        other is null ? 1 :
        Urgency != other.Urgency
            ? Urgency.CompareTo(other.Urgency)
            : EnqueuedAt.CompareTo(other.EnqueuedAt); // 同優先度なら先着順
}

var jobs = new PriorityQueue<string, TaskPriority>();
jobs.Enqueue("job1", new TaskPriority(1, DateTime.UtcNow));

PriorityQueue は同一優先度の順序を保証しない
最小ヒープ実装のため、同じ優先度の要素の取り出し順は未規定です。「優先度が同じなら先着順」など FIFO 的な動作が必要な場合は、優先度型に「追加時のシーケンス番号（単調増加カウンタ）」かDateTime/long Stopwatch.GetTimestamp() を組み合わせた複合優先度を使ってください。

不変版 — ImmutableQueue と ImmutableStack

ImmutableQueue / ImmutableStack（System.Collections.Immutable）

using System.Collections.Immutable;

// ImmutableStack: Push/Pop は新しいインスタンスを返す
ImmutableStack<int> s0 = ImmutableStack<int>.Empty;
ImmutableStack<int> s1 = s0.Push(1);
ImmutableStack<int> s2 = s1.Push(2);

// Pop は「新しいスタック」を返す。取り出した値は out パラメータ or Peek で取得
ImmutableStack<int> s3 = s2.Pop(out int top);
Console.WriteLine(top);           // 2
Console.WriteLine(s3.Peek());     // 1
Console.WriteLine(s2.Peek());     // 2（元は変わらない）

// ImmutableQueue: Enqueue/Dequeue も同様
ImmutableQueue<string> q0 = ImmutableQueue<string>.Empty;
ImmutableQueue<string> q1 = q0.Enqueue("A").Enqueue("B").Enqueue("C");
ImmutableQueue<string> q2 = q1.Dequeue(out string first);
Console.WriteLine(first);         // "A"
Console.WriteLine(q2.Peek());     // "B"

// 用途: 関数型スタイルの状態遷移・履歴保存・Undo/Redo で過去状態を共有
// 可変版に比べて差分だけをコピーする（構造共有）ので完全コピーより安価

スレッドセーフ版 — ConcurrentQueue と ConcurrentStack

ConcurrentQueue / ConcurrentStack

using System.Collections.Concurrent;

// 複数スレッドから同時に Enqueue / Dequeue できるロックフリー実装
var cq = new ConcurrentQueue<string>();

Parallel.For(0, 100, i => cq.Enqueue($"item{i}"));

// 取り出しは Try 系のみ（空チェック付き）
while (cq.TryDequeue(out string? item))
    Console.WriteLine(item);

// TryPeek
if (cq.TryPeek(out string? nextItem))
    Console.WriteLine($"次は {nextItem}");

// ConcurrentStack も同様
var cs2 = new ConcurrentStack<int>();
cs2.Push(1);
cs2.Push(2);

// PushRange / TryPopRange: 複数要素をアトミックに操作
cs2.PushRange(new[] { 3, 4, 5 });
var buffer = new int[3];
int popped = cs2.TryPopRange(buffer); // popped 件を buffer に取り出す

// Count は内部スナップショットを走査するため O(n)
// 「空かどうか」は IsEmpty プロパティを使う（O(1)）
if (!cq.IsEmpty) Console.WriteLine("まだ処理が残っている");

Concurrent 系の Count と foreach はスナップショット
ConcurrentQueue.Count は内部構造を走査するため O(n) で、頻繁にチェックするとパフォーマンスが劣化します。空判定は IsEmpty（O(1)）を使ってください。また foreach はある時点のスナップショットを列挙するため、列挙中に他スレッドが Enqueue した要素は見えない場合があります。「常に最新を走査」したい場合は TryDequeue をループする方が適切です。

非同期キュー — System.Threading.Channels

複数の非同期プロデューサ・コンシューマ間で値を受け渡したい場合、ConcurrentQueue + スピン待機よりも Channel<T>（.NET Core 3.0+）がモダンな選択肢です。バックプレッシャー（容量上限でブロック）・複数リーダー/ライター・完了通知を組み込みでサポートします。

Channel を使った非同期プロデューサ-コンシューマ

using System.Threading.Channels;

// バウンド付き（容量10）— 満杯のときは WriteAsync が待機する
var channel = Channel.CreateBounded<int>(new BoundedChannelOptions(10)
{
    SingleReader = false,
    SingleWriter = false,
    FullMode     = BoundedChannelFullMode.Wait, // 満杯時は書き手を待たせる
});

// プロデューサ
Task producer = Task.Run(async () =>
{
    for (int i = 0; i < 100; i++)
        await channel.Writer.WriteAsync(i);
    channel.Writer.Complete(); // これ以上書かない合図
});

// コンシューマ（複数走らせてもよい）
Task consumer = Task.Run(async () =>
{
    await foreach (int item in channel.Reader.ReadAllAsync())
        Console.WriteLine($"処理: {item}");
});

await Task.WhenAll(producer, consumer);

// Unbounded: 上限なし（メモリ圧迫のリスクあり）
var unbounded = Channel.CreateUnbounded<string>();

ConcurrentQueue と Channel の使い分け
シンプルな共有キューで非同期通知が不要なら ConcurrentQueue。プロデューサ・コンシューマが非同期でバックプレッシャーや完了通知を扱うなら Channel が最適です。Channel は ReadAllAsync を使えば await で読み続けられ、完了時のループ終了も自動化されます。ASP.NET Core のバックグラウンドタスク・バッチ処理・ストリーミング処理の標準パターンです。

実践パターン — BFS・DFS・Undo/Redo

パターン① — Queue で幅優先探索（BFS）

// グラフの最短経路・迷路探索・レベル順走査
public static int BfsShortestPath(
    Dictionary<string, List<string>> graph,
    string start,
    string goal)
{
    var visited  = new HashSet<string> { start };
    var queue    = new Queue<(string Node, int Depth)>();
    queue.Enqueue((start, 0));

    while (queue.TryDequeue(out var current))
    {
        if (current.Node == goal) return current.Depth;

        foreach (var next in graph[current.Node])
        {
            if (visited.Add(next))
                queue.Enqueue((next, current.Depth + 1));
        }
    }
    return -1; // 到達不可
}

パターン② — Stack で深さ優先探索（DFS）・括弧対応

// 括弧の対応チェック: "({[]})" → true, "(]" → false
public static bool IsBalanced(string input)
{
    var stack = new Stack<char>();
    var pairs = new Dictionary<char, char>
    {
        [')'] = '(', [']'] = '[', ['}'] = '{'
    };

    foreach (char c in input)
    {
        if (c is '(' or '[' or '{')
            stack.Push(c);
        else if (pairs.ContainsKey(c))
        {
            if (!stack.TryPop(out char open) || open != pairs[c])
                return false;
        }
    }
    return stack.Count == 0;
}

// 再帰を Stack で反復化（スタックオーバーフロー回避）
public static void IterativeDfs(TreeNode root)
{
    var stack = new Stack<TreeNode>();
    stack.Push(root);

    while (stack.TryPop(out var node))
    {
        Process(node);
        if (node.Right is not null) stack.Push(node.Right);
        if (node.Left  is not null) stack.Push(node.Left);
    }
}

パターン③ — 2つの Stack で Undo/Redo

public sealed class UndoRedoHistory<TState>
{
    private readonly Stack<TState> _undo = new();
    private readonly Stack<TState> _redo = new();

    public TState Current { get; private set; }

    public UndoRedoHistory(TState initial) => Current = initial;

    public void Do(TState newState)
    {
        _undo.Push(Current);
        Current = newState;
        _redo.Clear(); // 新しい操作で Redo 履歴は破棄
    }

    public bool Undo()
    {
        if (!_undo.TryPop(out var prev)) return false;
        _redo.Push(Current);
        Current = prev;
        return true;
    }

    public bool Redo()
    {
        if (!_redo.TryPop(out var next)) return false;
        _undo.Push(Current);
        Current = next;
        return true;
    }
}

// 使用例
var history = new UndoRedoHistory<string>("初期状態");
history.Do("編集1");
history.Do("編集2");
history.Undo();            // 編集1 に戻る
Console.WriteLine(history.Current); // "編集1"
history.Redo();            // 編集2 に進む

パターン④ — PriorityQueue で Dijkstra 法

// 最短経路探索: ノード間の最短コストを求める
public static Dictionary<string, int> Dijkstra(
    Dictionary<string, List<(string To, int Cost)>> graph,
    string start)
{
    var distances = graph.Keys.ToDictionary(k => k, _ => int.MaxValue);
    distances[start] = 0;

    var pq = new PriorityQueue<string, int>();
    pq.Enqueue(start, 0);

    while (pq.TryDequeue(out string? node, out int dist))
    {
        if (dist > distances[node]) continue; // より良い経路が既に確定

        foreach (var (neighbor, cost) in graph[node])
        {
            int newDist = dist + cost;
            if (newDist < distances[neighbor])
            {
                distances[neighbor] = newDist;
                pq.Enqueue(neighbor, newDist);
            }
        }
    }
    return distances;
}

よくある落とし穴と対処法

落とし穴① — List の先頭削除で O(n)

// NG: List.RemoveAt(0) は毎回 O(n)（残り要素を左にシフト）
var list = Enumerable.Range(1, 100_000).ToList();
while (list.Count > 0)
    list.RemoveAt(0); // 合計 O(n²) — 10万件で約 10^10 回の操作

// OK: Queue なら Dequeue が O(1) で合計 O(n)
var queue = new Queue<int>(Enumerable.Range(1, 100_000));
while (queue.Count > 0)
    queue.Dequeue(); // 合計 O(n) — 10万件で 10^5 回

落とし穴② — 空の Dequeue / Pop で例外

var q = new Queue<int>();

// NG: 空なら InvalidOperationException
// int x = q.Dequeue(); // 例外

// OK: TryDequeue で安全に
if (q.TryDequeue(out int value))
    Console.WriteLine(value);
else
    Console.WriteLine("キューは空");

// 冗長: Count チェック＋Dequeue は 2 回のプロパティアクセスになる
// while (q.Count > 0) { q.Dequeue(); }

// 推奨: TryDequeue 1 回でループを回すのが簡潔（ConcurrentQueue でも同じイディオム）
while (q.TryDequeue(out var item)) Process(item);

落とし穴③ — Stack の foreach は Push の逆順

var s = new Stack<string>();
s.Push("第1章");
s.Push("第2章");
s.Push("第3章");

// 期待: 第1章 → 第2章 → 第3章
// 実際: 第3章 → 第2章 → 第1章（LIFO 順）
foreach (var chapter in s)
    Console.WriteLine(chapter);

// 追加順で列挙したい場合
foreach (var chapter in s.Reverse())
    Console.WriteLine(chapter); // 第1章 → 第2章 → 第3章

落とし穴④ — 列挙中の変更は例外

var q = new Queue<int>(new[] { 1, 2, 3 });

// NG: foreach 中に Enqueue → InvalidOperationException
// foreach (var x in q) q.Enqueue(x * 10);

// OK: スナップショットに対してループする
var snapshot = q.ToArray();
foreach (var x in snapshot) q.Enqueue(x * 10);

// OK: 取り出しながら処理する（取り出し＋処理を分離するパターン）
while (q.TryDequeue(out int x))
{
    if (x < 100) q.Enqueue(x * 10); // 取り出し終わった項目の派生を追加
}

よくある質問

QQueue と List.RemoveAt(0) のどちらを使えばよいですか？

A「先頭から取り出して処理する」パターンでは必ず Queue を使ってください。List.RemoveAt(0) は残りの要素をすべて左にシフトするため O(n) で、1万件以上になると体感できるほど遅くなります。Queue はリングバッファで O(1) です。処理後に順序を保ったコピーが必要な場合は queue.ToArray() で配列化できます。

QPriorityQueue に対してランダムアクセスや要素の優先度更新はできますか？

A標準 PriorityQueue<TElement, TPriority> には「特定要素の優先度を変更する」メソッドがありません。Dijkstra 法の「訪問済みチェックで古いエントリを無視する」パターンが標準的な回避策です（本記事のサンプル参照）。本格的な優先度更新が必要な場面ではフィボナッチヒープや Indexed Priority Queue を自前実装するか、サードパーティ（C5 等）のライブラリを検討します。

QConcurrentQueue.Count が O(n) なのはなぜですか？

AConcurrentQueue は内部でロックフリーなセグメントのリンクドリストを使っており、正確な件数を返すには全セグメントを走査する必要があります。ロック取得を避ける代わりに Count の取得コストが上がる設計です。空判定だけなら IsEmpty（O(1)）、件数の概算で十分なら別途 Interlocked.Increment のカウンタを併用してください。

QStack の Pop と Peek の使い分けは？

A削除を伴うかどうかが違いです。Pop は頂点を取り出して返し、スタックから削除します。Peek は頂点を返すだけで削除しません。分岐処理で「頂点だけ見て判断し、条件を満たしたら取り出す」パターンでは Peek → 条件確認 → Pop の流れにします。コンパイラの式評価スタック・括弧対応チェックでよく使われるパターンです。

QQueue と Channel はどう使い分けますか？

A「同期的な共有キュー」なら Queue（単一スレッド）か ConcurrentQueue（複数スレッド）、「非同期プロデューサ・コンシューマ」なら Channel<T> です。Channel は await channel.Writer.WriteAsync で容量満杯時の自動待機、ReadAllAsync で await foreach での完了ベース消費ができます。ASP.NET Core のバックグラウンドサービス・バッチパイプラインでは Channel が現代の標準です。

まとめ

場面	選ぶべきコレクション	理由
単一スレッドの FIFO 処理	`Queue<T>`	リングバッファで Enqueue/Dequeue は O(1)
単一スレッドの LIFO 処理	`Stack<T>`	配列末尾操作で Push/Pop は O(1)
優先度順の処理	`PriorityQueue`（.NET 6+）	最小ヒープで Enqueue/Dequeue は O(log n)
複数スレッドの共有キュー	`ConcurrentQueue/Stack`	ロックフリー実装。空判定は IsEmpty を使う
非同期プロデューサ・コンシューマ	`Channel<T>`	バックプレッシャー・完了通知を組み込みで提供
不変スナップショット共有	`ImmutableQueue/Stack`	操作ごとに新インスタンス。関数型スタイル
BFS（幅優先探索）	`Queue`	レベル順走査で最短経路が取れる
DFS・Undo/Redo・括弧対応	`Stack`	LIFO で後から追加した状態が先に戻る
List の先頭から取り出し	Queue に置き換える	RemoveAt(0) の O(n²) 問題を回避

関連する他コレクションの選び方は配列と List 完全ガイド、重複排除とメンバーシップ判定はHashSet 完全ガイド、キー＋値のルックアップはDictionary 完全ガイド、非同期処理の基本はasync/await 完全ガイドを参照してください。