Pilhas

Conferir se os parênteses de {[()()]} formam pares corretamente leva uma pilha e 8 pushes e pops, um para cada símbolo.

Último a entrar, primeiro a sair

Pense numa pilha de pratos. Você põe um prato limpo em cima e, quando precisa de um, pega o de cima. O prato que você pôs por último é o primeiro a sair. Uma pilha é uma estrutura de dados com exatamente essa regra, chamada último a entrar, primeiro a sair (LIFO). Ela oferece duas operações principais: push põe um valor no topo, e pop remove o valor do topo e o devolve. Muitas pilhas também oferecem peek, que olha o topo sem remover nada.

Nas notas do 6.006 do MIT, a pilha é um caso especial da interface de sequência: insert last(x) e delete last(). Isso já diz como construir uma. Ponha os valores num array dinâmico e trate o fim do array como o topo. Na unidade anterior, o fim era a ponta barata, então push e pop custam 1 passo cada (amortizado, por causa da cópia ocasional). O tamanho da pilha não faz diferença. Fazer pop numa pilha de 3 valores ou de 3 milhões de valores é o mesmo passo único.

const stack = [];
stack.push(4);
stack.push(8);
stack.push(5);
console.log(stack.pop());           // 5, o último empilhado
console.log(stack[stack.length - 1]); // peek: 8
console.log(stack.length);          // 2

Conferindo parênteses

Um uso clássico da pilha é conferir se os parênteses estão balanceados, o que todo editor de código e todo compilador faz. Leia o texto da esquerda para a direita. Cada símbolo de abertura, (, [ ou {, é empilhado. Cada símbolo de fechamento precisa combinar com o de abertura que está no topo da pilha: se combinar, desempilhe esse símbolo; se a pilha estiver vazia ou o topo for de outro tipo, a sequência não está balanceada. No fim, a pilha precisa estar vazia, senão algum símbolo aberto nunca foi fechado.

Experimente as sequências no laboratório. {[()()]} precisa de 4 pushes e 4 pops, 8 passos, e termina com a pilha vazia. ([)] falha no terceiro caractere: o ) chega enquanto [ está no topo. (() vai até o fim com um ( sobrando. Por que uma pilha serve para esse trabalho? Os parênteses se aninham, e o aberto mais recentemente precisa ser o primeiro a fechar. Isso é último a entrar, primeiro a sair.

Onde mais as pilhas aparecem

• A pilha de chamadas. Quando a função a chama b e b chama c, o computador empilha um registro para cada chamada. Quando c retorna, o registro dela é desempilhado e b continua de onde parou. Uma recursão infinita enche essa pilha, que é o erro de "stack overflow" (estouro de pilha).
• Desfazer. Um editor empilha cada mudança. Desfazer desempilha a mudança mais recente e a reverte.
• Botão Voltar. Um navegador empilha cada página que você deixa; Voltar desempilha a última.
• Busca em profundidade. O curso de algoritmos usou uma pilha para ir o mais fundo possível num labirinto antes de voltar.