Потокобезопасен ли Queue в C#?

Нет. Одновременные вызовы Enqueue или Dequeue из двух потоков у одного Queue могут его испортить. Используйте ConcurrentQueue из System.Collections.Concurrent, чьи Enqueue и TryDequeue безопасно вызывать из многих потоков, или оборачивайте каждое обращение к обычной очереди в lock.

Исполняемые доки C#: Queue

Q: Что такое Queue в C#?

Queue из System.Collections.Generic это коллекция «первым пришёл, первым вышел» (FIFO). Enqueue добавляет элемент в конец, Dequeue удаляет и возвращает элемент из начала, а Peek возвращает первый элемент, не удаляя его. Все три операции выполняются за постоянное время.

Q: Что происходит при Dequeue из пустой очереди в C#?

Dequeue и Peek для пустой очереди выбрасывают InvalidOperationException. Сначала проверьте queue.Count > 0 или используйте TryDequeue(out var item) и TryPeek(out var item), которые вместо исключения возвращают false (доступны начиная с .NET Core 2.0).

Q: Чем Peek отличается от Dequeue?

Peek возвращает первый элемент и оставляет его в очереди, поэтому два вызова подряд вернут один и тот же элемент. Dequeue возвращает первый элемент и удаляет его, поэтому следующий вызов вернёт элемент, стоящий за ним.

Q: Зачем использовать Queue вместо List?

Удаление первого элемента List через RemoveAt(0) сдвигает все остальные элементы, поэтому замедляется по мере роста списка. Queue удаляет из начала за постоянное время, а её API выражает намерение: элементы обрабатываются в порядке поступления.

Queue<T> работает как очередь у кассы: первый добавленный элемент первым и забирается (FIFO, first in, first out). Вы добавляете в конец через 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 проверяйте Count > 0 перед вызовом Dequeue.

Просмотр содержимого очереди

Очередь можно перебрать, ничего не удаляя. 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.

Поиск в ширину с очередью

Порядок очереди это ровно то, что нужно поиску в ширину: посетить всё на расстоянии одного шага, затем всё на расстоянии двух шагов и так далее. Здесь он находит, сколько связей отделяет 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

Каждый человек попадает в очередь один раз, когда его впервые достигли, и поскольку очередь возвращает людей в порядке их нахождения, первый раз всегда приходится на кратчайший путь. Замените очередь на Stack, и тот же цикл станет поиском в глубину, который кратчайших путей уже не находит.

По той же схеме выполняются обход дерева по уровням, заливка области на сетке и обход ссылок: начните с одного элемента в очереди и, пока она не пуста, извлекайте элемент и добавляйте его непосещённых соседей.

Queue и List для работы FIFO

List<T> можно использовать как очередь через Add и RemoveAt(0), но RemoveAt(0) сдвигает все оставшиеся элементы на одну позицию вниз. Опустошение так списка из 100 000 элементов выполняет около пяти миллиардов перемещений; Queue<T> делает 100 000 шагов за постоянное время. Внутри очередь это кольцевой буфер: она хранит индексы начала и конца в массиве и выделяет память заново только при заполнении.

Операция	`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> не потокобезопасна. Когда несколько потоков добавляют или забирают элементы, используйте ConcurrentQueue<T> из System.Collections.Concurrent. У неё есть Enqueue, TryDequeue и TryPeek, но нет Dequeue, потому что при наличии других потоков схема «проверить Count, затем Dequeue» может сломаться между двумя вызовами.

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

С обычной Queue<T> вместо ConcurrentQueue<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) в роли очереди на больших данных. Каждый вызов занимает O(n).

Часто задаваемые вопросы

Что такое Queue в C#?

Queue<T> из System.Collections.Generic это коллекция «первым пришёл, первым вышел» (FIFO). Enqueue добавляет элемент в конец, Dequeue удаляет и возвращает элемент из начала, а Peek возвращает первый элемент, не удаляя его. Все три операции выполняются за постоянное время.

Что происходит при Dequeue из пустой очереди в C#?

Dequeue и Peek для пустой очереди выбрасывают InvalidOperationException. Сначала проверьте queue.Count > 0 или используйте TryDequeue(out var item) и TryPeek(out var item), которые вместо исключения возвращают false (доступны начиная с .NET Core 2.0).

Чем Peek отличается от Dequeue?

Peek возвращает первый элемент и оставляет его в очереди, поэтому два вызова подряд вернут один и тот же элемент. Dequeue возвращает первый элемент и удаляет его, поэтому следующий вызов вернёт элемент, стоящий за ним.

Потокобезопасен ли Queue<T> в C#?

Нет. Одновременные вызовы Enqueue или Dequeue из двух потоков у одного Queue<T> могут его испортить. Используйте ConcurrentQueue<T> из System.Collections.Concurrent, чьи Enqueue и TryDequeue безопасно вызывать из многих потоков, или оборачивайте каждое обращение к обычной очереди в lock.

Зачем использовать Queue вместо List?

Удаление первого элемента List<T> через RemoveAt(0) сдвигает все остальные элементы, поэтому замедляется по мере роста списка. Queue<T> удаляет из начала за постоянное время, а её API выражает намерение: элементы обрабатываются в порядке поступления.

Связанные концепции