Estruturas de Dados: O que são Pilhas

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-OutLIFO, “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:

Pilha em estruturas de dados

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

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

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.

Sobre Fábio dos Reis (1221 Artigos)
Fábio dos Reis trabalha com tecnologias variadas há mais de 30 anos, tendo atuado nos campos de Eletrônica, Telecomunicações, Programação de Computadores e Redes de Dados. É um entusiasta de Ciência e Tecnologia em geral, adora Viagens e Música, e estuda idiomas, além de ministrar cursos e palestras sobre diversas tecnologias em São Paulo e outras cidades do Brasil.

1 Comentário em Estruturas de Dados: O que são Pilhas

  1. Matheus Catarino // 08/07/2018 em 11:03 // Responder

    Excelente postagem! Está me ajudando bastante, pois é detalhada e de fácil compreensão (ao menos a minha).

    Embora eu não tenha hábito de ler digitalmente somente em livros e ainda prefiro visualizar vídeos pela rede. Pois os assuntos abordados no seu site é de ótima qualidade. Irá me ajudar bastante futuramente quando eu cursar engenharia da computação. Seria interessante também abordar padrões de objetos em português, já que no inglês tem bastante.

Escreva um comentário

Seu e-mail não será divulgado


*