[C#] System.Collections.Queue — 非ジェネリックな FIFO キューの仕組みと使いどころ

System.Collections.Queue は、.NET Framework 1.0 から提供されている 非ジェネリックな FIFO（先入れ先出し）コレクション です。Queue<T>（.NET 2.0+）の登場で実用上は置き換えが完了していますが、System.Collections シリーズの一員として整理しておきます。

`Queue` とは

名前空間：System.Collections
内部構造：循環バッファ（リングバッファ）。object[] + head + tail + size
容量超過時は新しい配列に詰め替え（既定は growFactor = 2.0 で 2 倍に拡張）
要素の型は object、値型はボックス化

using System.Collections;

var queue = new Queue();
queue.Enqueue("first");
queue.Enqueue("second");
queue.Enqueue("third");

string s = (string)queue.Dequeue()!; // "first"
string p = (string)queue.Peek()!;    // "second"（取り出さない）

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

インターフェース	役割
`ICollection`	`Count` / `CopyTo` / 同期サポート
`IEnumerable`	`foreach` で先頭から末尾の順に列挙
`ICloneable`	`Clone()` で浅いコピー

IList は実装しません。任意位置のアクセス・挿入・削除をサポートしないコレクション だからです。これは Queue の「先頭の取り出し／末尾への追加」という純粋な FIFO セマンティクスを反映しています。

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

ICollection: ArrayList の記事
IEnumerable / IEnumerator: IEnumerable と IEnumerator の記事
ICloneable: ICloneable インターフェースの記事

Queue.Clone() は新しい配列バッファに要素参照をコピーする 浅いコピー です。

主な API と計算量

操作	API	計算量	備考
末尾追加	`Enqueue(obj)`	O(1) 償却	容量超過時のみ O(n) で再確保
先頭取り出し	`Dequeue()`	O(1)	`head` を進めるだけ
先頭参照	`Peek()`	O(1)	取り出さずに先頭を見る
含有判定	`Contains(obj)`	O(n)	線形探索
列挙	`foreach`	O(n)	先頭から順に
配列化	`ToArray()`	O(n)

Dequeue() を空のキューに対して呼ぶと InvalidOperationException。事前に Count を確認するか、空でないことを保証して呼び出します。

`TrimToSize` と容量管理

var q = new Queue(capacity: 1_000);
for (int i = 0; i < 500; i++) q.Enqueue(i);
q.TrimToSize(); // 内部配列を Count に合わせて縮小

長期間動く処理で大きく膨らんだまま縮まないキューがあるなら、定期的に TrimToSize を呼ぶか、Queue<T> の同様の API を使ってメモリ圧を下げます。

ボックス化のコスト

値型の要素を扱うと エンキュー時とデキュー時の両方 でボックス化／アンボックス化が発生します。

var q = new Queue();
for (int i = 0; i < 1_000_000; i++) q.Enqueue(i); // 100 万回ボックス化

while (q.Count > 0)
{
    int x = (int)q.Dequeue()!; // アンボックス化 + キャスト
}

Queue<int> を使えばボックス化は発生せず、ヒープ割り当てもキャストもなくなるため、現代のコードでは Queue<T> 一択 です。

`Queue<T>` との比較

観点	`Queue`	`Queue<T>`
型安全	× `object` のキャストが必要	◯
値型のボックス化	発生	発生しない
推奨度	レガシー	新規コードの標準
パフォーマンス	劣る	良い
API	ほぼ同じ（`Enqueue`/`Dequeue`/`Peek`）	同じ＋`TryDequeue`/`TryPeek`

Queue<T>.TryDequeue(out T result) のような 空判定とのアトミック化 API がジェネリック版にしかない点も実用上の差です。

並行アクセス

Queue.Synchronized(queue) でスレッドセーフラッパが取れますが、粒度が粗いため現代では System.Collections.Concurrent.ConcurrentQueue<T> の利用が標準です。プロデューサ／コンシューマパターンには BlockingCollection<T> や Channel<T> のほうが適しています。

使いどころ

Queue / Queue<T> が活きる典型的な場面を見ておきます。

幅優先探索（BFS）

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

    while (queue.Count > 0)
    {
        var node = queue.Dequeue();
        yield return node;
        foreach (var c in children(node))
        {
            if (visited.Add(c)) queue.Enqueue(c);
        }
    }
}

生産者・消費者（単一スレッド・バッチ処理）

ジョブを順次積み、順次処理する典型的なバッチパターン。

var jobs = new Queue<Job>();
foreach (var j in incoming) jobs.Enqueue(j);
while (jobs.Count > 0) Process(jobs.Dequeue());

並行性が必要なら ConcurrentQueue<T> か Channel<T> に切り替えます。

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

固定サイズの履歴を保持したいときは、上限超過時に先頭を捨てるパターン。

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

これらいずれも Queue<T> で書くのが現代的。System.Collections.Queue を選ぶ理由はレガシー互換以外にありません。

まとめ

Queue は 非ジェネリックな FIFO。内部は循環バッファで Enqueue/Dequeue/Peek が O(1)。
ICollection / IEnumerable / ICloneable を実装。IList は実装しない。
値型はボックス化されるため、新規コードでは Queue<T> 一択、並行なら ConcurrentQueue<T> か Channel<T>。
BFS、ジョブの順次処理、固定長の履歴管理が代表的な使いどころ。

Queue とは