実行できるC#ドキュメント: Queue

Q: C#のQueueとは何ですか？

System.Collections.Generic の Queue は、先入れ先出し（FIFO）のコレクションです。Enqueue は末尾に要素を追加し、Dequeue は先頭の要素を削除して返し、Peek は先頭の要素を削除せずに返します。3つとも定数時間で動きます。

Q: C#で空のキューにDequeueするとどうなりますか？

空のキューに対する Dequeue と Peek は InvalidOperationException を投げます。先に queue.Count > 0 を確認するか、例外を投げずに false を返す TryDequeue(out var item) と TryPeek(out var item) を使います（.NET Core 2.0以降で使えます）。

Q: PeekとDequeueの違いは何ですか？

Peek は先頭の要素を返してキューに残すので、2回呼ぶと同じ要素が返ります。Dequeue は先頭の要素を返して削除するので、次の呼び出しではその後ろの要素が返ります。

Q: C#のQueue はスレッドセーフですか？

スレッドセーフではありません。2つのスレッドが同じ Queue に同時に Enqueue や Dequeue を呼ぶと、キューが壊れることがあります。Enqueue と TryDequeue を多数のスレッドから安全に呼べる System.Collections.Concurrent の ConcurrentQueue を使うか、通常のキューへのすべてのアクセスを lock で囲みます。

Q: ListではなくQueueを使うのはなぜですか？

List の最初の要素を RemoveAt(0) で削除すると、他のすべての要素がずれるので、リストが大きくなるほど遅くなります。Queue は先頭から定数時間で削除でき、そのAPIが「要素は到着順に処理される」という意図を表しています。

Queue<T> は窓口の行列のように動きます。最初に追加された要素が最初に取り出されます（FIFO、先入れ先出し）。Enqueue で末尾に追加し、Dequeue で先頭から取り出し、どちらも定数時間です。

Enqueue、Dequeue、Peek

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var printJobs = new Queue<string>();
        printJobs.Enqueue("invoice.pdf");
        printJobs.Enqueue("photo.png");
        printJobs.Enqueue("report.docx");

        Console.WriteLine("Waiting: " + printJobs.Count);
        Console.WriteLine("Next up: " + printJobs.Peek()); // look, do not remove

        string job = printJobs.Dequeue();                   // remove the front
        Console.WriteLine("Printing " + job);
        Console.WriteLine("Next up: " + printJobs.Peek());

        while (printJobs.Count > 0)
        {
            Console.WriteLine("Printing " + printJobs.Dequeue());
        }
        Console.WriteLine("Waiting: " + printJobs.Count);
    }
}

出力：

Waiting: 3
Next up: invoice.pdf
Printing invoice.pdf
Next up: photo.png
Printing photo.png
Printing report.docx
Waiting: 0

Peek は、次の要素を確定させる前に、それをどう扱うかを決めるためのものです。Dequeue で確定させます。空になるまで取り出す while (queue.Count > 0) ループはキューを処理する標準的な方法で、ループの本体でさらに要素を追加しても動き続けます。これは foreach ではできません。

空のキューの例外とTryDequeue

空のキューに対する Dequeue と Peek は InvalidOperationException を投げます。参照型であっても「空ならnull」という動作はありません。

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var tickets = new Queue<int>();

        try
        {
            tickets.Dequeue();
        }
        catch (InvalidOperationException e)
        {
            Console.WriteLine("Caught " + e.GetType().Name);
        }

        tickets.Enqueue(41);
        tickets.Enqueue(42);

        int ticket;
        while (tickets.TryDequeue(out ticket))
        {
            Console.WriteLine("Serving ticket " + ticket);
        }

        Console.WriteLine(tickets.TryPeek(out ticket)); // false: empty
    }
}

出力：

Caught InvalidOperationException
Serving ticket 41
Serving ticket 42
False

TryDequeue と TryPeek は、要素があれば true を返して out 変数を設定し、キューが空なら false を返します。これらは.NET Core 2.0で追加されました。古い.NET Frameworkのコードでは、Dequeue を呼ぶ前に Count > 0 を確認します。

キューの中身を見る

