pilha

Pilhas, também chamadas de stack, são estruturas lineares de dados que armazenam elementos de modo que o último a entrar é o primeiro a sair (LIFO). As operações básicas são empilhar (push), desempilhar (pop) e consultar o topo (peek). Normalmente também incluem checagens de vazio e informações sobre o tamanho.

Podem ser implementadas de duas formas comuns: com um array contíguo ou com uma lista ligada. Em uma pilha baseada em array, mantém-se um índice do topo; em uma pilha ligada, cada nó aponta para o elemento anterior. Em ambas, push e pop costumam ser operações em tempo constante.

Características importantes incluem o tamanho máximo (em pilhas fixas) e o tratamento de estouro (overflow) ou erro ao remover de uma pilha vazia (underflow). A ordem de acesso é estritamente LIFO, o que impede operações de acesso ao meio sem desempilhar elementos.

Aplicações típicas incluem a gestão da pilha de chamadas de funções, avaliação de expressões em notação polonesa reversa, parsing de estruturas sintáticas, busca em profundidade, algoritmos de retrocesso (backtracking) e mecanismos de desfazer/redo em interfaces de usuário. Pilhas também aparecem em várias implementações de compiladores e interpretadores para acompanhar o estado de execução.

Relacionados: filas (FIFO) são estruturas distintas com acesso em primeira posição, e o deque permite inserções e remoções em ambos os extremos. Em teoria da computação, pilhas aparecem em automatos de pilha (pushdown automata). Em programação prática, a expressão “pilha de chamadas” refere-se à pilha que gerencia chamadas de função e retornos durante a execução de um programa.