Docs C# exécutables : Queue

Q: Qu'est-ce qu'une Queue en C# ?

Queue , dans System.Collections.Generic, est une collection premier entré, premier sorti (FIFO). Enqueue ajoute un élément à l'arrière, Dequeue retire et renvoie l'élément à l'avant, et Peek renvoie l'élément de tête sans le retirer. Les trois s'exécutent en temps constant.

Q: Que se passe-t-il quand on appelle Dequeue sur une file vide en C# ?

Dequeue et Peek sur une file vide lèvent InvalidOperationException. Vérifiez d'abord queue.Count > 0, ou utilisez TryDequeue(out var item) et TryPeek(out var item), qui renvoient false au lieu de lever une exception (disponibles depuis .NET Core 2.0).

Q: Quelle est la différence entre Peek et Dequeue ?

Peek renvoie l'élément de tête et le laisse dans la file, donc deux appels renvoient le même élément. Dequeue renvoie l'élément de tête et le retire, donc l'appel suivant renvoie l'élément qui le suit.

Q: Queue est-il thread-safe en C# ?

Non. Deux threads qui appellent Enqueue ou Dequeue en même temps sur la même Queue peuvent la corrompre. Utilisez ConcurrentQueue de System.Collections.Concurrent, dont Enqueue et TryDequeue peuvent être appelés sans risque depuis de nombreux threads, ou protégez chaque accès à une file normale par un lock.

Q: Pourquoi utiliser une Queue plutôt qu'une List ?

Retirer le premier élément d'une List avec RemoveAt(0) décale tous les autres éléments, ce qui ralentit à mesure que la liste grandit. Une Queue retire en tête en temps constant, et son API exprime l'intention : les éléments sont traités dans leur ordre d'arrivée.

Une Queue<T> fonctionne comme une file d'attente à un guichet : le premier élément ajouté est le premier retiré (FIFO, premier entré, premier sorti). On ajoute à l'arrière avec Enqueue et on retire à l'avant avec Dequeue, les deux en temps constant.

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

Sortie :

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

Peek sert à décider quoi faire du prochain élément avant de s'engager ; Dequeue engage. La boucle while (queue.Count > 0) qui retire jusqu'à ce que la file soit vide est la façon standard de traiter une file, et elle continue de fonctionner si le corps de la boucle ajoute d'autres éléments, ce qu'un foreach ne permet pas.

L'exception de file vide et TryDequeue

Dequeue et Peek sur une file vide lèvent InvalidOperationException. Il n'y a pas de comportement « null quand vide », même pour les types référence.

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

Sortie :

Caught InvalidOperationException
Serving ticket 41
Serving ticket 42
False

TryDequeue et TryPeek renvoient true et remplissent la variable out quand il y a un élément, et renvoient false quand la file est vide. Elles sont arrivées avec .NET Core 2.0 ; dans du code .NET Framework plus ancien, vérifiez Count > 0 avant d'appeler Dequeue.

Regarder à l'intérieur d'une file

Une file peut être énumérée sans rien retirer. foreach, ToArray et Contains voient tous les éléments de l'avant vers l'arrière.

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

Sortie :

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

Il n'y a pas d'index : line[1] ne compile pas, et vous ne pouvez pas retirer un élément du milieu. Si vous avez besoin de l'un ou de l'autre, les données ne forment pas vraiment une file ; utilisez une List<T> ou une LinkedList<T>. Comme pour les autres collections, ajouter ou retirer dans un foreach sur la même file lève InvalidOperationException.

Parcours en largeur avec une file

L'ordre de la file est exactement ce dont a besoin le parcours en largeur (breadth first search) : visiter tout ce qui est à un pas, puis tout ce qui est à deux pas, et ainsi de suite. Ici, il calcule combien de relations séparent Ana de chacun dans un petit réseau :

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

Sortie :

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

Chaque personne est ajoutée à la file une seule fois, la première fois qu'elle est atteinte, et comme la file les rend dans l'ordre où elles ont été trouvées, cette première fois correspond toujours à un plus court chemin. Remplacez la file par une Stack et la même boucle devient un parcours en profondeur, qui ne trouve plus les plus courts chemins.

La même forme traite le parcours par niveaux d'un arbre, le remplissage par diffusion (flood fill) sur une grille et l'exploration de liens : commencez avec un élément dans la file et, tant qu'elle n'est pas vide, retirez-en un et ajoutez ses voisins non visités.

Queue ou List pour un traitement FIFO

