Dokumentacja C# z przykładami: Queue

Q: Czym jest Queue w C#?

Queue z System.Collections.Generic to kolekcja typu first in, first out (FIFO). Enqueue dodaje element na koniec, Dequeue usuwa i zwraca element z przodu, a Peek zwraca element z przodu bez usuwania go. Wszystkie trzy działają w czasie stałym.

Q: Co się dzieje po wywołaniu Dequeue na pustej kolejce w C#?

Dequeue i Peek na pustej kolejce rzucają InvalidOperationException. Najpierw sprawdź queue.Count > 0 albo użyj TryDequeue(out var item) i TryPeek(out var item), które zamiast rzucać wyjątek zwracają false (dostępne od .NET Core 2.0).

Q: Jaka jest różnica między Peek a Dequeue?

Peek zwraca element z przodu i zostawia go w kolejce, więc dwukrotne wywołanie zwraca ten sam element. Dequeue zwraca element z przodu i go usuwa, więc następne wywołanie zwraca element stojący za nim.

Q: Czy Queue jest bezpieczna wątkowo w C#?

Nie. Dwa wątki wywołujące jednocześnie Enqueue lub Dequeue na tej samej Queue mogą ją uszkodzić. Użyj ConcurrentQueue z System.Collections.Concurrent, której Enqueue i TryDequeue można bezpiecznie wywoływać z wielu wątków, albo otocz każdy dostęp do zwykłej kolejki instrukcją lock.

Q: Dlaczego używać Queue zamiast List?

Usunięcie pierwszego elementu z List przez RemoveAt(0) przesuwa wszystkie pozostałe elementy, więc działa coraz wolniej w miarę wzrostu listy. Queue usuwa z przodu w czasie stałym, a jej API wyraża intencję: elementy są przetwarzane w kolejności przybycia.

Queue<T> działa jak kolejka do okienka: pierwszy dodany element jest pierwszym wyjętym (FIFO, first in, first out). Dodajesz na koniec za pomocą Enqueue i zabierasz z przodu za pomocą Dequeue, obie operacje w czasie stałym.

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

Wynik:

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

Peek służy do zdecydowania, co zrobić z następnym elementem, zanim się na niego zdecydujesz; Dequeue tę decyzję wykonuje. Pętla while (queue.Count > 0), która wyjmuje elementy aż do opróżnienia, to standardowy sposób przetwarzania kolejki i działa dalej, nawet jeśli ciało pętli dodaje nowe elementy, na co foreach nie pozwala.

Wyjątek pustej kolejki i TryDequeue

Dequeue i Peek na pustej kolejce rzucają InvalidOperationException. Nie ma zachowania "null, gdy pusto", nawet dla typów referencyjnych.

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

Wynik:

Caught InvalidOperationException
Serving ticket 41
Serving ticket 42
False

TryDequeue i TryPeek zwracają true i ustawiają zmienną out, gdy jest jakiś element, a gdy kolejka jest pusta, zwracają false. Pojawiły się w .NET Core 2.0; w starszym kodzie .NET Framework sprawdzaj Count > 0 przed wywołaniem Dequeue.

Zaglądanie do kolejki

Kolejkę można przeglądać bez usuwania czegokolwiek. foreach, ToArray i Contains widzą elementy od przodu do końca.

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

Wynik:

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

Nie ma indeksu: line[1] się nie kompiluje i nie da się usunąć elementu ze środka. Jeśli potrzebujesz któregoś z nich, dane tak naprawdę nie są kolejką; użyj List<T> albo LinkedList<T>. Jak w innych kolekcjach, dodawanie lub wyjmowanie elementów wewnątrz foreach po tej samej kolejce rzuca InvalidOperationException.

Przeszukiwanie wszerz z kolejką

Kolejność kolejki to dokładnie to, czego potrzebuje przeszukiwanie wszerz (BFS): odwiedź wszystko, co jest o jeden krok dalej, potem wszystko o dwa kroki dalej i tak dalej. Tutaj znajduje ono, ile połączeń dzieli Anę od wszystkich innych w małej sieci:

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

Wynik:

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

Każda osoba trafia do kolejki raz, gdy zostanie osiągnięta po raz pierwszy, a ponieważ kolejka oddaje osoby w kolejności ich znalezienia, ten pierwszy raz zawsze prowadzi najkrótszą ścieżką. Zamień kolejkę na Stack, a ta sama pętla stanie się przeszukiwaniem w głąb (DFS), które nie znajduje już najkrótszych ścieżek.

Ten sam schemat obsługuje przechodzenie drzewa poziomami, wypełnianie obszaru na siatce (flood fill) i przechodzenie po linkach: zacznij od jednego elementu w kolejce i dopóki nie jest pusta, wyjmij jeden i dodaj jego nieodwiedzonych sąsiadów.

Queue a List do pracy FIFO

