A pilha de chamadas e o botão desfazer

Desfazer e voltar: a pilha em ação

Pense no que acontece quando você digita num editor de texto. Cada ação, escrever uma palavra, apagar uma frase, colar um trecho, é guardada numa pilha de ações. Ao apertar desfazer, o programa desempilha a última ação e a reverte. Aperte desfazer de novo e ele desempilha a penúltima, e assim por diante, voltando no tempo na ordem inversa exata em que você agiu. Isso é a regra LIFO trabalhando por você: a última coisa que você fez é a primeira a ser desfeita. Se fosse uma fila, o desfazer reverteria suas ações mais antigas primeiro, o que não faria o menor sentido.

O botão voltar do navegador é a mesma ideia com outra roupa. Cada página que você visita é empilhada sobre a anterior. Quando você clica em voltar, o navegador desempilha a página atual e mostra a que estava logo abaixo, a última que você tinha visto antes. Clique em voltar várias vezes e você desce a pilha de páginas, refazendo sua trilha de trás para frente. Editores de imagem, planilhas, aplicativos de desenho, quase todo software com um desfazer decente carrega uma pilha por dentro. Reconhecer esse padrão é entender por que a estrutura importa: ela não é teoria, é o que faz o desfazer parecer natural.

A pilha que o computador mantém sozinho

Aqui está o uso mais profundo, e muitas vezes invisível, da pilha: a pilha de chamadas. Toda vez que uma função chama outra, o computador precisa lembrar de onde a chamada partiu, para poder voltar quando a função chamada terminar. Ele faz isso empilhando um registro da função atual. Se a função principal chama A, e A chama B, a pilha tem três registros: principal no fundo, A no meio, B no topo. Quando B termina, seu registro é desempilhado e a execução volta para A, exatamente no ponto onde A tinha chamado B. Quando A termina, volta para principal. É uma pilha porque a última função chamada é a primeira a terminar e devolver o controle.

Essa mecânica explica também um erro famoso: o estouro de pilha. Se uma função chama a si mesma sem nunca parar, uma recursão sem caso base, por exemplo, a pilha de chamadas cresce sem fim. Cada chamada empilha um registro novo, e como nenhuma termina, nada é desempilhado. A pilha enche até bater no limite de memória e o programa quebra com a mensagem de estouro de pilha. Entender que existe uma pilha por trás das chamadas transforma esse erro de um mistério assustador num sintoma claro: em algum lugar, as chamadas estão entrando e não estão saindo.

Por que reconhecer o padrão importa

O que une o desfazer, o voltar e a pilha de chamadas é o mesmo padrão de raciocínio: sempre que você precisa lembrar de onde veio para poder retornar, e retornar na ordem inversa, a pilha é a estrutura natural. Não é coincidência que problemas tão diferentes usem a mesma solução. Um bom programador aprende a enxergar esse formato: se o problema tem cheiro de voltar ao passo anterior, de aninhar coisas dentro de outras, de reverter na ordem contrária, a pilha provavelmente resolve. Essa aula tratou de casos prontos, mas a próxima mostra você mesmo usando uma pilha para resolver um problema clássico do zero.