Stack в C#: Push, Pop, Peek, отмена действий и проверка скобок

Stack<T> это стопка: вы кладёте элементы наверх через Push и снимаете их сверху через Pop, поэтому последний положенный элемент выходит первым (LIFO). Доступна только вершина, и каждая операция с ней выполняется за постоянное время.

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

Вывод:

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

green положили последним, поэтому он снимается первым. Peek возвращает вершину, не меняя стек; так можно посмотреть, что даст Pop, прежде чем решить, забирать ли элемент.

Исключение пустого стека и TryPop

Извлечение или просмотр вершины пустого стека выбрасывает InvalidOperationException. Чаще всего это случается в парсерах и алгоритмах, получивших на вход больше закрывающих элементов, чем открывающих.

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

Вывод:

Caught InvalidOperationException
True 10
False 0

TryPop и TryPeek (.NET Core 2.0 и новее) возвращают false для пустого стека и задают переменной out значение по умолчанию, здесь 0. В .NET Framework сначала проверяйте Count > 0.

Порядок перебора: сначала вершина

Перебор стека ничего не удаляет и идёт сверху вниз, в том порядке, в каком элементы вернул бы 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());
    }
}

Вывод:

checkout products home 
checkout > products > home
True
home
checkout

Перевёрнутая копия многих застаёт врасплох: конструктор принимает любой IEnumerable<T> и кладёт его элементы по порядку, а стек перебирается с вершины, поэтому старая вершина оказывается на дне копии. Если сначала перевернуть последовательность (Reverse() из LINQ возвращает элементы начиная со дна), получится копия с той же вершиной.

Если положить список элементов в новый стек, они тоже перевернутся, и это быстрый способ перевернуть последовательность: new Stack<char>("hello") отдаёт обратно o, l, l, e, h.

Пример: история отмены

Редакторы кладут каждое изменение в стек. Отмена извлекает последнее изменение и откатывает его; повтор хранит второй стек отменённых изменений.

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

Вывод:

Hello, world!
Hello, world
Hello
Hello, world

Хранение целых снимков это самый простой вариант. Настоящие редакторы вместо этого кладут небольшие объекты-команды (что вставлено и куда), у каждого из которых есть метод для отката, но два стека работают так же.

Пример: сбалансированные скобки

Проверка, что (, [ и { закрыты в правильном порядке, это стандартное упражнение на стек, и та же логика работает внутри каждого компилятора и 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));
        }
    }
}

Вывод:

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

Три проверки на ошибку соответствуют трём способам, которыми скобки могут быть нарушены: закрывающая скобка без открытой (a)b(, её ловит Count == 0, а не исключение из Pop), закрывающая скобка не того вида ((]) и открывающие скобки, которые так и не закрыли (((a), их ловит финальная проверка).

Другие применения

• Поиск в глубину. Замените очередь в поиске в ширину на стек, и обход пойдёт вглубь, а не вширь. Явный стек также заменяет рекурсию, когда входные данные достаточно глубоки, чтобы рисковать StackOverflowException, который нельзя перехватить.
• Вычисление выражений. Постфиксная запись (3 4 + 2 *) вычисляется так: числа кладутся в стек, а для каждого оператора извлекаются два числа.
• Возврат с отменой (backtracking). История навигации, прохождение лабиринта и состояния парсера кладут позицию в стек и возвращаются к ней в тупике.

Аналог «первым пришёл, первым вышел» описан на странице Queue.

Stack, Queue или List

Для нескольких потоков ConcurrentStack<T> из System.Collections.Concurrent предлагает Push, TryPop и TryPeek без блокировок.

Частые ошибки

• Извлечение без проверки. Пустой стек выбрасывает InvalidOperationException; проверяйте Count или используйте TryPop.
• Ожидание, что foreach начнёт с первого положенного элемента. Он начинает с вершины.
• Копирование через new Stack<T>(stack). Копия получается перевёрнутой.
• Добавление внутри foreach по тому же стеку. Выбрасывает исключение; используйте цикл while (stack.Count > 0).