Stack em C#: Push, Pop, Peek, desfazer e balanceamento de parênteses

Uma Stack<T> é uma pilha: você coloca itens no topo com Push e os tira do topo com Pop, então o último item a entrar é o primeiro a sair (LIFO). Só o topo é alcançável, e toda operação sobre ele leva tempo constante.

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

Saída:

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

green foi empilhado por último, então sai primeiro. Peek retorna o topo sem mudar a pilha, e é assim que você inspeciona o que o Pop devolveria antes de decidir retirá-lo.

A exceção da pilha vazia e o TryPop

Fazer pop ou peek em uma pilha vazia lança InvalidOperationException. Isso aparece com mais frequência em parsers e algoritmos que recebem uma entrada com mais itens de fechamento que de abertura.

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

Saída:

Caught InvalidOperationException
True 10
False 0

TryPop e TryPeek (.NET Core 2.0 em diante) retornam false em uma pilha vazia e definem a variável out com o valor padrão, 0 aqui. No .NET Framework, verifique Count > 0 antes.

Ordem de iteração: o topo primeiro

Enumerar uma pilha não remove nada, e vai do topo para baixo, na ordem em que o Pop devolveria os itens:

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

Saída:

checkout products home 
checkout > products > home
True
home
checkout

A cópia invertida pega muita gente de surpresa: o construtor recebe qualquer IEnumerable<T> e empilha os itens em ordem, e uma pilha é enumerada a partir do topo, então o topo antigo acaba no fundo da cópia. Inverter a sequência antes (o Reverse() do LINQ devolve os itens a partir do fundo) gera uma cópia com o mesmo topo.

Empilhar uma lista de itens em uma pilha nova também os inverte, o que é um jeito rápido de inverter uma sequência: new Stack<char>("hello") devolve no pop o, l, l, e, h.

Exemplo: um histórico de desfazer

Editores guardam cada mudança em uma pilha. Desfazer tira a mudança mais recente e a reverte; refazer mantém uma segunda pilha com as mudanças desfeitas.

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

Saída:

Hello, world!
Hello, world
Hello
Hello, world

Guardar cópias inteiras do estado é a versão mais simples. Editores reais empilham pequenos objetos de comando (o que foi inserido e onde), cada um com um método para se reverter, mas as duas pilhas funcionam do mesmo jeito.

Exemplo: parênteses balanceados

Verificar se (, [ e { são fechados na ordem certa é o exercício clássico de pilha, e a mesma lógica está dentro de todo compilador e parser de 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));
        }
    }
}

Saída:

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

As três verificações de falha correspondem às três formas de os símbolos darem errado: um fechamento sem nada aberto (a)b(, pego por Count == 0 em vez de uma exceção do Pop), um fechamento do tipo errado ((]) e aberturas nunca fechadas (((a), pegas pela verificação final).

Outros usos

• Busca em profundidade. Troque a fila de uma busca em largura por uma pilha e o percurso vai fundo antes de ir para os lados. Uma pilha explícita também substitui a recursão quando a entrada é profunda o bastante para arriscar uma StackOverflowException, que não pode ser capturada.
• Avaliar expressões. A notação pós-fixa (3 4 + 2 *) é avaliada empilhando números e desempilhando dois para cada operador.
• Backtracking. Histórico de navegação, resolução de labirintos e estados de parser empilham uma posição e voltam para ela ao chegar a um beco sem saída.

Veja Queue para a contraparte em que o primeiro a entrar é o primeiro a sair.

Stack vs Queue vs List

Para várias threads, ConcurrentStack<T> em System.Collections.Concurrent oferece Push, TryPop e TryPeek sem locks.

Erros comuns

• Fazer Pop sem verificar. Uma pilha vazia lança InvalidOperationException; verifique Count ou use TryPop.
• Esperar que o foreach comece pelo primeiro item empilhado. Ele começa pelo topo.
• Copiar com new Stack<T>(stack). A cópia fica invertida.
• Empilhar dentro de um foreach sobre a mesma pilha. Lança exceção; use um laço while (stack.Count > 0).