Queue è thread safe in C#?

No. Due thread che chiamano Enqueue o Dequeue sulla stessa Queue nello stesso momento possono corromperla. Usa ConcurrentQueue di System.Collections.Concurrent, i cui Enqueue e TryDequeue si possono chiamare in sicurezza da molti thread, oppure racchiudi ogni accesso a una coda normale in un lock.

Guida C# interattiva: Queue

Q: Cos'è una Queue in C#?

Queue in System.Collections.Generic è una collezione first in, first out (FIFO). Enqueue aggiunge un elemento in fondo, Dequeue rimuove e restituisce l'elemento in testa, e Peek restituisce l'elemento in testa senza rimuoverlo. Tutte e tre richiedono tempo costante.

Q: Cosa succede se fai Dequeue su una coda vuota in C#?

Dequeue e Peek su una coda vuota lanciano InvalidOperationException. Controlla prima queue.Count > 0, oppure usa TryDequeue(out var item) e TryPeek(out var item), che restituiscono false invece di lanciare un'eccezione (disponibili da .NET Core 2.0).

Q: Che differenza c'è tra Peek e Dequeue?

Peek restituisce l'elemento in testa e lo lascia nella coda, quindi chiamarlo due volte restituisce lo stesso elemento. Dequeue restituisce l'elemento in testa e lo rimuove, quindi la chiamata successiva restituisce quello che lo seguiva.

Q: Perché usare una Queue invece di una List?

Rimuovere il primo elemento di una List con RemoveAt(0) sposta tutti gli altri elementi, quindi diventa più lento man mano che la lista cresce. Una Queue rimuove dalla testa in tempo costante, e la sua API dichiara l'intenzione: gli elementi vengono elaborati nell'ordine di arrivo.

Una Queue<T> funziona come la fila a uno sportello: il primo elemento aggiunto è il primo a uscire (FIFO, first in, first out). Aggiungi in fondo con Enqueue e prendi dalla testa con Dequeue, entrambi in tempo costante.

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

Output:

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

Peek serve a decidere cosa fare con il prossimo elemento prima di impegnarti; Dequeue è l'impegno. Il ciclo while (queue.Count > 0) che estrae finché la coda non è vuota è il modo standard di elaborare una coda, e continua a funzionare se il corpo del ciclo accoda altri elementi, cosa che un foreach non permette.

L'eccezione della coda vuota e TryDequeue

Dequeue e Peek su una coda vuota lanciano InvalidOperationException. Non esiste un comportamento "null quando è vuota", nemmeno per i tipi riferimento.

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

Output:

Caught InvalidOperationException
Serving ticket 41
Serving ticket 42
False

TryDequeue e TryPeek restituiscono true e impostano la variabile out quando c'è un elemento, e restituiscono false quando la coda è vuota. Sono arrivati con .NET Core 2.0; nel codice più vecchio per .NET Framework, controlla Count > 0 prima di chiamare Dequeue.

Guardare dentro una coda

Una coda si può enumerare senza rimuovere nulla. foreach, ToArray e Contains vedono tutti gli elementi dalla testa al fondo.

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

Output:

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

Non c'è un indice: line[1] non compila, e non puoi rimuovere un elemento dal mezzo. Se ti serve una delle due cose, i dati non sono davvero una coda; usa una List<T> o una LinkedList<T>. Come per le altre collezioni, accodare o estrarre dentro un foreach sulla stessa coda lancia InvalidOperationException.

Ricerca in ampiezza con una coda

L'ordine della coda è esattamente ciò che serve alla ricerca in ampiezza (BFS): visita tutto ciò che si trova a un passo, poi tutto ciò che si trova a due passi, e così via. Qui trova quanti collegamenti separano Ana da tutti gli altri in una piccola rete:

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

Output:

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

Ogni persona viene accodata una volta sola, la prima volta che viene raggiunta, e poiché la coda le restituisce nell'ordine in cui sono state trovate, la prima volta è sempre lungo un percorso minimo. Sostituisci la coda con uno Stack e lo stesso ciclo diventa una ricerca in profondità, che non trova più i percorsi minimi.

La stessa struttura gestisce la visita per livelli di un albero, il flood fill su una griglia e la scansione di link: parti con un elemento nella coda e, finché non è vuota, estraine uno e accoda i suoi vicini non ancora visitati.

Queue o List per il lavoro FIFO

