Docs executáveis de C#: Queue (fila)

Q: O que é uma Queue em C#?

Queue , em System.Collections.Generic, é uma coleção em que o primeiro a entrar é o primeiro a sair (FIFO). Enqueue adiciona um item no fim, Dequeue remove e retorna o item da frente, e Peek retorna o item da frente sem removê-lo. Os três levam tempo constante.

Q: O que acontece ao fazer Dequeue em uma fila vazia em C#?

Dequeue e Peek em uma fila vazia lançam InvalidOperationException. Verifique queue.Count > 0 antes, ou use TryDequeue(out var item) e TryPeek(out var item), que retornam false em vez de lançar exceção (disponíveis desde o .NET Core 2.0).

Q: Qual a diferença entre Peek e Dequeue?

Peek retorna o item da frente e o deixa na fila, então chamá-lo duas vezes retorna o mesmo item. Dequeue retorna o item da frente e o remove, então a próxima chamada retorna o item que estava atrás dele.

Q: Queue é thread safe em C#?

Não. Duas threads chamando Enqueue ou Dequeue na mesma Queue ao mesmo tempo podem corrompê-la. Use ConcurrentQueue de System.Collections.Concurrent, cujos Enqueue e TryDequeue podem ser chamados com segurança de muitas threads, ou envolva todo acesso a uma fila normal em um lock.

Q: Por que usar uma Queue em vez de uma List?

Remover o primeiro item de uma List com RemoveAt(0) desloca todos os outros itens, então fica mais lento à medida que a lista cresce. Uma Queue remove da frente em tempo constante, e a API dela deixa a intenção clara: os itens são processados na ordem de chegada.

Uma Queue<T> funciona como uma fila no balcão: o primeiro item adicionado é o primeiro a sair (FIFO, first in, first out). Você adiciona no fim com Enqueue e tira da frente com Dequeue, os dois em tempo constante.

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

Saída:

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

Peek serve para decidir o que fazer com o próximo item antes de se comprometer com ele; Dequeue se compromete. O laço while (queue.Count > 0) que faz dequeue até esvaziar é a forma padrão de processar uma fila, e ele continua funcionando se o corpo do laço enfileirar mais itens, o que um foreach não permite.

A exceção da fila vazia e o TryDequeue

Dequeue e Peek em uma fila vazia lançam InvalidOperationException. Não existe o comportamento "null quando vazia", nem para tipos de referência.

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

Saída:

Caught InvalidOperationException
Serving ticket 41
Serving ticket 42
False

TryDequeue e TryPeek retornam true e definem a variável out quando há um item, e retornam false quando a fila está vazia. Eles chegaram no .NET Core 2.0; em código mais antigo do .NET Framework, verifique Count > 0 antes de chamar Dequeue.

Olhando dentro de uma fila

Uma fila pode ser enumerada sem remover nada. foreach, ToArray e Contains veem os itens da frente para o fim.

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

Saída:

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

Não há índice: line[1] não compila, e você não pode remover um item do meio. Se você precisa de alguma dessas coisas, os dados na verdade não são uma fila; use uma List<T> ou uma LinkedList<T>. Como em outras coleções, enfileirar ou desenfileirar dentro de um foreach sobre a mesma fila lança InvalidOperationException.

Busca em largura com uma fila

A ordem da fila é exatamente o que a busca em largura precisa: visitar tudo o que está a um passo, depois tudo o que está a dois passos, e assim por diante. Aqui ela descobre quantas conexões separam Ana de todas as outras pessoas em uma rede pequena:

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

Saída:

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

Cada pessoa é enfileirada uma vez, na primeira vez em que é alcançada, e como a fila as devolve na ordem em que foram encontradas, essa primeira vez sempre segue um caminho mais curto. Troque a fila por uma Stack e o mesmo laço vira uma busca em profundidade, que não encontra mais os caminhos mais curtos.

A mesma forma resolve o percurso em nível de uma árvore, o flood fill em uma grade e o rastreamento de links: comece com um item na fila e, enquanto ela não estiver vazia, desenfileire um e enfileire os vizinhos ainda não visitados.

Queue vs List para trabalho FIFO

