C# Stack: Push, Pop, Peek, Undo and Bracket Matching

A Stack<T> is a pile: you put items on top with Push and take them off the top with Pop, so the last item in is the first one out (LIFO). Only the top is reachable, and every operation on it takes constant time.

Push, Pop and 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 was pushed last, so it comes off first. Peek returns the top without changing the stack, which is how you inspect what Pop would give you before deciding to take it.

The empty stack exception and TryPop

Popping or peeking at an empty stack throws InvalidOperationException. This shows up most often in parsers and algorithms fed with input that has more closing items than opening ones.

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 and TryPeek (.NET Core 2.0 and later) return false on an empty stack and set the out variable to the default value, 0 here. On .NET Framework, check Count > 0 first.

Iteration order: top first

Enumerating a stack does not remove anything, and it goes from the top down, in the order Pop would return the items:

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

The reversed copy catches people out: the constructor takes any IEnumerable<T> and pushes its items in order, and a stack enumerates top first, so the old top ends up at the bottom of the copy. Reversing the sequence first (LINQ's Reverse() returns the items bottom first) gives a copy with the same top.

Pushing a list of items onto a new stack also reverses them, which is a quick way to reverse a sequence: new Stack<char>("hello") pops back o, l, l, e, h.

Example: an undo history

Editors keep every change on a stack. Undo pops the most recent change and reverts it; redo keeps a second stack of undone changes.

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

Storing whole snapshots is the simplest version. Real editors push small command objects instead (what was inserted, and where), each with a method to reverse itself, but the two stacks work the same way.

Example: balanced brackets

Checking that (, [ and { are closed in the right order is the standard stack exercise, and the same logic sits inside every compiler and 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));
        }
    }
}

Output:

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

The three failure checks correspond to the three ways brackets go wrong: a closer with nothing open (a)b(, caught by Count == 0 instead of an exception from Pop), a closer of the wrong kind ((]), and openers never closed (((a), caught by the final check).

Other uses

• Depth first search. Replace the queue in a breadth first search with a stack and the traversal goes deep before wide. An explicit stack also replaces recursion when the input is deep enough to risk a StackOverflowException, which cannot be caught.
• Evaluating expressions. Postfix notation (3 4 + 2 *) is evaluated by pushing numbers and popping two for each operator.
• Backtracking. Navigation history, maze solving and parser states push a position and pop back to it on a dead end.

See Queue for the first in, first out counterpart.

Stack vs Queue vs List

For several threads, ConcurrentStack<T> in System.Collections.Concurrent offers Push, TryPop and TryPeek without locks.

Common mistakes

• Popping without checking. An empty stack throws InvalidOperationException; check Count or use TryPop.
• Expecting foreach to go from the first item pushed. It goes from the top.
• Copying with new Stack<T>(stack). The copy is reversed.
• Pushing inside foreach over the same stack. Throws; use a while (stack.Count > 0) loop.