Ausführbare C#-Docs: Stack

Q: Was ist ein Stack in C#?

Stack in System.Collections.Generic ist eine Collection nach dem Prinzip last in, first out (LIFO). Push legt ein Element oben ab, Pop entfernt das oberste Element und gibt es zurück, und Peek gibt das oberste Element zurück, ohne es zu entfernen. Alle drei laufen in konstanter Zeit.

Q: Was passiert in C# bei Pop auf einem leeren Stack?

Pop und Peek werfen InvalidOperationException, wenn der Stack leer ist. Prüfe vorher stack.Count > 0 oder nimm TryPop(out var item) und TryPeek(out var item), die stattdessen false zurückgeben (ab .NET Core 2.0).

Q: Was ist der Unterschied zwischen einem Stack und einer Queue in C#?

Ein Stack gibt das neueste Element zuerst zurück (last in, first out), eine Queue das älteste (first in, first out). Nimm einen Stack für Undo-Historien, verschachtelte Strukturen und Tiefensuche; nimm eine Queue, um Arbeit in der Reihenfolge des Eintreffens abzuarbeiten, und für die Breitensuche.

Ein Stack<T> ist ein Stapel: Du legst Elemente mit Push oben ab und nimmst sie mit Pop oben wieder weg, das zuletzt hineingelegte Element kommt also zuerst heraus (LIFO). Nur das oberste Element ist erreichbar, und jede Operation darauf braucht konstante Zeit.

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

Ausgabe:

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

green wurde zuletzt abgelegt und kommt daher zuerst heraus. Peek gibt das oberste Element zurück, ohne den Stack zu ändern. So siehst du nach, was Pop liefern würde, bevor du dich entscheidest, es zu nehmen.

Die Exception bei leerem Stack und TryPop

Pop oder Peek auf einem leeren Stack wirft InvalidOperationException. Das passiert am häufigsten in Parsern und Algorithmen, deren Eingabe mehr schließende als öffnende Elemente hat.

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

Ausgabe:

Caught InvalidOperationException
True 10
False 0

TryPop und TryPeek (ab .NET Core 2.0) geben bei leerem Stack false zurück und setzen die out-Variable auf den Standardwert, hier 0. Unter .NET Framework prüfe vorher Count > 0.

Reihenfolge beim Durchlaufen: oben zuerst

Einen Stack zu durchlaufen entfernt nichts, und es geht von oben nach unten, in der Reihenfolge, in der Pop die Elemente zurückgeben würde:

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

Ausgabe:

checkout products home 
checkout > products > home
True
home
checkout

Die umgekehrte Kopie erwischt Leute: Der Konstruktor nimmt ein beliebiges IEnumerable<T> und legt seine Elemente der Reihe nach ab, und ein Stack wird oben zuerst durchlaufen, das alte oberste Element landet in der Kopie also unten. Die Sequenz vorher umzukehren (Reverse() aus LINQ liefert die Elemente von unten zuerst) ergibt eine Kopie mit demselben obersten Element.

Eine Liste von Elementen auf einen neuen Stack zu legen kehrt sie ebenfalls um, was ein schneller Weg ist, eine Sequenz umzukehren: new Stack<char>("hello") gibt per Pop o, l, l, e, h zurück.

Beispiel: eine Undo-Historie

Editoren legen jede Änderung auf einen Stack. Undo nimmt die letzte Änderung per Pop herunter und macht sie rückgängig; Redo führt einen zweiten Stack mit rückgängig gemachten Änderungen.

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

Ausgabe:

Hello, world!
Hello, world
Hello
Hello, world

Ganze Momentaufnahmen zu speichern ist die einfachste Version. Echte Editoren legen stattdessen kleine Befehlsobjekte ab (was wo eingefügt wurde), jedes mit einer Methode, sich selbst rückgängig zu machen, aber die beiden Stacks funktionieren genauso.

Beispiel: ausgeglichene Klammern

