Pilha

AULA

19

P ILHAS

Quando tratamos de listas lineares, o armazenamento seqüencial é usado, em geral, quando essas estruturas sofrem poucas modificações ao longo do tempo de execução em uma aplicação, com poucas inserções e remoções realizadas durante sua existência. Isso implica claramente em poucas movimentações de células. Por outro lado, a alocação encadeada é mais usada em situações inversas, ou seja, quando modificações nas listas lineares são mais freqüentes.
Caso os elementos a serem inseridos ou removidos de uma lista linear se localizem em posições especiais nessas estruturas, como por exemplo a primeira ou a última posição, então temos uma situação favorável para o uso de listas lineares em alocação seqüencial. Este é o caso da estrutura de dados denominada pilha. O que torna essa lista linear especial é a adoção de uma política bem definida de inserções e remoções, sempre em um dos extremos da lista. Além da alocação seqüencial, a implementação de uma pilha em alocação encadeada tem muitas aplicações importantes e também será discutida nesta aula.
Esta aula é baseada nas referências [2, 13].

19.1 Definição
Uma pilha é uma lista linear tal que as operações de inserção e remoção são realizadas em um único extremo dessa estrutura de dados.
O funcionamento dessa lista linear pode ser comparado a qualquer pilha de objetos que usamos com freqüência como, por exemplo, uma pilha de pratos de um restaurante. Em geral, os clientes do restaurante retiram pratos do início da pilha, isto é, do primeiro prato mais alto na pilha. Os funcionários colocam pratos limpos também nesse mesmo ponto da pilha. Seria estranho ter de movimentar pratos, por exemplo no meio ou no final da pilha, sempre que uma dessas dessas operações fosse realizada.
O indicador do extremo onde ocorrem as operações de inserção e remoção é chamado de topo da pilha. Essas duas operações são também chamadas de empilhamento e desempilhamento de elementos. Nenhuma outra