キューは、何も削除せずに列挙できます。foreach、ToArray、Contains はどれも、要素を先頭から末尾へと見ます。

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var line = new Queue<string>(new[] { "Ana", "Ben", "Chloe" });

        foreach (string name in line)
        {
            Console.Write(name + " ");
        }
        Console.WriteLine();

        Console.WriteLine(line.Contains("Ben"));
        string[] snapshot = line.ToArray();
        Console.WriteLine(snapshot[0] + " is first, " + snapshot.Length + " in line");
        Console.WriteLine(line.Count); // nothing was removed
    }
}

出力：

Ana Ben Chloe 
True
Ana is first, 3 in line
3

インデックスはありません。line[1] はコンパイルできず、途中の要素を削除することもできません。どちらかが必要なら、そのデータは本当はキューではありません。List<T> か LinkedList<T> を使います。他のコレクションと同じく、同じキューを foreach している最中に追加や取り出しを行うと InvalidOperationException が投げられます。

キューを使った幅優先探索

キューの順序は、まさに幅優先探索に必要なものです。1ステップ先のものをすべて訪れ、次に2ステップ先のものをすべて訪れ、というように進みます。ここでは小さなネットワークで、Anaから他の全員まで何人のつながりを隔てているかを求めます。

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var friends = new Dictionary<string, string[]>
        {
            ["Ana"] = new[] { "Ben", "Chloe" },
            ["Ben"] = new[] { "Ana", "Dev" },
            ["Chloe"] = new[] { "Ana", "Dev", "Eli" },
            ["Dev"] = new[] { "Ben", "Chloe", "Fay" },
            ["Eli"] = new[] { "Chloe" },
            ["Fay"] = new[] { "Dev" },
        };

        var distance = new Dictionary<string, int> { ["Ana"] = 0 };
        var queue = new Queue<string>();
        queue.Enqueue("Ana");

        while (queue.Count > 0)
        {
            string person = queue.Dequeue();
            foreach (string next in friends[person])
            {
                if (!distance.ContainsKey(next))
                {
                    distance[next] = distance[person] + 1;
                    queue.Enqueue(next);
                }
            }
        }

        foreach (var pair in distance)
        {
            Console.WriteLine(pair.Key + ": " + pair.Value + " step(s) from Ana");
        }
    }
}

出力：

Ana: 0 step(s) from Ana
Ben: 1 step(s) from Ana
Chloe: 1 step(s) from Ana
Dev: 2 step(s) from Ana
Eli: 2 step(s) from Ana
Fay: 3 step(s) from Ana

各人物は最初に到達したときに1回だけキューに追加され、キューは見つかった順に人物を返すので、最初に到達したときの経路が常に最短経路になります。キューをスタックに置き換えると、同じループが深さ優先探索になり、最短経路はもう見つかりません。

木のレベル順の走査、グリッドの塗りつぶし、リンクのクロールも同じ形で扱えます。キューに1つの要素を入れて始め、空でない間は1つ取り出して、その未訪問の隣接要素を追加します。

FIFOの処理でのQueueとList

Add と RemoveAt(0) で List<T> をキューとして使うこともできますが、RemoveAt(0) は残りのすべての要素を1つずつ前にずらします。10万要素のリストをこの方法で空にすると約50億回の要素の移動が起きますが、Queue<T> なら定数時間のステップが10万回で済みます。キューの内部は循環バッファーで、配列の先頭と末尾のインデックスを追跡し、いっぱいになったときだけ再確保します。

操作	`Queue<T>`	キューとして使う `List<T>`
末尾に追加	`Enqueue`、O(1)	`Add`、O(1)
先頭から削除	`Dequeue`、O(1)	`RemoveAt(0)`、O(n)
先頭を見る	`Peek`	`list[0]`
インデックスによるアクセス	不可	`list[i]`

複数のスレッドにはConcurrentQueue

Queue<T> はスレッドセーフではありません。複数のスレッドが要素を追加したり取り出したりする場合は、System.Collections.Concurrent の ConcurrentQueue<T> を使います。Enqueue、TryDequeue、TryPeek はありますが、Dequeue はありません。他のスレッドがいると、「Countを確認してからDequeue」が2つの呼び出しの間で失敗しうるからです。