Zu prüfen, dass (, [ und { in der richtigen Reihenfolge geschlossen werden, ist die Standardübung für Stacks, und dieselbe Logik steckt in jedem Compiler und JSON-Parser.

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

Ausgabe:

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

Die drei Fehlerprüfungen entsprechen den drei Arten, wie Klammern falsch sein können: eine schließende Klammer ohne offene (a)b(, erkannt durch Count == 0 statt durch eine Exception von Pop), eine schließende Klammer der falschen Art ((]) und öffnende Klammern, die nie geschlossen werden (((a), erkannt durch die abschließende Prüfung).

Weitere Einsätze

Tiefensuche. Ersetze die Queue einer Breitensuche durch einen Stack, und die Durchquerung geht erst in die Tiefe, dann in die Breite. Ein expliziter Stack ersetzt auch Rekursion, wenn die Eingabe tief genug ist, um eine StackOverflowException zu riskieren, die sich nicht abfangen lässt.
Ausdrücke auswerten. Postfix-Notation (3 4 + 2 *) wird ausgewertet, indem Zahlen abgelegt und für jeden Operator zwei per Pop genommen werden.
Backtracking. Navigationsverlauf, Labyrinthlösung und Parserzustände legen eine Position ab und kehren in einer Sackgasse per Pop zu ihr zurück.

Das Gegenstück nach dem Prinzip first in, first out findest du unter Queue.

Stack gegenüber Queue gegenüber List

	`Stack<T>`	`Queue<T>`	`List<T>`
Reihenfolge beim Herausnehmen	Neuestes zuerst	Ältestes zuerst	Beliebig, per Index
Hinzufügen	`Push`	`Enqueue`	`Add`, `Insert`
Entfernen	`Pop` (oben)	`Dequeue` (vorn)	`Remove`, `RemoveAt`
Ansehen	`Peek`	`Peek`	`list[i]`
Sichere Varianten	`TryPop`, `TryPeek`	`TryDequeue`, `TryPeek`	nicht nötig

Für mehrere Threads bietet ConcurrentStack<T> in System.Collections.Concurrent die Methoden Push, TryPop und TryPeek ohne Locks.

Häufige Fehler

Pop ohne Prüfung. Ein leerer Stack wirft InvalidOperationException; prüfe Count oder nimm TryPop.
Erwarten, dass foreach beim zuerst abgelegten Element beginnt. Es beginnt oben.
Mit new Stack<T>(stack) kopieren. Die Kopie ist umgekehrt.
In foreach über denselben Stack ablegen. Wirft; nimm eine Schleife while (stack.Count > 0).

Häufig gestellte Fragen

Was ist ein Stack in C#?

Stack<T> in System.Collections.Generic ist eine Collection nach dem Prinzip last in, first out (LIFO). Push legt ein Element oben ab, Pop entfernt das oberste Element und gibt es zurück, und Peek gibt das oberste Element zurück, ohne es zu entfernen. Alle drei laufen in konstanter Zeit.

Was passiert in C# bei Pop auf einem leeren Stack?

Pop und Peek werfen InvalidOperationException, wenn der Stack leer ist. Prüfe vorher stack.Count > 0 oder nimm TryPop(out var item) und TryPeek(out var item), die stattdessen false zurückgeben (ab .NET Core 2.0).

In welcher Reihenfolge durchläuft foreach einen Stack?

Von oben nach unten: Das zuletzt abgelegte Element kommt zuerst, in derselben Reihenfolge, in der Pop sie zurückgeben würde. ToArray() verwendet dieselbe Reihenfolge. Eine Folge davon: new Stack<T>(otherStack) erzeugt eine umgekehrte Kopie, weil der Konstruktor die Elemente in der Reihenfolge ablegt, in der er sie durchläuft.

Was ist der Unterschied zwischen einem Stack und einer Queue in C#?

Ein Stack<T> gibt das neueste Element zuerst zurück (last in, first out), eine Queue<T> das älteste (first in, first out). Nimm einen Stack für Undo-Historien, verschachtelte Strukturen und Tiefensuche; nimm eine Queue, um Arbeit in der Reihenfolge des Eintreffens abzuarbeiten, und für die Breitensuche.

Wie prüfe ich in C# ausgeglichene Klammern?

Durchlaufe den String einmal. Lege jede öffnende Klammer auf einen Stack<char>. Bei jeder schließenden Klammer muss der Stack nicht leer sein, und sein oberstes Element muss die passende öffnende Klammer sein, die du dann mit Pop entfernst. Der String ist ausgeglichen, wenn der Durchlauf mit leerem Stack endet.

Verwandte Konzepte