Puoi usare una List<T> come coda con Add e RemoveAt(0), ma RemoveAt(0) sposta di una posizione tutti gli elementi rimanenti. Svuotare in questo modo una lista di 100.000 elementi richiede circa cinque miliardi di spostamenti; una Queue<T> fa 100.000 passi a tempo costante. Internamente una coda è un buffer circolare: tiene traccia di un indice di testa e uno di coda in un array e rialloca solo quando è piena.

Operazione	`Queue<T>`	`List<T>` usata come coda
Aggiungere in fondo	`Enqueue`, O(1)	`Add`, O(1)
Rimuovere dalla testa	`Dequeue`, O(1)	`RemoveAt(0)`, O(n)
Guardare la testa	`Peek`	`list[0]`
Accesso per indice	Non disponibile	`list[i]`

ConcurrentQueue per più thread

Queue<T> non è thread safe. Quando più thread aggiungono o prendono elementi, usa ConcurrentQueue<T> di System.Collections.Concurrent. Ha Enqueue, TryDequeue e TryPeek ma non Dequeue, perché con altri thread in giro "controlla Count e poi Dequeue" potrebbe fallire tra le due chiamate.

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

Output:

4000
4000 processed

Con una semplice Queue<T> al posto di ConcurrentQueue<T>, il conteggio risulterebbe sbagliato oppure il programma lancerebbe un'eccezione, a seconda delle tempistiche. Per thread produttori e consumatori che devono aspettare il lavoro invece di girare a vuoto, BlockingCollection<T> (che di default avvolge una ConcurrentQueue<T>) o System.Threading.Channels aggiungono il blocco e il completamento. Vedi lock per proteggere a mano una collezione normale.

PriorityQueue

Quando gli elementi devono uscire in base alla priorità invece che all'ordine di arrivo (il ticket più urgente per primo, il percorso più breve finora nell'algoritmo di Dijkstra), .NET 6 e successivi offrono PriorityQueue<TElement, TPriority>. Esce per primo il valore di priorità più basso:

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

Gli elementi con la stessa priorità possono uscire in qualsiasi ordine; aggiungi un numero progressivo alla priorità se l'ordine di arrivo deve decidere i pareggi.

Errori comuni

Estrarre senza controllare. Una coda vuota lancia InvalidOperationException; cicla su Count > 0 o usa TryDequeue.
Chiamare Peek e aspettarsi che l'elemento sparisca. Solo Dequeue rimuove.
Accodare dentro un foreach sulla coda. Lancia un'eccezione; elabora con un ciclo while.
Condividere una Queue<T> tra thread. Usa ConcurrentQueue<T> o un lock.
Usare List.RemoveAt(0) come coda su grandi quantità di dati. Ogni chiamata è O(n).

Domande frequenti

Cos'è una Queue in C#?

Queue<T> in System.Collections.Generic è una collezione first in, first out (FIFO). Enqueue aggiunge un elemento in fondo, Dequeue rimuove e restituisce l'elemento in testa, e Peek restituisce l'elemento in testa senza rimuoverlo. Tutte e tre richiedono tempo costante.

Cosa succede se fai Dequeue su una coda vuota in C#?

Dequeue e Peek su una coda vuota lanciano InvalidOperationException. Controlla prima queue.Count > 0, oppure usa TryDequeue(out var item) e TryPeek(out var item), che restituiscono false invece di lanciare un'eccezione (disponibili da .NET Core 2.0).

Che differenza c'è tra Peek e Dequeue?

Peek restituisce l'elemento in testa e lo lascia nella coda, quindi chiamarlo due volte restituisce lo stesso elemento. Dequeue restituisce l'elemento in testa e lo rimuove, quindi la chiamata successiva restituisce quello che lo seguiva.

Queue<T> è thread safe in C#?

No. Due thread che chiamano Enqueue o Dequeue sulla stessa Queue<T> nello stesso momento possono corromperla. Usa ConcurrentQueue<T> di System.Collections.Concurrent, i cui Enqueue e TryDequeue si possono chiamare in sicurezza da molti thread, oppure racchiudi ogni accesso a una coda normale in un lock.

Perché usare una Queue invece di una List?

Rimuovere il primo elemento di una List<T> con RemoveAt(0) sposta tutti gli altri elementi, quindi diventa più lento man mano che la lista cresce. Una Queue<T> rimuove dalla testa in tempo costante, e la sua API dichiara l'intenzione: gli elementi vengono elaborati nell'ordine di arrivo.

Concetti correlati