O que são Pilhas (Stacks)
Uma Pilha é uma estrutura de dados que serve como uma coleção de elementos, e permite o acesso a somente um item de dados armazenado – o último item que foi inserido na estrutura (item do topo). Esse item pode ser lido ou removido.
Caso seja removido, teremos acesso ao item imediatamente anterior a ele que se torna automaticamente o último item da pilha (topo), e assim sucessivamente, até que a estrutura esteja vazia.
Uma pilha difere de um array, que é outra estrutura que permite o armazenamento de itens (dados) pois o acesso aos itens de uma pilha é restrito – somente um item pode ser lido ou removido por vez, na ordem inversa em que foram colocado na pilha, ao contrário de um array (vetor), onde podemos acessar qualquer elemento em qualquer posição diretamente, sem a necessidade de acessar itens anteriores primeiro (desde que conhecida a posição do elemento que se deseja acessar).
Podemos implementar pilhas de algumas formas, como por meio de arrays ou com o uso de ADTs (Abstract Data Types / Tipos de Dados Abstratos). Estudaremos ambas as formas nestas lições.
Aplicações das pilhas
As pilhas encontram inúmeras aplicações em programação e desenvolvimento de algoritmos, como por exemplo:
- Avaliação de Expressões e Parsing Sintático
- Algoritmos de Backtracking
- Gerenciamento de Memória em Tempo de Compilação
- Implementação de diversos algoritmos, como Grahan scan e SMAWK
- Operações como desfazer e refazer em aplicações
- Controle de navegação em browsers
- Endereçamento de instruções em microprocessadores
- Análise de expressões aritméticas
e muitas outras.
Como funciona um Pilha
Para entender como uma pilha funciona, faremos uma analogia com o mundo real.
Imagine uma pilha de pratos na cozinha. Se quisermos utilizar um prato, pegamos um do topo desta pilha (último prato). Se necessitarmos de outro, pegamos o próximo da pilha (que agora é o último), e assim por diante.
Quando um prato é lavado, após seu uso, pode ser recolocado novamente na pilha de pratos, sempre no topo. Esse prato recém-colocado na pilha passa a ser o último, e o primeiro que será retirado quando precisarmos usar um prato novamente.
Essa é a ideia geral de uma estrutura de dados do tipo pilha. Nela, os dados são inseridos na pilha (empilhados), e acessados em ordem inversa (o último a ser inserido é sempre o primeiro a ser utilizado). Colocar um elemento no topo de uma pilha é uma operação que recebe um nome especial: push. Já a remoção de um elemento do topo da pilha é uma operação denominada pop.
Por conta deste modo de operação, as pilhas são classificadas como estruturas de dados de armazenamento Last-In, First-Out – LIFO, “o último a entrar é o primeiro a sair”, pois o último item inserido na pilha é sempre o primeiro a ser removido (ou lido).
A figura a seguir ilustra uma pilha contendo valores numéricos, e seu topo assinalado:
Operações Push e Pop
Uma pilha permite o acesso somente ao último item de dados inserido. Ao ser removido esse item, é possível acessar o item anterior a ele, e assim por diante. Para tal, lançamos mão de algumas operações específicas, tanto para inserir quanto para retirar itens da pilha.
As duas principais operações realizadas sobre uma pilha são as operações básicas push e pop.
A operação push é executada para adicionar um elemento ao topo de uma pilha.
A operação pop é executada para retirar um elemento do topo de uma pilha. O elemento retirado é sempre o último que foi adicionado com a operação push.
A figura a seguir ilustra a operação push em uma pilha, sendo executada duas vezes para permitir a inserção de dois novos valores em uma pilha já existente:
Operação push em uma pilha
Já a figura a seguir ilustra a operação pop sendo efetuada sobre a pilha, de modo a remover elementos. Note que se trata de uma operação exatamente inversa à operação push:
Operação pop em uma pilha
Mais sobre pilhas
As pilhas, no geral, são estruturas de dados de tamanho pequeno. Com apenas alguns itens de dados, uma pilha pode ser útil na realização de diversas tarefas computacionais.
Além das operações push e pop, existem algumas outras operações comuns implementadas em pilhas, como peek, isFull e isEmpty. A seguir temos uma breve descrição de cada uma:
- peek – Consiste na leitura do valor armazenado no topo da pilha, sem no entanto removê-lo. Às vezes chamada de top.
- isFull – Função utilizada para verificar se uma pilha está cheia (ou seja, se não é mais possível armazenar itens)
- isEmpty – Função que verifica se uma pilha está vazia – ou seja, se não é possível continuar a remover itens.
As pilhas podem ser implementadas de duas formas principais: usando arrays ou usando listas encadeadas (linked lists). Na próxima lição veremos como implementar uma pilha usando arrays em linguagem C, e posteriormente como implementar pilhas em Java.
Anterior: O que são Estruturas de Dados
Próximo: Como implementar uma pilha em linguagem C usando array.