Ausführbare C#-Docs: Queue

Q: Was ist eine Queue in C#?

Queue in System.Collections.Generic ist eine Collection nach dem Prinzip first in, first out (FIFO). Enqueue fügt hinten ein Element an, Dequeue entfernt das vordere Element und gibt es zurück, und Peek gibt das vordere Element zurück, ohne es zu entfernen. Alle drei brauchen konstante Zeit.

Q: Was passiert in C# bei Dequeue auf einer leeren Queue?

Dequeue und Peek werfen auf einer leeren Queue InvalidOperationException. Prüfe vorher queue.Count > 0 oder nimm TryDequeue(out var item) und TryPeek(out var item), die stattdessen false zurückgeben (verfügbar seit .NET Core 2.0).

Q: Was ist der Unterschied zwischen Peek und Dequeue?

Peek gibt das vordere Element zurück und lässt es in der Queue, zwei Aufrufe liefern also dasselbe Element. Dequeue gibt das vordere Element zurück und entfernt es, der nächste Aufruf liefert also das Element dahinter.

Q: Ist Queue in C# threadsicher?

Nein. Rufen zwei Threads gleichzeitig Enqueue oder Dequeue auf derselben Queue auf, kann sie beschädigt werden. Nimm ConcurrentQueue aus System.Collections.Concurrent, dessen Enqueue und TryDequeue sich sicher aus vielen Threads aufrufen lassen, oder umschließe jeden Zugriff auf eine normale Queue mit einem lock.

Q: Warum eine Queue statt einer List verwenden?

Das erste Element einer List mit RemoveAt(0) zu entfernen verschiebt jedes andere Element, das wird mit wachsender Liste also langsamer. Eine Queue entfernt vorn in konstanter Zeit, und ihre API drückt die Absicht aus: Elemente werden in der Reihenfolge ihres Eintreffens verarbeitet.

Eine Queue<T> funktioniert wie eine Warteschlange an einem Schalter: Das zuerst hinzugefügte Element wird als erstes herausgenommen (FIFO, first in, first out). Du fügst hinten mit Enqueue hinzu und nimmst vorn mit Dequeue heraus, beides in konstanter Zeit.

Enqueue, Dequeue und 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);
    }
}

Ausgabe:

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

Peek dient dazu, zu entscheiden, was mit dem nächsten Element passieren soll, bevor du dich festlegst; Dequeue legt sich fest. Die Schleife while (queue.Count > 0), die bis zur leeren Queue herausnimmt, ist der Standardweg, eine Queue abzuarbeiten, und sie funktioniert weiter, wenn der Schleifenrumpf neue Elemente einreiht, was ein foreach nicht erlaubt.

Die Exception bei leerer Queue und TryDequeue

Dequeue und Peek werfen auf einer leeren Queue InvalidOperationException. Ein Verhalten „null, wenn leer“ gibt es nicht, auch nicht für Referenztypen.

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
    }
}

Ausgabe:

Caught InvalidOperationException
Serving ticket 41
Serving ticket 42
False

TryDequeue und TryPeek geben true zurück und setzen die out-Variable, wenn ein Element da ist, und geben false zurück, wenn die Queue leer ist. Sie kamen mit .NET Core 2.0; in älterem Code für .NET Framework prüfe Count > 0, bevor du Dequeue aufrufst.

In eine Queue hineinschauen

Eine Queue lässt sich durchlaufen, ohne etwas zu entfernen. foreach, ToArray und Contains sehen alle die Elemente von vorn nach hinten.

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
    }
}

Ausgabe:

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

Es gibt keinen Index: line[1] kompiliert nicht, und du kannst kein Element aus der Mitte entfernen. Wenn du eines davon brauchst, sind die Daten eigentlich keine Queue; nimm eine List<T> oder eine LinkedList<T>. Wie bei anderen Collections wirft Einreihen oder Herausnehmen in einem foreach über dieselbe Queue InvalidOperationException.

Breitensuche mit einer Queue

Die Reihenfolge der Queue ist genau das, was die Breitensuche braucht: alles einen Schritt entfernt besuchen, dann alles zwei Schritte entfernt und so weiter. Hier findet sie heraus, wie viele Verbindungen Ana in einem kleinen Netzwerk von allen anderen trennen:

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");
        }
    }
}

Ausgabe:

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

Jede Person wird einmal eingereiht, beim ersten Erreichen, und weil die Queue sie in der Reihenfolge zurückgibt, in der sie gefunden wurden, liegt das erste Erreichen immer auf einem kürzesten Weg. Ersetze die Queue durch einen Stack, und dieselbe Schleife wird zur Tiefensuche, die keine kürzesten Wege mehr findet.

Dieselbe Form erledigt die Durchquerung eines Baums Ebene für Ebene, Flood Fill auf einem Raster und das Crawlen von Links: Beginne mit einem Element in der Queue, und solange sie nicht leer ist, nimm eines heraus und reihe seine nicht besuchten Nachbarn ein.

Queue gegenüber List für FIFO-Arbeit

