¿Es Queue segura para hilos en C#?

No. Dos hilos que llaman a la vez a Enqueue o Dequeue sobre la misma Queue pueden corromperla. Usa ConcurrentQueue de System.Collections.Concurrent, cuyos Enqueue y TryDequeue pueden llamarse sin riesgo desde muchos hilos, o envuelve cada acceso a una cola normal en un lock.

Docs ejecutables de C#: Queue

Q: ¿Qué es una Queue en C#?

Queue de System.Collections.Generic es una colección FIFO (first in, first out, el primero que entra es el primero que sale). Enqueue añade un elemento al final, Dequeue quita y devuelve el elemento del principio, y Peek devuelve el elemento del principio sin quitarlo. Las tres operaciones tardan un tiempo constante.

Q: ¿Qué ocurre al hacer Dequeue sobre una cola vacía en C#?

Dequeue y Peek sobre una cola vacía lanzan InvalidOperationException. Comprueba antes queue.Count > 0, o usa TryDequeue(out var item) y TryPeek(out var item), que devuelven false en lugar de lanzar una excepción (disponibles desde .NET Core 2.0).

Q: ¿Qué diferencia hay entre Peek y Dequeue?

Peek devuelve el elemento del principio y lo deja en la cola, así que llamarlo dos veces devuelve el mismo elemento. Dequeue devuelve el elemento del principio y lo quita, así que la siguiente llamada devuelve el que va detrás.

Q: ¿Por qué usar una Queue en lugar de una List?

Quitar el primer elemento de una List con RemoveAt(0) desplaza todos los demás, así que se vuelve más lento a medida que crece la lista. Una Queue quita del principio en tiempo constante, y su API expresa la intención: los elementos se procesan en orden de llegada.

Una Queue<T> funciona como la fila de un mostrador: el primer elemento añadido es el primero que se saca (FIFO, first in, first out). Añades al final con Enqueue y sacas del principio con Dequeue, las dos en tiempo constante.

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

Salida:

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

Peek sirve para decidir qué hacer con el siguiente elemento antes de comprometerte con él; Dequeue se compromete. El bucle while (queue.Count > 0) que saca elementos hasta vaciar la cola es la forma habitual de procesar una cola, y sigue funcionando si el cuerpo del bucle añade más elementos, algo que un foreach no permite.

La excepción de la cola vacía y TryDequeue

Dequeue y Peek sobre una cola vacía lanzan InvalidOperationException. No existe un comportamiento de "null cuando está vacía", ni siquiera con tipos de referencia.

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

Salida:

Caught InvalidOperationException
Serving ticket 41
Serving ticket 42
False

TryDequeue y TryPeek devuelven true y asignan la variable out cuando hay un elemento, y devuelven false cuando la cola está vacía. Llegaron en .NET Core 2.0; en código antiguo de .NET Framework, comprueba Count > 0 antes de llamar a Dequeue.

Mirar dentro de una cola

Una cola puede enumerarse sin quitar nada. foreach, ToArray y Contains ven los elementos del principio al final.

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

Salida:

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

No hay índice: line[1] no compila, y no puedes quitar un elemento del medio. Si necesitas cualquiera de las dos cosas, los datos no son realmente una cola; usa una List<T> o una LinkedList<T>. Como con otras colecciones, añadir o sacar elementos dentro de un foreach sobre la misma cola lanza InvalidOperationException.

Búsqueda en anchura con una cola

El orden de la cola es justo lo que necesita la búsqueda en anchura: visitar todo lo que está a un paso, después todo lo que está a dos pasos, y así sucesivamente. Aquí averigua cuántas conexiones separan a Ana de todos los demás en una red pequeña:

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

Salida:

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 persona se añade a la cola una sola vez, la primera vez que se la alcanza, y como la cola las devuelve en el orden en que se encontraron, la primera vez siempre es por un camino más corto. Cambia la cola por un Stack y el mismo bucle se convierte en una búsqueda en profundidad, que ya no encuentra los caminos más cortos.

La misma forma sirve para recorrer un árbol por niveles, para el relleno por inundación en una cuadrícula y para rastrear enlaces: empieza con un elemento en la cola y, mientras no esté vacía, saca uno y añade sus vecinos no visitados.

Queue frente a List para trabajo FIFO

