C# Stack<T> (Pilha)

O Ctrl+Z desfaz a última coisa que você fez. Apertando de novo, desfaz a penúltima, e assim por diante: sempre da mais nova para a mais antiga. O botão Voltar do navegador funciona igual. Por trás dos dois existe uma pilha, e no C# ela se chama Stack<T>. É a irmã da fila, com a regra ao contrário.

Todos os programas desta aula rodaram com o .NET 10 na máquina da Ana (usuária ana, computador notebook), na pasta ~/cs, com dotnet run arquivo.cs. Você pode repetir cada um no editor do guia.

A ideia: uma pilha de pratos

Na pia da Ana, os pratos sujos vão sendo colocados um em cima do outro. Para lavar, ela pega o de cima: o último que chegou. Pegar o prato de baixo derrubaria todos.

     entra e sai por aqui
            ↓↑
     [ prato branco ]   ← topo (o último que entrou)
     [ prato verde  ]
     [ prato azul   ]   ← base (o primeiro que entrou)

Essa regra é a LIFO, de Last In, First Out: "o último a entrar é o primeiro a sair". Compare com a fila (FIFO), em que sai o primeiro que chegou. Numa pilha você só mexe no topo:

1. Empilhar, espiar e desempilhar

var pilha = new Stack<string>();

pilha.Push("prato azul");
pilha.Push("prato verde");
pilha.Push("prato branco");
Console.WriteLine($"Pratos: {pilha.Count}");

Console.WriteLine($"No topo: {pilha.Peek()}");

string lavado = pilha.Pop();
Console.WriteLine($"Lavei o {lavado}");
Console.WriteLine($"No topo: {pilha.Peek()}");
Console.WriteLine($"Pratos: {pilha.Count}");

new Stack<string>()

Cria uma pilha vazia de textos. O T é o tipo do que vai na pilha (veja Generics).

pilha.Push("prato azul");

Põe o prato azul no topo. Como a pilha estava vazia, ele fica também na base.

pilha.Push("prato branco");

O último Push: o prato branco é o novo topo.

pilha.Peek()

Devolve o topo, sem tirar.

string lavado = pilha.Pop();

Tira o topo e devolve. O prato verde passa a ser o topo.

$ dotnet run pratos.cs
Pratos: 3
No topo: prato branco             « o último que entrou
Lavei o prato branco              « o Pop tirou o topo
No topo: prato verde
Pratos: 2

2. A ordem de uma pilha

O foreach e o string.Join mostram a pilha do topo para a base: na mesma ordem em que os Pop tirariam os itens.

var pilha = new Stack<int>();
pilha.Push(1);
pilha.Push(2);
pilha.Push(3);

foreach (int n in pilha)
{
    Console.WriteLine(n);
}
Console.WriteLine(string.Join(", ", pilha));
Console.WriteLine(string.Join(", ", pilha.ToArray()));

var outra = new Stack<int>([1, 2, 3]);
Console.WriteLine($"Topo da outra: {outra.Peek()}");
Console.WriteLine($"Itens ainda: {pilha.Count}");

$ dotnet run ordem.cs
3                       « o topo primeiro
2
1
3, 2, 1
3, 2, 1                 « o ToArray também começa pelo topo
Topo da outra: 3        « o 3 foi o último a ser empilhado
Itens ainda: 3         « o foreach só olhou: não tirou nada

foreach (int n in pilha)

Percorre do topo (3) até a base (1), sem tirar nada.

pilha.ToArray()

Copia a pilha num array, também do topo para a base.

new Stack<int>([1, 2, 3])

Cria a pilha empilhando os itens na ordem da lista: primeiro o 1, depois o 2, depois o 3. Por isso o 3 fica no topo, e a pilha "parece" invertida quando você a mostra.

Como a fila, a pilha não tem Add: Stack<int> p = [1, 2, 3]; dá error CS1061 (o erro está em Quando dá errado). Use o construtor, como acima, ou Push.