Vous pouvez utiliser une List<T> comme file avec Add et RemoveAt(0), mais RemoveAt(0) décale d'un emplacement chaque élément restant. Vider ainsi une liste de 100 000 éléments représente environ cinq milliards de déplacements d'éléments ; une Queue<T> fait 100 000 étapes en temps constant. En interne, une file est un tampon circulaire : elle suit un index de tête et un index de queue dans un tableau et ne réalloue que lorsqu'elle est pleine.

Opération	`Queue<T>`	`List<T>` utilisée comme file
Ajouter à l'arrière	`Enqueue`, O(1)	`Add`, O(1)
Retirer à l'avant	`Dequeue`, O(1)	`RemoveAt(0)`, O(n)
Regarder la tête	`Peek`	`list[0]`
Accès par index	Non disponible	`list[i]`

ConcurrentQueue pour plusieurs threads

Queue<T> n'est pas thread-safe. Quand plusieurs threads ajoutent ou retirent des éléments, utilisez ConcurrentQueue<T> de System.Collections.Concurrent. Elle a Enqueue, TryDequeue et TryPeek mais pas Dequeue, car avec d'autres threads en jeu, « vérifier Count puis Dequeue » pourrait échouer entre les deux appels.

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

Sortie :

4000
4000 processed

Avec une simple Queue<T> à la place de ConcurrentQueue<T>, le compte serait faux ou le programme lèverait une exception, selon le timing. Pour des threads producteurs et consommateurs qui doivent attendre du travail au lieu de tourner à vide, BlockingCollection<T> (qui enveloppe une ConcurrentQueue<T> par défaut) ou System.Threading.Channels ajoutent l'attente bloquante et la notion de fin. Voir lock pour protéger une collection normale à la main.

PriorityQueue

Quand les éléments doivent sortir par priorité plutôt que par ordre d'arrivée (le ticket le plus urgent d'abord, le plus court chemin trouvé jusque-là dans l'algorithme de Dijkstra), .NET 6 et plus fournissent PriorityQueue<TElement, TPriority>. La valeur de priorité la plus basse sort en premier :

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

Les éléments de même priorité peuvent sortir dans n'importe quel ordre ; ajoutez un numéro de séquence à la priorité si l'ordre d'arrivée doit départager les égalités.

Erreurs courantes

Retirer sans vérifier. Une file vide lève InvalidOperationException ; bouclez sur Count > 0 ou utilisez TryDequeue.
Appeler Peek en s'attendant à ce que l'élément disparaisse. Seul Dequeue retire.
Ajouter dans un foreach sur la file. Cela lève une exception ; traitez plutôt avec une boucle while.
Partager une Queue<T> entre threads. Utilisez ConcurrentQueue<T> ou un verrou.
Utiliser List.RemoveAt(0) comme file sur de gros volumes. Chaque appel est en O(n).

Questions fréquentes

Qu'est-ce qu'une Queue en C# ?

Queue<T>, dans System.Collections.Generic, est une collection premier entré, premier sorti (FIFO). Enqueue ajoute un élément à l'arrière, Dequeue retire et renvoie l'élément à l'avant, et Peek renvoie l'élément de tête sans le retirer. Les trois s'exécutent en temps constant.

Que se passe-t-il quand on appelle Dequeue sur une file vide en C# ?

Dequeue et Peek sur une file vide lèvent InvalidOperationException. Vérifiez d'abord queue.Count > 0, ou utilisez TryDequeue(out var item) et TryPeek(out var item), qui renvoient false au lieu de lever une exception (disponibles depuis .NET Core 2.0).

Quelle est la différence entre Peek et Dequeue ?

Peek renvoie l'élément de tête et le laisse dans la file, donc deux appels renvoient le même élément. Dequeue renvoie l'élément de tête et le retire, donc l'appel suivant renvoie l'élément qui le suit.

Queue<T> est-il thread-safe en C# ?

Non. Deux threads qui appellent Enqueue ou Dequeue en même temps sur la même Queue<T> peuvent la corrompre. Utilisez ConcurrentQueue<T> de System.Collections.Concurrent, dont Enqueue et TryDequeue peuvent être appelés sans risque depuis de nombreux threads, ou protégez chaque accès à une file normale par un lock.

Pourquoi utiliser une Queue plutôt qu'une List ?

Retirer le premier élément d'une List<T> avec RemoveAt(0) décale tous les autres éléments, ce qui ralentit à mesure que la liste grandit. Une Queue<T> retire en tête en temps constant, et son API exprime l'intention : les éléments sont traités dans leur ordre d'arrivée.

Concepts liés