Docs C# exécutables : Stack

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

Stack , dans System.Collections.Generic, est une collection dernier entré, premier sorti (LIFO). Push pose un élément au sommet, Pop retire et renvoie l'élément du sommet, et Peek renvoie l'élément du sommet sans le retirer. Les trois s'exécutent en temps constant.

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

Pop et Peek lèvent InvalidOperationException quand la pile est vide. Vérifiez d'abord stack.Count > 0, ou utilisez TryPop(out var item) et TryPeek(out var item), qui renvoient false au lieu de lever une exception (.NET Core 2.0 et plus).

Q: Quelle est la différence entre une Stack et une Queue en C# ?

Une Stack renvoie d'abord l'élément le plus récent (dernier entré, premier sorti), tandis qu'une Queue renvoie d'abord le plus ancien (premier entré, premier sorti). Utilisez une pile pour un historique d'annulation, les structures imbriquées et le parcours en profondeur ; utilisez une file pour traiter le travail dans l'ordre d'arrivée et pour le parcours en largeur.

Une Stack<T> est une pile : vous posez des éléments au sommet avec Push et les retirez du sommet avec Pop, donc le dernier élément entré est le premier sorti (LIFO). Seul le sommet est accessible, et chaque opération sur lui prend un temps constant.

Push, Pop et Peek

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var plates = new Stack<string>();
        plates.Push("blue");
        plates.Push("red");
        plates.Push("green");

        Console.WriteLine("On top: " + plates.Peek()); // look only
        Console.WriteLine("Count: " + plates.Count);

        Console.WriteLine("Took " + plates.Pop());       // remove the top
        Console.WriteLine("On top: " + plates.Peek());

        while (plates.Count > 0)
        {
            Console.WriteLine("Took " + plates.Pop());
        }
        Console.WriteLine("Count: " + plates.Count);
    }
}

Sortie :

On top: green
Count: 3
Took green
On top: red
Took red
Took blue
Count: 0

green a été empilé en dernier, il sort donc en premier. Peek renvoie le sommet sans modifier la pile, ce qui permet d'examiner ce que Pop vous donnerait avant de décider de le prendre.

L'exception de pile vide et TryPop

Dépiler ou consulter une pile vide lève InvalidOperationException. Cela arrive le plus souvent dans les analyseurs et les algorithmes alimentés par une entrée qui contient plus d'éléments fermants qu'ouvrants.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var history = new Stack<int>();

        try
        {
            history.Pop();
        }
        catch (InvalidOperationException e)
        {
            Console.WriteLine("Caught " + e.GetType().Name);
        }

        history.Push(10);

        int value;
        Console.WriteLine(history.TryPop(out value) + " " + value);
        Console.WriteLine(history.TryPop(out value) + " " + value); // empty now
    }
}

Sortie :

Caught InvalidOperationException
True 10
False 0

TryPop et TryPeek (.NET Core 2.0 et plus) renvoient false sur une pile vide et mettent la variable out à la valeur par défaut, ici 0. Sur .NET Framework, vérifiez d'abord Count > 0.

Ordre d'itération : le sommet d'abord

Énumérer une pile ne retire rien, et va du sommet vers le bas, dans l'ordre où Pop renverrait les éléments :

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        var pages = new Stack<string>();
        pages.Push("home");
        pages.Push("products");
        pages.Push("checkout");

        foreach (string page in pages)
        {
            Console.Write(page + " ");
        }
        Console.WriteLine();

        Console.WriteLine(string.Join(" > ", pages.ToArray()));
        Console.WriteLine(pages.Contains("home"));

        var copy = new Stack<string>(pages);  // pushes in enumeration order...
        Console.WriteLine(copy.Peek());        // ...so the copy is reversed

        var sameOrder = new Stack<string>(pages.Reverse());
        Console.WriteLine(sameOrder.Peek());
    }
}

Sortie :

checkout products home 
checkout > products > home
True
home
checkout

La copie inversée piège les développeurs : le constructeur accepte n'importe quel IEnumerable<T> et empile ses éléments dans l'ordre, et une pile s'énumère sommet d'abord, donc l'ancien sommet se retrouve au fond de la copie. Inverser d'abord la séquence (le Reverse() de LINQ renvoie les éléments en partant du fond) donne une copie avec le même sommet.

Empiler une liste d'éléments sur une nouvelle pile les inverse aussi, ce qui est une façon rapide d'inverser une séquence : new Stack<char>("hello") restitue o, l, l, e, h au dépilage.

Exemple : un historique d'annulation

Les éditeurs gardent chaque modification sur une pile. Annuler dépile la modification la plus récente et la défait ; rétablir garde une seconde pile des modifications annulées.

using System;
using System.Collections.Generic;

class Editor
{
    private string text = "";
    private readonly Stack<string> undo = new Stack<string>();
    private readonly Stack<string> redo = new Stack<string>();

    public void Type(string s)
    {
        undo.Push(text);   // remember the state before the change
        redo.Clear();      // a new change invalidates the redo history
        text += s;
    }

    public void Undo()
    {
        if (undo.Count == 0) return;
        redo.Push(text);
        text = undo.Pop();
    }

    public void Redo()
    {
        if (redo.Count == 0) return;
        undo.Push(text);
        text = redo.Pop();
    }

    public string Text { get { return text; } }
}

class Program
{
    static void Main()
    {
        var ed = new Editor();
        ed.Type("Hello");
        ed.Type(", world");
        ed.Type("!");
        Console.WriteLine(ed.Text);

        ed.Undo();
        Console.WriteLine(ed.Text);
        ed.Undo();
        Console.WriteLine(ed.Text);

        ed.Redo();
        Console.WriteLine(ed.Text);
    }
}