var historico = new Stack<string>();
historico.Push("inicio.html");
historico.Push("variaveis.html");
historico.Push("arrays.html");
historico.Push("list.html");

// a Ana clicou duas vezes em Voltar

Console.WriteLine($"Página atual: {historico.Peek()}");

var historico = new Stack<string>();
historico.Push("inicio.html");
historico.Push("variaveis.html");
historico.Push("arrays.html");
historico.Push("list.html");

historico.Pop();
historico.Pop();

Console.WriteLine($"Página atual: {historico.Peek()}");

3. A pilha vazia: Stack empty.

var pilha = new Stack<string>();
pilha.Push("prato azul");

Console.WriteLine(pilha.Pop());
Console.WriteLine(pilha.Pop());

$ dotnet run vazia.cs
prato azul
Unhandled exception. System.InvalidOperationException: Stack empty.
   at System.Collections.Generic.Stack`1.ThrowForEmptyStack()
   at System.Collections.Generic.Stack`1.Pop()
   at Program.<Main>$(String[] args) in /home/ana/cs/vazia.cs:line 5
$ echo $?
134

"Pilha vazia." O segundo Pop (linha 5) não tinha prato para tirar. O Peek numa pilha vazia dá a mesma mensagem, com Stack`1.Peek() no rastro. É o mesmo tipo de exceção da fila vazia, a InvalidOperationException: a operação não faz sentido no estado em que a pilha está.

Os métodos com Try não lançam exceção. Eles devolvem true ou false e entregam o item num out:

string texto = "";
var historico = new Stack<string>();

void Escrever(string novo)
{
    historico.Push(texto);
    texto += novo;
    Console.WriteLine($"Texto: \"{texto}\"");
}

void Desfazer()
{
    if (historico.TryPop(out string? anterior))
    {
        texto = anterior;
        Console.WriteLine($"Desfeito: \"{texto}\"");
    }
    else
    {
        Console.WriteLine("Nada para desfazer.");
    }
}

Escrever("Olá");
Escrever(", Ana");
Escrever("!!!");
Desfazer();
Desfazer();
Desfazer();
Desfazer();

$ dotnet run desfazer.cs
Texto: "Olá"
Texto: "Olá, Ana"
Texto: "Olá, Ana!!!"
Desfeito: "Olá, Ana"          « desfez a última escrita
Desfeito: "Olá"
Desfeito: ""
Nada para desfazer.           « pilha vazia: o TryPop devolveu false, sem exceção

void Escrever(string novo)

Uma função local. Antes de mudar o texto, ela empilha como ele era: é isso que permite voltar depois.

historico.Push(texto);

Guarda a versão antiga no topo da pilha.

if (historico.TryPop(out string? anterior))

"Se conseguir tirar uma versão antiga, chame-a de anterior." Numa pilha vazia, devolve false, e o else avisa.

texto = anterior;

Volta para a versão guardada. Como a pilha devolve a mais nova primeiro, cada Desfazer volta um passo.

Existe também o TryPeek(out var x), que espia o topo sem tirar e devolve false numa pilha vazia.

4. Inverter uma palavra

Como a pilha devolve os itens ao contrário da ordem em que entraram, ela inverte coisas naturalmente. Empilhe as letras e desempilhe:

string palavra = "roma";
var pilha = new Stack<char>();
foreach (char letra in palavra)
    pilha.Push(letra);

string invertida = "";
while (pilha.Count > 0)
    invertida += pilha.Pop();

Console.WriteLine(invertida);

$ dotnet run inverter.cs
amor

foreach (char letra in palavra)

Um string pode ser percorrido letra por letra (cada letra é um char). Entram r, o, m, a; o "a" fica no topo.

while (pilha.Count > 0)

Enquanto houver letras, tire a do topo: a, m, o, r.

invertida += pilha.Pop();

Gruda cada letra no fim do texto novo.

5. Conferir parênteses

Um uso clássico, que os compiladores fazem o tempo todo: ver se cada (, [ e { foi fechado na ordem certa. A ideia: ao ver um símbolo que abre, empilhe; ao ver um que fecha, o topo da pilha tem de ser o par dele.

Console.WriteLine(Balanceado("(1 + 2) * [3 - {4 / 2}]"));
Console.WriteLine(Balanceado("(1 + 2]"));
Console.WriteLine(Balanceado("((1 + 2)"));
Console.WriteLine(Balanceado("1 + 2)"));

bool Balanceado(string expressao)
{
    var abertos = new Stack<char>();
    foreach (char c in expressao)
    {
        if (c == '(' || c == '[' || c == '{')
        {
            abertos.Push(c);
        }
        else if (c == ')' || c == ']' || c == '}')
        {
            if (!abertos.TryPop(out char aberto))
                return false;
            if ((c == ')' && aberto != '(') || (c == ']' && aberto != '[') || (c == '}' && aberto != '{'))
                return false;
        }
    }
    return abertos.Count == 0;
}

$ dotnet run parenteses.cs
True                   « tudo fechado na ordem
False                  « abriu com ( e fechou com ]
False                  « sobrou um ( aberto
False                  « fechou um ) que ninguém abriu

Pilha ou fila?

Quando dá errado

$ dotnet run foreach.cs
Unhandled exception. System.InvalidOperationException: Collection was modified after the enumerator was instantiated.
   at System.Collections.Generic.Stack`1.Enumerator.ThrowInvalidVersion()
   at System.Collections.Generic.Stack`1.Enumerator.MoveNext()
   at Program.<Main>$(String[] args) in /home/ana/cs/foreach.cs:line 2

$ dotnet run colexpr.cs
/home/ana/cs/colexpr.cs(1,16): error CS1061: ‘Stack<int>’ não contém uma definição para "Add" e não foi possível encontrar nenhum método de extensão "Add" que aceite um primeiro argumento do tipo ‘Stack<int>’ (você está se esquecendo de usar uma diretiva ou uma referência de assembly?)

Ocorreu uma falha no build. Corrija os erros de build e execute novamente.

Referência rápida

Exercícios

Missão final: os parênteses da calculadora

True
False
False

Console.WriteLine(Balanceado("(1 + (2 * 3))"));
Console.WriteLine(Balanceado("(1 + 2"));
Console.WriteLine(Balanceado("1 + 2)"));

bool Balanceado(string expressao)
{
    var abertos = new Stack<char>();
    foreach (char c in expressao)
    {
        if (c == '(')
        {
            // empilhe o parêntese aberto
        }
        else if (c == ')')
        {
            // tente desempilhar; se a pilha estava vazia, devolva false
        }
    }
    return true; // troque: só está certo se não sobrou nenhum aberto
}

Console.WriteLine(Balanceado("(1 + (2 * 3))"));
Console.WriteLine(Balanceado("(1 + 2"));
Console.WriteLine(Balanceado("1 + 2)"));

bool Balanceado(string expressao)
{
    var abertos = new Stack<char>();
    foreach (char c in expressao)
    {
        if (c == '(')
        {
            abertos.Push(c);
        }
        else if (c == ')')
        {
            if (!abertos.TryPop(out _))
                return false;
        }
    }
    return abertos.Count == 0;
}

O out _ da solução é o descarte: "tire o topo, mas não preciso do valor". Aqui só interessa saber se havia um ( para tirar.

Resumo

• Uma Stack<T> é uma pilha: o último a entrar é o primeiro a sair (LIFO). Você só mexe no topo.
• Push empilha; Pop tira e devolve o topo; Peek mostra o topo sem tirar.
• foreach, ToArray e string.Join vão do topo para a base; new Stack<T>(lista) deixa o último da lista no topo.
• Pop e Peek numa pilha vazia lançam InvalidOperationException: Stack empty.; TryPop e TryPeek devolvem false.
• Mudar a pilha dentro do foreach dá Collection was modified after the enumerator was instantiated.
• Usos clássicos: desfazer, botão Voltar, inverter uma sequência e conferir parênteses.