Możesz używać List<T> jako kolejki z Add i RemoveAt(0), ale RemoveAt(0) przesuwa każdy pozostały element o jedno miejsce w dół. Opróżnienie w ten sposób listy 100 000 elementów to około pięciu miliardów przesunięć elementów; Queue<T> wykonuje 100 000 kroków w czasie stałym. Wewnętrznie kolejka to bufor cykliczny: śledzi indeks początku i końca w tablicy i realokuje ją tylko wtedy, gdy jest pełna.

Operacja	`Queue<T>`	`List<T>` użyta jako kolejka
Dodanie na koniec	`Enqueue`, O(1)	`Add`, O(1)
Usunięcie z przodu	`Dequeue`, O(1)	`RemoveAt(0)`, O(n)
Podgląd przodu	`Peek`	`list[0]`
Dostęp po indeksie	Niedostępny	`list[i]`

ConcurrentQueue dla wielu wątków

Queue<T> nie jest bezpieczna wątkowo. Gdy kilka wątków dodaje lub zabiera elementy, użyj ConcurrentQueue<T> z System.Collections.Concurrent. Ma Enqueue, TryDequeue i TryPeek, ale nie ma Dequeue, bo przy innych wątkach wokół schemat "sprawdź Count, potem Dequeue" mógłby zawieść między tymi dwoma wywołaniami.

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

Wynik:

4000
4000 processed

Ze zwykłą Queue<T> w miejscu ConcurrentQueue<T> licznik wyszedłby błędny albo program rzuciłby wyjątek, zależnie od kolejności wykonania. Dla wątków producenta i konsumenta, które powinny czekać na pracę zamiast kręcić się w pętli, BlockingCollection<T> (domyślnie opakowujące ConcurrentQueue<T>) albo System.Threading.Channels dodają blokowanie i sygnał zakończenia. O ręcznej ochronie zwykłej kolekcji przeczytasz na stronie o lock.

PriorityQueue

Gdy elementy powinny wychodzić według priorytetu, a nie kolejności przybycia (najpilniejsze zgłoszenie najpierw, dotychczas najkrótsza ścieżka w algorytmie Dijkstry), .NET 6 i nowsze udostępniają PriorityQueue<TElement, TPriority>. Najpierw wychodzi element o najniższej wartości priorytetu:

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

Elementy o równym priorytecie mogą wychodzić w dowolnej kolejności; dodaj do priorytetu numer kolejny, jeśli remisy ma rozstrzygać kolejność przybycia.

Typowe błędy

Wyjmowanie bez sprawdzenia. Pusta kolejka rzuca InvalidOperationException; zapętlaj na Count > 0 albo użyj TryDequeue.
Wywołanie Peek w przekonaniu, że element zniknie. Usuwa tylko Dequeue.
Dodawanie elementów wewnątrz foreach po kolejce. Rzuca wyjątek; przetwarzaj pętlą while.
Współdzielenie Queue<T> między wątkami. Użyj ConcurrentQueue<T> albo blokady.
Używanie List.RemoveAt(0) jako kolejki na dużych danych. Każde wywołanie to O(n).

Najczęściej zadawane pytania

Czym jest Queue w C#?

Queue<T> z System.Collections.Generic to kolekcja typu first in, first out (FIFO). Enqueue dodaje element na koniec, Dequeue usuwa i zwraca element z przodu, a Peek zwraca element z przodu bez usuwania go. Wszystkie trzy działają w czasie stałym.

Co się dzieje po wywołaniu Dequeue na pustej kolejce w C#?

Dequeue i Peek na pustej kolejce rzucają InvalidOperationException. Najpierw sprawdź queue.Count > 0 albo użyj TryDequeue(out var item) i TryPeek(out var item), które zamiast rzucać wyjątek zwracają false (dostępne od .NET Core 2.0).

Jaka jest różnica między Peek a Dequeue?

Peek zwraca element z przodu i zostawia go w kolejce, więc dwukrotne wywołanie zwraca ten sam element. Dequeue zwraca element z przodu i go usuwa, więc następne wywołanie zwraca element stojący za nim.

Czy Queue<T> jest bezpieczna wątkowo w C#?

Nie. Dwa wątki wywołujące jednocześnie Enqueue lub Dequeue na tej samej Queue<T> mogą ją uszkodzić. Użyj ConcurrentQueue<T> z System.Collections.Concurrent, której Enqueue i TryDequeue można bezpiecznie wywoływać z wielu wątków, albo otocz każdy dostęp do zwykłej kolejki instrukcją lock.

Dlaczego używać Queue zamiast List?

Usunięcie pierwszego elementu z List<T> przez RemoveAt(0) przesuwa wszystkie pozostałe elementy, więc działa coraz wolniej w miarę wzrostu listy. Queue<T> usuwa z przodu w czasie stałym, a jej API wyraża intencję: elementy są przetwarzane w kolejności przybycia.

Powiązane zagadnienia