Você pode usar uma List<T> como fila com Add e RemoveAt(0), mas RemoveAt(0) desloca todos os elementos restantes uma posição para baixo. Esvaziar assim uma lista de 100.000 itens faz cerca de cinco bilhões de movimentações de elementos; uma Queue<T> faz 100.000 passos de tempo constante. Por dentro, uma fila é um buffer circular: ela acompanha um índice de início e um de fim em um array e só realoca quando enche.

Operação	`Queue<T>`	`List<T>` usada como fila
Adicionar no fim	`Enqueue`, O(1)	`Add`, O(1)
Remover da frente	`Dequeue`, O(1)	`RemoveAt(0)`, O(n)
Ver a frente	`Peek`	`list[0]`
Acesso por índice	Não disponível	`list[i]`

ConcurrentQueue para várias threads

Queue<T> não é thread safe. Quando várias threads adicionam ou retiram itens, use ConcurrentQueue<T> de System.Collections.Concurrent. Ela tem Enqueue, TryDequeue e TryPeek, mas não Dequeue, porque com outras threads por perto, "verificar Count e depois fazer Dequeue" poderia falhar entre as duas chamadas.

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

Saída:

4000
4000 processed

Com uma Queue<T> comum no lugar de ConcurrentQueue<T>, a contagem sairia errada ou o programa lançaria uma exceção, dependendo do momento. Para threads produtoras e consumidoras que devem esperar por trabalho em vez de ficar girando, BlockingCollection<T> (que por padrão envolve uma ConcurrentQueue<T>) ou System.Threading.Channels adicionam bloqueio e conclusão. Veja lock para proteger uma coleção normal manualmente.

PriorityQueue

Quando os itens devem sair por prioridade em vez de pela ordem de chegada (o chamado mais urgente primeiro, o caminho mais curto até agora no algoritmo de Dijkstra), o .NET 6 em diante oferece PriorityQueue<TElement, TPriority>. O menor valor de prioridade sai primeiro:

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

Itens com a mesma prioridade podem sair em qualquer ordem; adicione um número de sequência à prioridade se a ordem de chegada precisar desempatar.

Erros comuns

Fazer Dequeue sem verificar. Uma fila vazia lança InvalidOperationException; faça o laço com Count > 0 ou use TryDequeue.
Chamar Peek e esperar que o item tenha saído. Só o Dequeue remove.
Enfileirar dentro de um foreach sobre a fila. Lança exceção; processe com um laço while.
Compartilhar uma Queue<T> entre threads. Use ConcurrentQueue<T> ou um lock.
Usar List.RemoveAt(0) como fila em dados grandes. Cada chamada é O(n).

Perguntas frequentes

O que é uma Queue em C#?

Queue<T>, em System.Collections.Generic, é uma coleção em que o primeiro a entrar é o primeiro a sair (FIFO). Enqueue adiciona um item no fim, Dequeue remove e retorna o item da frente, e Peek retorna o item da frente sem removê-lo. Os três levam tempo constante.

O que acontece ao fazer Dequeue em uma fila vazia em C#?

Dequeue e Peek em uma fila vazia lançam InvalidOperationException. Verifique queue.Count > 0 antes, ou use TryDequeue(out var item) e TryPeek(out var item), que retornam false em vez de lançar exceção (disponíveis desde o .NET Core 2.0).

Qual a diferença entre Peek e Dequeue?

Peek retorna o item da frente e o deixa na fila, então chamá-lo duas vezes retorna o mesmo item. Dequeue retorna o item da frente e o remove, então a próxima chamada retorna o item que estava atrás dele.

Queue<T> é thread safe em C#?

Não. Duas threads chamando Enqueue ou Dequeue na mesma Queue<T> ao mesmo tempo podem corrompê-la. Use ConcurrentQueue<T> de System.Collections.Concurrent, cujos Enqueue e TryDequeue podem ser chamados com segurança de muitas threads, ou envolva todo acesso a uma fila normal em um lock.

Por que usar uma Queue em vez de uma List?

Remover o primeiro item de uma List<T> com RemoveAt(0) desloca todos os outros itens, então fica mais lento à medida que a lista cresce. Uma Queue<T> remove da frente em tempo constante, e a API dela deixa a intenção clara: os itens são processados na ordem de chegada.

Conceitos relacionados