Du kannst eine List<T> mit Add und RemoveAt(0) als Queue verwenden, aber RemoveAt(0) verschiebt jedes verbleibende Element um einen Platz nach vorn. Eine Liste mit 100.000 Elementen auf diese Weise zu leeren kostet etwa fünf Milliarden Elementverschiebungen; eine Queue<T> braucht 100.000 Schritte in konstanter Zeit. Intern ist eine Queue ein Ringpuffer: Sie führt einen Kopf- und einen Endindex in ein Array und allokiert nur neu, wenn es voll ist.

Operation	`Queue<T>`	`List<T>` als Queue
Hinten hinzufügen	`Enqueue`, O(1)	`Add`, O(1)
Vorn entfernen	`Dequeue`, O(1)	`RemoveAt(0)`, O(n)
Vorderes Element ansehen	`Peek`	`list[0]`
Indexzugriff	Nicht verfügbar	`list[i]`

ConcurrentQueue für mehrere Threads

Queue<T> ist nicht threadsicher. Wenn mehrere Threads Elemente hinzufügen oder herausnehmen, nimm ConcurrentQueue<T> aus System.Collections.Concurrent. Sie hat Enqueue, TryDequeue und TryPeek, aber kein Dequeue, weil mit anderen Threads im Spiel „Count prüfen, dann Dequeue“ zwischen den beiden Aufrufen scheitern könnte.

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");
    }
}

Ausgabe:

4000
4000 processed

Mit einer normalen Queue<T> statt ConcurrentQueue<T> wäre die Anzahl je nach Timing falsch, oder das Programm würde werfen. Für Producer- und Consumer-Threads, die auf Arbeit warten sollen, statt aktiv zu kreisen, fügen BlockingCollection<T> (das standardmäßig eine ConcurrentQueue<T> kapselt) oder System.Threading.Channels Blockieren und Abschluss hinzu. Wie du eine normale Collection von Hand schützt, steht unter lock.

PriorityQueue

Wenn Elemente nach Priorität statt nach Ankunftsreihenfolge herauskommen sollen (das dringendste Ticket zuerst, der bisher kürzeste Weg im Dijkstra-Algorithmus), bieten .NET 6 und neuer PriorityQueue<TElement, TPriority>. Der niedrigste Prioritätswert kommt zuerst heraus:

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

Elemente mit gleicher Priorität können in beliebiger Reihenfolge herauskommen; füge der Priorität eine laufende Nummer hinzu, wenn die Ankunftsreihenfolge bei Gleichstand entscheiden muss.

Häufige Fehler

Herausnehmen ohne Prüfung. Eine leere Queue wirft InvalidOperationException; lass die Schleife mit Count > 0 laufen oder nimm TryDequeue.
Peek aufrufen und erwarten, dass das Element weg ist. Nur Dequeue entfernt.
In foreach über die Queue einreihen. Wirft; arbeite stattdessen mit einer while-Schleife.
Eine Queue<T> zwischen Threads teilen. Nimm ConcurrentQueue<T> oder einen Lock.
List.RemoveAt(0) als Queue bei großen Datenmengen verwenden. Jeder Aufruf ist O(n).

Häufig gestellte Fragen

Was ist eine Queue in C#?

Queue<T> in System.Collections.Generic ist eine Collection nach dem Prinzip first in, first out (FIFO). Enqueue fügt hinten ein Element an, Dequeue entfernt das vordere Element und gibt es zurück, und Peek gibt das vordere Element zurück, ohne es zu entfernen. Alle drei brauchen konstante Zeit.

Was passiert in C# bei Dequeue auf einer leeren Queue?

Dequeue und Peek werfen auf einer leeren Queue InvalidOperationException. Prüfe vorher queue.Count > 0 oder nimm TryDequeue(out var item) und TryPeek(out var item), die stattdessen false zurückgeben (verfügbar seit .NET Core 2.0).

Was ist der Unterschied zwischen Peek und Dequeue?

Peek gibt das vordere Element zurück und lässt es in der Queue, zwei Aufrufe liefern also dasselbe Element. Dequeue gibt das vordere Element zurück und entfernt es, der nächste Aufruf liefert also das Element dahinter.

Ist Queue<T> in C# threadsicher?

Nein. Rufen zwei Threads gleichzeitig Enqueue oder Dequeue auf derselben Queue<T> auf, kann sie beschädigt werden. Nimm ConcurrentQueue<T> aus System.Collections.Concurrent, dessen Enqueue und TryDequeue sich sicher aus vielen Threads aufrufen lassen, oder umschließe jeden Zugriff auf eine normale Queue mit einem lock.

Warum eine Queue statt einer List verwenden?

Das erste Element einer List<T> mit RemoveAt(0) zu entfernen verschiebt jedes andere Element, das wird mit wachsender Liste also langsamer. Eine Queue<T> entfernt vorn in konstanter Zeit, und ihre API drückt die Absicht aus: Elemente werden in der Reihenfolge ihres Eintreffens verarbeitet.

Verwandte Konzepte