3.3. O que é uma Pilha?¶

Uma pilha (stack) é uma coleção ordenada de itens onde a inserção de novos itens e a remoção de itens existentes sempre ocorrem na mesma extremidade. Este extremidade é comumente chamada de topo. A extremidade oposta ao topo é conhecida como base.

Os itens armazenados na pilha que estão mais perto da base são aqueles que estão na pilha a mais tempo. O último item inserido é aquele que está na posição em que pode ser removido primeiro. Este princípio de ordenação é as vezes chamado de LIFO, último a entrar primeiro a sair (last in first out). Os itens estão armazenados de acordo com o tempo de permanência na estrutura. Itens recentemente inseridos na estrutura estão mais próximos do topo, enquanto os itens mais antigos na estrutura estão perto da base.

Muitos exemplos de pilhas ocorrem em situações cotidianas. Quase qualquer refeitório tem uma pilha de bandejas ou pratos onde você pega a bandeja ou prato que está no topo, descobrindo uma nova bandeja ou prato para o próximo cliente na fila. Imagine uma pilha de livros em uma mesa (Figure 1). O único livro cuja capa é visível é o que está no topo. Para acessar algum livro na pilha, precisamos remover os que estão sobre ele. Figure 2 mostra outra pilha que contém alguns objetos nativos de Python.

Figure 1: Uma pilha de livros¶

Figure 2: Uma pilha de objetos de Python¶

Uma das idéias mais úteis relacionadas às pilhas vem da simples observação dos itens à medida que são inseridos e removidos. Suponha que você começa com uma mesa vazia. Agora, coloque um livro de cada vez na mesa, um sobre o outro. Você está construindo uma pilha. Considere o que acontece quando você começar a remover livros. A ordem que eles são removidos é exatamente a inversa da ordem em que foram colocados. As pilhas são fundamentalmente importantes, pois elas podem ser usadas para reverter a ordem dos itens. A ordem de inserção é a inversa da ordem de remoção. Figura 3 mostra a pilha de objetos de Python como ela foi criada e, novamente, como os itens são removidos. Preste atenção a ordem do objetos.

Figure 3: Reversão usando pilhas¶

Considerando essa propriedade de reversão, talvez você possa pensar em exemplos de pilhas que ocorrem quando você usa seu computador. Por exemplo, todo navegador tem um botão Voltar (Back). À medida que você navega de uma página web para outra página, essas páginas são colocadas em uma pilha (na verdade, são as URLs que vão para a pilha). A página atual que você está visualizando está no topo e a primeira página que você olhou está na base. Se você clicar no botão Voltar, você começa a se mover pelas página na ordem inversa.