O que é uma pilha (LIFO)

Uma estrutura com uma regra só

No módulo anterior você viu a diferença entre uma estrutura de dados, que guarda a informação, e um algoritmo, que age sobre ela. A pilha é a primeira estrutura abstrata que vamos estudar de verdade, e o bonito dela é a simplicidade. Uma pilha tem uma regra só, e essa regra decide tudo: o último item que você coloca é o primeiro que você tira. Nada de escolher um item do meio, nada de furar a ordem. Se você guardou dez coisas, a décima sai primeiro, depois a nona, e assim por diante, na ordem inversa da entrada.

A analogia que nunca falha é a pilha de pratos na cozinha. Você lava um prato e o coloca em cima da pilha. Lava outro, coloca em cima. Na hora de secar, pega o de cima, que foi o último a ser colocado. Ninguém puxa o prato do fundo, porque a torre inteira desabaria. A pilha de livros na escrivaninha funciona igual: o livro que você largou por último é o que está no topo, à mão. Toda pilha do mundo físico obedece a essa lógica de topo, e a pilha da programação apenas copia esse comportamento numa estrutura de dados.

Por que só o topo importa

O que faz a pilha ser uma estrutura tão específica é justamente o que ela proíbe. Numa lista, você pode ler o item de qualquer posição, o primeiro, o quinto, o último, a hora que quiser. A pilha abre mão dessa liberdade de propósito. Ela só deixa você mexer no topo, e essa restrição, longe de ser uma limitação boba, é o que a torna perfeita para certos problemas. Quando um problema tem a cara de desfazer o último passo, voltar ao ponto anterior ou tratar as coisas na ordem inversa, a pilha encaixa como uma luva, porque ela foi feita para isso. Escolher a estrutura certa é meia solução, e reconhecer o padrão do topo é o que faz você pensar em pilha.

Pilha não é o mesmo que lista

Vale reforçar a diferença, porque é fácil confundir. Por dentro, muitas linguagens constroem a pilha em cima de uma lista, então a matéria-prima é a mesma. Mas a pilha é um contrato de uso: ela promete que você só vai mexer no topo. Uma lista à qual você adiciona e remove só no final se comporta como uma pilha, mesmo que a estrutura por baixo seja um vetor comum. O que define a pilha não é como ela é guardada na memória, e sim quais operações ela permite. Essa ideia de separar o que a estrutura faz do como ela é feita é o conceito de tipo abstrato de dados, e a pilha é o primeiro exemplo concreto dele neste curso.