Sortie :

Hello, world!
Hello, world
Hello
Hello, world

Stocker des instantanés complets est la version la plus simple. Les vrais éditeurs empilent plutôt de petits objets commande (ce qui a été inséré, et où), chacun avec une méthode pour s'annuler, mais les deux piles fonctionnent de la même façon.

Exemple : les parenthèses équilibrées

Vérifier que (, [ et { sont refermés dans le bon ordre est l'exercice de pile classique, et la même logique se trouve au cœur de chaque compilateur et de chaque analyseur JSON.

using System;
using System.Collections.Generic;

class Program
{
    static bool IsBalanced(string s)
    {
        var open = new Stack<char>();
        foreach (char c in s)
        {
            if (c == '(' || c == '[' || c == '{')
            {
                open.Push(c);
            }
            else if (c == ')' || c == ']' || c == '}')
            {
                if (open.Count == 0) return false;          // closer with no opener
                char top = open.Pop();
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) return false; // wrong kind
            }
        }
        return open.Count == 0;                             // leftovers are unclosed
    }

    static void Main()
    {
        string[] inputs = { "f(a[i], {x: 1})", "(]", "((a)", "a)b(", "" };
        foreach (string input in inputs)
        {
            Console.WriteLine("\"" + input + "\" -> " + IsBalanced(input));
        }
    }
}

Sortie :

"f(a[i], {x: 1})" -> True
"(]" -> False
"((a)" -> False
"a)b(" -> False
"" -> True

Les trois tests d'échec correspondent aux trois façons dont les parenthèses peuvent être incorrectes : une fermante sans ouvrante (a)b(, détectée par Count == 0 au lieu d'une exception de Pop), une fermante du mauvais type ((]), et des ouvrantes jamais refermées (((a), détectées par le test final).

Autres usages

Parcours en profondeur. Remplacez la file d'un parcours en largeur par une pile, et le parcours va en profondeur avant d'aller en largeur. Une pile explicite remplace aussi la récursivité quand l'entrée est assez profonde pour risquer une StackOverflowException, qui ne peut pas être interceptée.
Évaluer des expressions. La notation postfixée (3 4 + 2 *) s'évalue en empilant les nombres et en en dépilant deux pour chaque opérateur.
Retour arrière. L'historique de navigation, la résolution de labyrinthes et les états d'un analyseur empilent une position et y reviennent en dépilant face à une impasse.

Voir Queue pour son pendant premier entré, premier sorti.

Stack, Queue ou List

	`Stack<T>`	`Queue<T>`	`List<T>`
Ordre de sortie	Le plus récent d'abord	Le plus ancien d'abord	Quelconque, par index
Ajouter	`Push`	`Enqueue`	`Add`, `Insert`
Retirer	`Pop` (sommet)	`Dequeue` (tête)	`Remove`, `RemoveAt`
Consulter	`Peek`	`Peek`	`list[i]`
Variantes sûres	`TryPop`, `TryPeek`	`TryDequeue`, `TryPeek`	inutiles

Pour plusieurs threads, ConcurrentStack<T> dans System.Collections.Concurrent propose Push, TryPop et TryPeek sans verrou.

Erreurs courantes

Dépiler sans vérifier. Une pile vide lève InvalidOperationException ; vérifiez Count ou utilisez TryPop.
S'attendre à ce que foreach parte du premier élément empilé. Il part du sommet.
Copier avec new Stack<T>(stack). La copie est inversée.
Empiler dans un foreach sur la même pile. Cela lève une exception ; utilisez une boucle while (stack.Count > 0).

Questions fréquentes

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

Stack<T>, dans System.Collections.Generic, est une collection dernier entré, premier sorti (LIFO). Push pose un élément au sommet, Pop retire et renvoie l'élément du sommet, et Peek renvoie l'élément du sommet sans le retirer. Les trois s'exécutent en temps constant.

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

Pop et Peek lèvent InvalidOperationException quand la pile est vide. Vérifiez d'abord stack.Count > 0, ou utilisez TryPop(out var item) et TryPeek(out var item), qui renvoient false au lieu de lever une exception (.NET Core 2.0 et plus).

Dans quel ordre foreach parcourt-il une Stack ?

Du sommet vers le bas : l'élément empilé le plus récemment vient en premier, dans l'ordre où Pop les renverrait. ToArray() utilise le même ordre. Une conséquence est que new Stack<T>(otherStack) produit une copie inversée, car le constructeur empile les éléments dans l'ordre où il les énumère.

Quelle est la différence entre une Stack et une Queue en C# ?

Une Stack<T> renvoie d'abord l'élément le plus récent (dernier entré, premier sorti), tandis qu'une Queue<T> renvoie d'abord le plus ancien (premier entré, premier sorti). Utilisez une pile pour un historique d'annulation, les structures imbriquées et le parcours en profondeur ; utilisez une file pour traiter le travail dans l'ordre d'arrivée et pour le parcours en largeur.

Comment vérifier que des parenthèses sont équilibrées en C# ?

Parcourez la chaîne une fois. Empilez chaque parenthèse ouvrante sur une Stack<char>. Pour chaque parenthèse fermante, la pile doit être non vide et son sommet doit être l'ouvrante correspondante, que vous dépilez alors. La chaîne est équilibrée si la pile est vide à la fin du parcours.

Concepts liés