Guida C# interattiva: Stack

Q: Cos'è uno Stack in C#?

Stack in System.Collections.Generic è una collezione last in, first out (LIFO). Push mette un elemento in cima, Pop rimuove e restituisce l'elemento in cima, e Peek restituisce l'elemento in cima senza rimuoverlo. Tutte e tre vengono eseguite in tempo costante.

Q: Cosa succede se fai Pop su uno stack vuoto in C#?

Pop e Peek lanciano InvalidOperationException quando lo stack è vuoto. Controlla prima stack.Count > 0, oppure usa TryPop(out var item) e TryPeek(out var item), che restituiscono false invece di lanciare un'eccezione (.NET Core 2.0 e successivi).

Q: Che differenza c'è tra uno Stack e una Queue in C#?

Uno Stack restituisce per primo l'elemento più recente (last in, first out), mentre una Queue restituisce per primo quello più vecchio (first in, first out). Usa uno stack per la cronologia di annullamento, le strutture annidate e la ricerca in profondità; usa una coda per elaborare il lavoro in ordine di arrivo e per la ricerca in ampiezza.

Uno Stack<T> è una pila: metti gli elementi in cima con Push e li togli dalla cima con Pop, quindi l'ultimo elemento entrato è il primo a uscire (LIFO). Si può raggiungere solo la cima, e ogni operazione su di essa richiede tempo costante.

Push, Pop e 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);
    }
}

Output:

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

green è stato inserito per ultimo, quindi esce per primo. Peek restituisce la cima senza modificare la pila, ed è così che controlli cosa ti darebbe Pop prima di decidere di prenderlo.

L'eccezione della pila vuota e TryPop

Estrarre o guardare la cima di una pila vuota lancia InvalidOperationException. Succede soprattutto nei parser e negli algoritmi che ricevono un input con più elementi di chiusura che di apertura.

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

Output:

Caught InvalidOperationException
True 10
False 0

TryPop e TryPeek (.NET Core 2.0 e successivi) restituiscono false su una pila vuota e impostano la variabile out al valore predefinito, qui 0. Su .NET Framework, controlla prima Count > 0.

Ordine di iterazione: prima la cima

Enumerare una pila non rimuove nulla, e procede dalla cima verso il basso, nell'ordine in cui Pop restituirebbe gli elementi:

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

Output:

checkout products home 
checkout > products > home
True
home
checkout

La copia invertita coglie molti di sorpresa: il costruttore accetta qualsiasi IEnumerable<T> e ne inserisce gli elementi in ordine, e una pila si enumera partendo dalla cima, quindi la vecchia cima finisce in fondo alla copia. Invertire prima la sequenza (il Reverse() di LINQ restituisce gli elementi partendo dal fondo) dà una copia con la stessa cima.

Anche inserire una lista di elementi in una nuova pila li inverte, il che è un modo rapido per invertire una sequenza: new Stack<char>("hello") restituisce con Pop o, l, l, e, h.

Esempio: una cronologia di annullamento

Gli editor tengono ogni modifica in una pila. Annulla estrae la modifica più recente e la ripristina; ripeti usa una seconda pila con le modifiche annullate.

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

Output:

Hello, world!
Hello, world
Hello
Hello, world

Memorizzare istantanee complete è la versione più semplice. Gli editor veri inseriscono invece piccoli oggetti comando (cosa è stato inserito, e dove), ognuno con un metodo per annullare se stesso, ma le due pile funzionano allo stesso modo.

Esempio: parentesi bilanciate

Verificare che (, [ e { vengano chiuse nell'ordine giusto è l'esercizio standard sulle pile, e la stessa logica si trova dentro ogni compilatore e parser 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));
        }
    }
}

Output:

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

I tre controlli di fallimento corrispondono ai tre modi in cui le parentesi possono essere sbagliate: una chiusura senza nulla di aperto (a)b(, intercettata da Count == 0 invece che da un'eccezione di Pop), una chiusura del tipo sbagliato ((]) e aperture mai chiuse (((a), intercettate dal controllo finale).

Altri usi

Ricerca in profondità. Sostituisci la coda di una ricerca in ampiezza con una pila e la visita va in profondità prima che in larghezza. Una pila esplicita sostituisce anche la ricorsione quando l'input è abbastanza profondo da rischiare una StackOverflowException, che non si può catturare.
Valutare espressioni. La notazione postfissa (3 4 + 2 *) si valuta inserendo i numeri ed estraendone due per ogni operatore.
Backtracking. La cronologia di navigazione, la risoluzione di labirinti e gli stati di un parser inseriscono una posizione e tornano indietro a essa quando arrivano a un vicolo cieco.

Vedi Queue per la controparte first in, first out.

Stack, Queue e List a confronto

	`Stack<T>`	`Queue<T>`	`List<T>`
Ordine di uscita	Prima il più recente	Prima il più vecchio	Qualsiasi, per indice
Aggiungere	`Push`	`Enqueue`	`Add`, `Insert`
Rimuovere	`Pop` (cima)	`Dequeue` (testa)	`Remove`, `RemoveAt`
Guardare	`Peek`	`Peek`	`list[i]`
Varianti sicure	`TryPop`, `TryPeek`	`TryDequeue`, `TryPeek`	non necessarie

Per più thread, ConcurrentStack<T> di System.Collections.Concurrent offre Push, TryPop e TryPeek senza lock.

Errori comuni

Estrarre senza controllare. Una pila vuota lancia InvalidOperationException; controlla Count o usa TryPop.
Aspettarsi che foreach parta dal primo elemento inserito. Parte dalla cima.
Copiare con new Stack<T>(stack). La copia è invertita.
Inserire dentro un foreach sulla stessa pila. Lancia un'eccezione; usa un ciclo while (stack.Count > 0).

Domande frequenti

Cos'è uno Stack in C#?

Stack<T> in System.Collections.Generic è una collezione last in, first out (LIFO). Push mette un elemento in cima, Pop rimuove e restituisce l'elemento in cima, e Peek restituisce l'elemento in cima senza rimuoverlo. Tutte e tre vengono eseguite in tempo costante.

Cosa succede se fai Pop su uno stack vuoto in C#?

Pop e Peek lanciano InvalidOperationException quando lo stack è vuoto. Controlla prima stack.Count > 0, oppure usa TryPop(out var item) e TryPeek(out var item), che restituiscono false invece di lanciare un'eccezione (.NET Core 2.0 e successivi).

In che ordine foreach percorre uno Stack?

Dalla cima verso il basso: per primo viene l'elemento inserito più di recente, nello stesso ordine in cui li restituirebbe Pop. ToArray() usa lo stesso ordine. Una conseguenza è che new Stack<T>(otherStack) produce una copia invertita, perché il costruttore inserisce gli elementi nell'ordine in cui li enumera.

Che differenza c'è tra uno Stack e una Queue in C#?

Uno Stack<T> restituisce per primo l'elemento più recente (last in, first out), mentre una Queue<T> restituisce per primo quello più vecchio (first in, first out). Usa uno stack per la cronologia di annullamento, le strutture annidate e la ricerca in profondità; usa una coda per elaborare il lavoro in ordine di arrivo e per la ricerca in ampiezza.

Come controllo se le parentesi sono bilanciate in C#?

Scorri la stringa una volta. Inserisci ogni parentesi di apertura in uno Stack<char>. Per ogni parentesi di chiusura, lo stack non deve essere vuoto e la sua cima deve essere la parentesi di apertura corrispondente, che a quel punto estrai. La stringa è bilanciata quando la scansione termina con lo stack vuoto.

Concetti correlati