using System;
using System.Collections.Concurrent;
using System.Threading.Tasks;

class Program
{
    static void Main()
    {
        var events = new ConcurrentQueue<int>();

        // 4 parallel iterations each add 1,000 items.
        Parallel.For(0, 4, worker =>
        {
            for (int i = 0; i < 1000; i++) events.Enqueue(i);
        });
        Console.WriteLine(events.Count);

        int total = 0;
        int item;
        while (events.TryDequeue(out item)) total++;
        Console.WriteLine(total + " processed");
    }
}

出力：

4000
4000 processed

ConcurrentQueue<T> の代わりに通常の Queue<T> を使うと、タイミング次第で、数が合わなくなるか、プログラムが例外を投げます。空回りせずに処理を待つべきプロデューサーとコンシューマーのスレッドには、BlockingCollection<T>（既定で ConcurrentQueue<T> をラップします）か System.Threading.Channels が待機と完了の仕組みを加えます。通常のコレクションを手動で保護する方法はlockを参照してください。

PriorityQueue

到着順ではなく優先度の順に要素を出すべき場合（最も緊急のチケットを先に、ダイクストラ法でそれまでの最短経路を先に）には、.NET 6以降の PriorityQueue<TElement, TPriority> を使います。優先度の値が最も小さいものが最初に出てきます。

var triage = new PriorityQueue<string, int>();
triage.Enqueue("sprained ankle", 3);
triage.Enqueue("chest pain", 1);
triage.Enqueue("headache", 5);

while (triage.TryDequeue(out string patient, out int priority))
{
    Console.WriteLine($"{priority}: {patient}");
}
// 1: chest pain
// 3: sprained ankle
// 5: headache

優先度が等しい要素はどんな順序で出てきてもおかしくありません。同順のときに到着順で決める必要があるなら、優先度に連番を加えます。

よくある間違い

確認せずに取り出す。 空のキューは InvalidOperationException を投げます。Count > 0 でループするか、TryDequeue を使います。
Peek を呼んで要素がなくなると思う。 削除するのは Dequeue だけです。
キューを foreach している最中に追加する。 例外が投げられます。代わりに while ループで処理します。
スレッド間で Queue<T> を共有する。 ConcurrentQueue<T> かロックを使います。
大きなデータで List.RemoveAt(0) をキューとして使う。 1回の呼び出しがO(n)です。

よくある質問

C#のQueueとは何ですか？

System.Collections.Generic の Queue<T> は、先入れ先出し（FIFO）のコレクションです。Enqueue は末尾に要素を追加し、Dequeue は先頭の要素を削除して返し、Peek は先頭の要素を削除せずに返します。3つとも定数時間で動きます。

C#で空のキューにDequeueするとどうなりますか？

空のキューに対する Dequeue と Peek は InvalidOperationException を投げます。先に queue.Count > 0 を確認するか、例外を投げずに false を返す TryDequeue(out var item) と TryPeek(out var item) を使います（.NET Core 2.0以降で使えます）。

PeekとDequeueの違いは何ですか？

Peek は先頭の要素を返してキューに残すので、2回呼ぶと同じ要素が返ります。Dequeue は先頭の要素を返して削除するので、次の呼び出しではその後ろの要素が返ります。

C#のQueue<T>はスレッドセーフですか？

スレッドセーフではありません。2つのスレッドが同じ Queue<T> に同時に Enqueue や Dequeue を呼ぶと、キューが壊れることがあります。Enqueue と TryDequeue を多数のスレッドから安全に呼べる System.Collections.Concurrent の ConcurrentQueue<T> を使うか、通常のキューへのすべてのアクセスを lock で囲みます。

ListではなくQueueを使うのはなぜですか？

List<T> の最初の要素を RemoveAt(0) で削除すると、他のすべての要素がずれるので、リストが大きくなるほど遅くなります。Queue<T> は先頭から定数時間で削除でき、そのAPIが「要素は到着順に処理される」という意図を表しています。