Puedes usar una List<T> como cola con Add y RemoveAt(0), pero RemoveAt(0) desplaza una posición hacia abajo todos los elementos restantes. Vaciar así una lista de 100.000 elementos supone unos cinco mil millones de movimientos de elementos; una Queue<T> hace 100.000 pasos de tiempo constante. Internamente, una cola es un buffer circular: lleva la cuenta de un índice de cabeza y otro de cola dentro de un array y solo vuelve a reservar memoria cuando se llena.

Operación	`Queue<T>`	`List<T>` usada como cola
Añadir al final	`Enqueue`, O(1)	`Add`, O(1)
Quitar del principio	`Dequeue`, O(1)	`RemoveAt(0)`, O(n)
Mirar el principio	`Peek`	`list[0]`
Acceso por índice	No disponible	`list[i]`

ConcurrentQueue para varios hilos

Queue<T> no es segura para hilos. Cuando varios hilos añaden o sacan elementos, usa ConcurrentQueue<T> de System.Collections.Concurrent. Tiene Enqueue, TryDequeue y TryPeek pero no Dequeue, porque con otros hilos alrededor, "comprobar Count y después hacer Dequeue" podría fallar entre las dos llamadas.

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

Salida:

4000
4000 processed

Con una Queue<T> normal en lugar de ConcurrentQueue<T>, el recuento saldría mal o el programa lanzaría una excepción, según el momento. Para hilos productores y consumidores que deben esperar al trabajo en lugar de girar en vacío, BlockingCollection<T> (que por defecto envuelve una ConcurrentQueue<T>) o System.Threading.Channels añaden bloqueo y finalización. Consulta lock para proteger a mano una colección normal.

PriorityQueue

Cuando los elementos deben salir por prioridad y no por orden de llegada (primero el ticket más urgente, el camino más corto hasta el momento en el algoritmo de Dijkstra), .NET 6 y posteriores ofrecen PriorityQueue<TElement, TPriority>. Sale primero el valor de prioridad más bajo:

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

Los elementos con la misma prioridad pueden salir en cualquier orden; añade un número de secuencia a la prioridad si el orden de llegada debe deshacer los empates.

Errores comunes

Sacar sin comprobar. Una cola vacía lanza InvalidOperationException; haz el bucle con Count > 0 o usa TryDequeue.
Llamar a Peek y esperar que el elemento haya desaparecido. Solo Dequeue lo quita.
Añadir elementos dentro de un foreach sobre la cola. Lanza una excepción; procesa con un bucle while.
Compartir una Queue<T> entre hilos. Usa ConcurrentQueue<T> o un lock.
Usar List.RemoveAt(0) como cola con muchos datos. Cada llamada es O(n).

Preguntas frecuentes

¿Qué es una Queue en C#?

Queue<T> de System.Collections.Generic es una colección FIFO (first in, first out, el primero que entra es el primero que sale). Enqueue añade un elemento al final, Dequeue quita y devuelve el elemento del principio, y Peek devuelve el elemento del principio sin quitarlo. Las tres operaciones tardan un tiempo constante.

¿Qué ocurre al hacer Dequeue sobre una cola vacía en C#?

Dequeue y Peek sobre una cola vacía lanzan InvalidOperationException. Comprueba antes queue.Count > 0, o usa TryDequeue(out var item) y TryPeek(out var item), que devuelven false en lugar de lanzar una excepción (disponibles desde .NET Core 2.0).

¿Qué diferencia hay entre Peek y Dequeue?

Peek devuelve el elemento del principio y lo deja en la cola, así que llamarlo dos veces devuelve el mismo elemento. Dequeue devuelve el elemento del principio y lo quita, así que la siguiente llamada devuelve el que va detrás.

¿Es Queue<T> segura para hilos en C#?

No. Dos hilos que llaman a la vez a Enqueue o Dequeue sobre la misma Queue<T> pueden corromperla. Usa ConcurrentQueue<T> de System.Collections.Concurrent, cuyos Enqueue y TryDequeue pueden llamarse sin riesgo desde muchos hilos, o envuelve cada acceso a una cola normal en un lock.

¿Por qué usar una Queue en lugar de una List?

Quitar el primer elemento de una List<T> con RemoveAt(0) desplaza todos los demás, así que se vuelve más lento a medida que crece la lista. Una Queue<T> quita del principio en tiempo constante, y su API expresa la intención: los elementos se procesan en orden de llegada.

Conceptos relacionados