[C#] System.Collections.Generic.Queue<T> — 型安全な FIFO キューの仕組みと使いどころ

System.Collections.Generic.Queue<T> は、型安全な FIFO（先入れ先出し）コレクション です。.NET 2.0 で非ジェネリック版 System.Collections.Queue を置き換える形で導入され、現代の C# でキューと言えば実質的にこの型を指します。

`Queue<T>` とは

名前空間：System.Collections.Generic
内部構造：循環バッファ（T[] + head + tail + size）
容量超過時は新しい配列に詰め替えて 2 倍に拡張
要素は T 型のまま格納されるためボックス化なし

var queue = new Queue<string>();
queue.Enqueue("first");
queue.Enqueue("second");

string s = queue.Dequeue(); // "first"
string p = queue.Peek();    // "second"

サポートするインターフェース

インターフェース	役割
`IEnumerable<T>`	`foreach` で先頭から末尾の順に列挙
`IReadOnlyCollection<T>`	読み取り専用の `Count`
`ICollection`	非ジェネリック版（`CopyTo` / 同期サポート）
`IEnumerable`	非ジェネリック版

非ジェネリック Queue と同様に IList<T> も ICollection<T> も実装しません。Queue<T> は「先頭の取り出しと末尾の追加」という FIFO セマンティクスに限定されているため、任意位置の追加・削除を意味する API を露出させない設計になっています。

各インターフェースの詳細は次を参照してください。

ICollection: ArrayList の記事
IEnumerable<T> / IEnumerator<T>: IEnumerable と IEnumerator の記事

主な API と計算量

操作	API	計算量
末尾追加	`Enqueue(item)`	O(1) 償却
先頭取り出し	`Dequeue()`	O(1)
先頭参照	`Peek()`	O(1)
安全な取り出し	`TryDequeue(out item)`	O(1)
安全な参照	`TryPeek(out item)`	O(1)
含有判定	`Contains(item)`	O(n)
列挙	`foreach`	O(n)
配列化	`ToArray()`	O(n)
容量縮小	`TrimExcess()`	O(n)

Dequeue / Peek は空のキューに対しては InvalidOperationException。例外を避けたいなら TryDequeue / TryPeek を使います。

while (queue.TryDequeue(out var job))
    Process(job);

容量管理

事前に要素数の見当が付くなら容量指定で再確保を防げます。

var q = new Queue<int>(capacity: 10_000);
for (int i = 0; i < 10_000; i++) q.Enqueue(i);

.NET 6+ では EnsureCapacity(n) も使えます。長期間動かしてキューが膨らんだまま縮まないなら TrimExcess() で内部配列を縮小しましょう。

非ジェネリック `Queue` との比較

観点	`Queue<T>`	`Queue`
型安全	◯	× `object`
値型のボックス化	なし	あり
`TryDequeue` / `TryPeek`	あり（.NET Core 2.0+）	なし
推奨	標準	レガシー

新規コードでは Queue<T> 一択。非ジェネリック版を使う理由は古い API 互換にしかありません。

並行版 — `ConcurrentQueue<T>` と `Channel<T>`

Queue<T> は スレッドセーフではありません。並行アクセスが必要なら次を選びます。

用途	候補
ロックフリーで読み書きしたい	`System.Collections.Concurrent.ConcurrentQueue<T>`
プロデューサ・コンシューマ間でブロッキング待ち	`System.Threading.Channels.Channel<T>`
容量制限・優先度・複数コンシューマ	`BlockingCollection<T>`、`Channel<T>`

非同期コード（async/await）では Channel<T> が現代の標準。バックプレッシャやキャンセル、容量上限の制御が API レベルで備わっています。

使いどころ

1. 幅優先探索（BFS）

Stack<T> を使った DFS と対になる古典例。

static IEnumerable<TNode> Bfs<TNode>(TNode start, Func<TNode, IEnumerable<TNode>> children)
    where TNode : notnull
{
    var visited = new HashSet<TNode>();
    var queue   = new Queue<TNode>();
    queue.Enqueue(start);
    visited.Add(start);

    while (queue.TryDequeue(out var node))
    {
        yield return node;
        foreach (var c in children(node))
            if (visited.Add(c)) queue.Enqueue(c);
    }
}

2. ジョブの順次処理

ジョブを積んで FIFO 順に処理する典型パターン。

var jobs = new Queue<Job>();
foreach (var j in incoming) jobs.Enqueue(j);
while (jobs.TryDequeue(out var job)) Process(job);

並行が必要になったら ConcurrentQueue<T> か Channel<T> に置き換えます。

3. 直近 N 件のリングバッファ

固定サイズの履歴管理。

void Push(Queue<string> log, string entry, int max)
{
    log.Enqueue(entry);
    while (log.Count > max) log.Dequeue();
}

4. レベル別 BFS

「どの距離にあるか」をレベルごとに処理したいときは、各反復で queue.Count をスナップショットして 1 レベル分だけ取り出します。

while (queue.Count > 0)
{
    int levelSize = queue.Count;
    for (int i = 0; i < levelSize; i++)
    {
        var node = queue.Dequeue();
        // 同じ距離の処理
    }
    depth++;
}

向かないケース

任意位置の参照や検索が頻繁 → List<T>
両端への追加・削除 → LinkedList<T> か Deque 的に使える List<T>
並行アクセス → ConcurrentQueue<T> / Channel<T>
容量制限・ブロッキング待ち → Channel<T> / BlockingCollection<T>

まとめ

Queue<T> は 型安全な FIFO。内部は循環バッファで Enqueue/Dequeue/Peek が O(1)。
IEnumerable<T> / IReadOnlyCollection<T> を実装。IList<T>/ICollection<T> は実装しない。
TryDequeue / TryPeek で空判定をアトミックに。
並行アクセスは ConcurrentQueue<T>、非同期プロデューサ・コンシューマは Channel<T> を選ぶ。
BFS、ジョブの順次処理、固定長履歴管理が代表的な使いどころ。

Queue<T> とは