Stos Stack w C#: Push, Pop, Peek, cofanie i sprawdzanie nawiasów

Stack<T> to stos: kładziesz elementy na wierzch za pomocą Push i zdejmujesz je z wierzchu za pomocą Pop, więc ostatni włożony element wychodzi pierwszy (LIFO). Dostępny jest tylko wierzch, a każda operacja na nim działa w czasie stałym.

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

Wynik:

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

green został włożony jako ostatni, więc wychodzi pierwszy. Peek zwraca wierzch bez zmiany stosu; w ten sposób sprawdzasz, co dałby ci Pop, zanim zdecydujesz się to zdjąć.

Wyjątek pustego stosu i TryPop

Zdejmowanie z pustego stosu albo podglądanie go rzuca InvalidOperationException. Najczęściej zdarza się to w parserach i algorytmach, które dostają dane z większą liczbą elementów zamykających niż otwierających.

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

Wynik:

Caught InvalidOperationException
True 10
False 0

TryPop i TryPeek (.NET Core 2.0 i nowsze) zwracają false na pustym stosie i ustawiają zmienną out na wartość domyślną, tutaj 0. W .NET Framework najpierw sprawdź Count > 0.

Kolejność iteracji: najpierw wierzch

Przeglądanie stosu niczego nie usuwa i przebiega od wierzchu w dół, w kolejności, w jakiej zwracałby elementy Pop:

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

Wynik:

checkout products home 
checkout > products > home
True
home
checkout

Odwrócona kopia potrafi zaskoczyć: konstruktor przyjmuje dowolne IEnumerable<T> i wkłada jego elementy po kolei, a stos jest przeglądany od wierzchu, więc stary wierzch ląduje na dnie kopii. Wcześniejsze odwrócenie sekwencji (Reverse() z LINQ zwraca elementy od dna) daje kopię z tym samym wierzchem.

Włożenie listy elementów na nowy stos również je odwraca, co jest szybkim sposobem na odwrócenie sekwencji: new Stack<char>("hello") oddaje przy zdejmowaniu o, l, l, e, h.

Przykład: historia cofania

Edytory trzymają każdą zmianę na stosie. Cofnięcie zdejmuje najnowszą zmianę i ją odwraca; ponowienie korzysta z drugiego stosu cofniętych zmian.

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

Wynik:

Hello, world!
Hello, world
Hello
Hello, world

Zapisywanie całych migawek to najprostsza wersja. Prawdziwe edytory wkładają zamiast tego małe obiekty poleceń (co wstawiono i gdzie), z których każdy ma metodę odwracającą samego siebie, ale oba stosy działają tak samo.

Przykład: zbalansowane nawiasy

Sprawdzenie, czy (, [ i { są zamykane we właściwej kolejności, to standardowe ćwiczenie ze stosem, a ta sama logika siedzi w każdym kompilatorze i parserze 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));
        }
    }
}

Wynik:

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

Trzy sprawdzenia błędów odpowiadają trzem sposobom, w jakie nawiasy mogą się zepsuć: nawias zamykający bez otwartego (a)b(, wyłapany przez Count == 0 zamiast wyjątku z Pop), nawias zamykający złego rodzaju ((]) oraz nawiasy otwierające, których nigdy nie zamknięto (((a), wyłapane przez końcowe sprawdzenie).

Inne zastosowania

• Przeszukiwanie w głąb. Zamień kolejkę w przeszukiwaniu wszerz na stos, a przejście najpierw pójdzie w głąb, a dopiero potem wszerz. Jawny stos zastępuje też rekurencję, gdy dane są na tyle głębokie, że grożą StackOverflowException, którego nie da się przechwycić.
• Obliczanie wyrażeń. Notację postfiksową (3 4 + 2 *) oblicza się, wkładając liczby na stos i zdejmując dwie przy każdym operatorze.
• Nawroty (backtracking). Historia nawigacji, rozwiązywanie labiryntów i stany parsera wkładają pozycję na stos i wracają do niej w ślepym zaułku.

Odpowiednik typu first in, first out opisuje strona o Queue.

Stack a Queue a List

Dla wielu wątków ConcurrentStack<T> z System.Collections.Concurrent oferuje Push, TryPop i TryPeek bez blokad.

Typowe błędy

• Zdejmowanie bez sprawdzenia. Pusty stos rzuca InvalidOperationException; sprawdź Count albo użyj TryPop.
• Oczekiwanie, że foreach zacznie od pierwszego włożonego elementu. Zaczyna od wierzchu.
• Kopiowanie przez new Stack<T>(stack). Kopia jest odwrócona.
• Wkładanie elementów wewnątrz foreach po tym samym stosie. Rzuca wyjątek; użyj pętli while (stack.Count > 0).