As estruturas de dados são essenciais na programação, funcionando como alicerces para organizar informações de forma eficaz. Entre elas, a pilha se destaca por sua simplicidade e utilidade.
Neste artigo, exploraremos a fundo o conceito de pilha e suas implementações práticas em Python.
O que Define uma Pilha?
Pense em uma pilha como um monte de objetos, como livros ou cadeiras, onde o último item adicionado é o primeiro a ser removido. Esse é o princípio fundamental da pilha: Último a Entrar, Primeiro a Sair (LIFO, do inglês Last-In/First-Out). Para ilustrar, imagine a seguinte situação:
Imagine uma pilha de livros.
Para acessar o terceiro livro de cima, você precisa remover os dois primeiros. O livro que chegou por último à pilha é o primeiro a ser retirado. Essa lógica LIFO é a base da estrutura de dados pilha na programação.
Operações Básicas em Pilhas
As pilhas operam principalmente por meio de duas ações:
1. push(dado)
Essa operação insere um novo elemento no topo da pilha, como adicionar um livro no topo da pilha física.
2. pop()
Essa operação remove o elemento do topo da pilha, como tirar o livro mais recente de uma pilha de livros.
As ilustrações abaixo demonstram essas ações visualmente.
Além dessas operações, algumas funções auxiliares são úteis para obter informações sobre o estado da pilha.
Vejamos algumas delas:
olhadinha()
Essa função permite verificar qual elemento está atualmente no topo da pilha, sem removê-lo.
está_vazia()
Essa função verifica se a pilha está vazia ou se contém algum elemento.
Agora que compreendemos os conceitos teóricos da pilha, vamos à sua implementação prática. Vamos supor que você já tenha o Python instalado ou que esteja usando um compilador online.
Implementando Pilhas em Python
A implementação de pilhas é relativamente simples em comparação com outras estruturas de dados. Em Python, podemos implementar uma pilha de várias maneiras.
A seguir, exploraremos algumas abordagens:
#1. Usando Listas
Neste método, criaremos uma classe para encapsular a lógica de pilha usando listas. Vamos detalhar cada passo da implementação.
Passo 1: Definir a classe Pilha.
class Pilha: pass
Passo 2: Criar uma lista vazia para armazenar os elementos.
class Pilha: def __init__(self): self.elementos = []
Passo 3: Implementar a função `push` para adicionar elementos à lista.
class Pilha: def __init__(self): self.elementos = [] def push(self, dado): self.elementos.append(dado) return dado
Passo 4: Implementar a função `pop` para remover o elemento do topo da lista.
class Pilha: ## ... def pop(self): return self.elementos.pop()
Até este ponto, implementamos a pilha com as operações básicas. Agora, adicionaremos as funções auxiliares para obter mais informações sobre o estado da pilha.
Passo 5: Implementar a função `olhadinha` para verificar o elemento do topo sem removê-lo.
class Pilha: ## ... def olhadinha(self): return self.elementos[-1]
Passo 6: Implementar a função `está_vazia` para verificar se a pilha está vazia.
class Pilha: ## ... def está_vazia(self): return len(self.elementos) == 0
Concluímos a implementação da pilha usando listas como base. Agora, vamos aprender a usar nossa implementação.
Para utilizar a classe `Pilha`, precisamos criar um objeto dessa classe. A seguir, veremos como fazer isso.
class Pilha:
## ...
if __name__ == '__main__':
pilha = Pilha()
Criamos o objeto pilha e agora estamos prontos para usar as operações. Para testar, vamos seguir os seguintes passos:
- Verificar se a pilha está vazia usando `está_vazia`. O resultado deve ser `True`.
- Inserir os números 1, 2, 3, 4 e 5 na pilha usando `push`.
- Verificar se a pilha ainda está vazia usando `está_vazia`. O resultado deve ser `False`.
- Exibir o elemento do topo usando `olhadinha`.
- Remover o elemento do topo usando `pop`.
- Verificar novamente o elemento do topo usando `olhadinha`. O resultado deve ser 4.
- Remover todos os elementos da pilha usando `pop`.
- Verificar se a pilha está vazia pela última vez usando `está_vazia`. O resultado deve ser `True`.
Se todos os passos forem executados corretamente, nossa implementação da pilha estará concluída. Tente escrever o código para esses passos.
Se você precisar de ajuda, aqui está o código completo:
class Pilha:
def __init__(self):
self.elementos = []
def push(self, dado):
self.elementos.append(dado)
return dado
def pop(self):
return self.elementos.pop()
def olhadinha(self):
return self.elementos[-1]
def está_vazia(self):
return len(self.elementos) == 0
if __name__ == '__main__':
pilha = Pilha()
## verificando se está vazia -> true
print(pilha.está_vazia())
## inserindo elementos
pilha.push(1)
pilha.push(2)
pilha.push(3)
pilha.push(4)
pilha.push(5)
## verificando novamente se está vazia -> false
print(pilha.está_vazia())
## mostrando o elemento do topo -> 5
print(pilha.olhadinha())
## removendo o elemento do topo -> 5
pilha.pop()
## verificando o elemento do topo novamente -> 4
print(pilha.olhadinha())
## removendo todos os elementos
pilha.pop()
pilha.pop()
pilha.pop()
pilha.pop()
## verificando se está vazia pela última vez -> true
print(pilha.está_vazia())
Parabéns! Implementamos uma pilha do zero usando listas em Python. Se você executar o código acima, obterá a saída a seguir:
True False 5 4 True
Podemos usar listas diretamente como pilhas, mas a implementação acima ajuda a entender o conceito de pilha em outras linguagens de programação.
Além disso, você pode consultar estes artigos relacionados a listas.
Agora, vamos explorar o `deque`, que é fornecido pelo módulo `collections` do Python, como alternativa para implementar pilhas.
#2. Usando `deque` do módulo `collections`
O `deque` é implementado como uma fila de duas extremidades, permitindo adicionar e remover elementos em ambas as pontas. Essa característica o torna útil para implementarmos uma pilha seguindo o princípio LIFO.
Internamente, ele é implementado usando listas duplamente encadeadas. Isso garante um desempenho consistente na inserção e remoção de elementos. A desvantagem das listas encadeadas é o acesso aos elementos do meio, que levam tempo O(n). No entanto, como em uma pilha raramente precisamos acessar os elementos intermediários, isso não é um problema.
Antes de implementarmos a pilha, vejamos os métodos do `deque` que utilizaremos:
- `append(dado)` – Insere o elemento no topo da pilha (fim do deque).
- `pop()` – Remove o elemento do topo da pilha (fim do deque).
Não existem métodos diretos para `olhadinha` e `está_vazia`, mas podemos imprimir todo o deque para “ver” o topo e usar `len()` para verificar se está vazio. Vejamos a implementação:
from collections import deque ## criando objeto deque pilha = deque() ## verificando se a pilha está vazia -> true print(len(pilha) == 0) ## inserindo os elementos pilha.append(1) pilha.append(2) pilha.append(3) pilha.append(4) pilha.append(5) ## verificando novamente se a pilha está vazia -> false print(len(pilha) == 0) ## mostrando a pilha print(pilha) ## removendo o elemento do topo -> 5 pilha.pop() ## mostrando a pilha novamente print(pilha) ## removendo todos os elementos pilha.pop() pilha.pop() pilha.pop() pilha.pop() ## verificando se a pilha está vazia pela última vez -> true print(len(pilha) == 0)
Aprendemos como implementar uma pilha usando `deque`. A saída deste código será:
True False deque([1, 2, 3, 4, 5]) deque([1, 2, 3, 4]) True
Até agora, vimos duas formas de implementar pilhas. Há ainda uma terceira forma de implementar pilhas que exploraremos a seguir.
#3. Usando `LifoQueue` do módulo `queue`
O nome `LifoQueue` indica que ela segue o princípio LIFO, sendo perfeita para implementar pilhas. Ela é fornecida pelo módulo `queue` do Python e oferece alguns métodos convenientes:
- `put(dado)` – Adiciona um elemento à pilha.
- `get()` – Remove o elemento do topo da pilha.
- `empty()` – Verifica se a pilha está vazia.
- `qsize()` – Retorna o tamanho da pilha.
Vejamos como implementar pilhas usando `LifoQueue`:
from queue import LifoQueue
## criando objeto LifoQueue
pilha = LifoQueue()
## verificando se a pilha está vazia -> true
print(pilha.empty())
## adicionando os elementos
pilha.put(1)
pilha.put(2)
pilha.put(3)
pilha.put(4)
pilha.put(5)
## verificando se a pilha está vazia novamente -> false
print(pilha.empty())
## removendo todos os elementos
print(pilha.get())
print(pilha.get())
print(pilha.get())
## mostrando o tamanho da pilha
print("Tamanho", pilha.qsize())
print(pilha.get())
print(pilha.get())
## verificando se a pilha está vazia pela última vez -> true
print(pilha.empty())
A saída deste código será:
True False 5 4 3 Tamanho 2 2 1 True
Aplicações Práticas de Pilhas
Agora que você conhece bem as pilhas, vamos explorar como aplicá-las em problemas reais de programação. Considere o problema de verificar o balanceamento de parênteses, chaves e colchetes em uma expressão.
Por exemplo:
Entrada: “[{}]([])”
Saída: Equilibrado
Entrada: “{[}]([])”
Saída: Não Equilibrado
Podemos usar uma pilha para resolver esse problema. Veja os passos:
- Criar uma pilha para armazenar os caracteres.
- Se o comprimento da expressão for ímpar, a expressão não é balanceada.
- Iterar sobre a expressão:
- Se o caractere atual for um parêntese, chave ou colchete de abertura, insira-o na pilha.
- Caso contrário, se o caractere for de fechamento, remova um elemento da pilha.
- Se o caractere removido corresponder ao de abertura, continue, caso contrário, a expressão é desbalanceada.
- Ao finalizar a iteração, se a pilha estiver vazia, a expressão estará balanceada, caso contrário, não estará.
Podemos utilizar a implementação de pilha com listas para a verificação do balanceamento:
## pilha
class Pilha:
def __init__(self):
self.elementos = []
def push(self, dado):
self.elementos.append(dado)
return dado
def pop(self):
return self.elementos.pop()
def olhadinha(self):
return self.elementos[-1]
def está_vazia(self):
return len(self.elementos) == 0
def verificar_balanceamento(expressão):
## verificando o comprimento da expressão
if len(expressão) % 2 != 0:
## se for ímpar não é balanceada
return False
## para verificação
abertura = set('([{')
pares = set([ ('(',')'), ('[',']'), ('{','}') ])
## inicialização da pilha
pilha = Pilha()
## iteração sobre a expressão
for caractere in expressão:
## verifica se o caractere é de abertura
if caractere in abertura:
## adiciona na pilha
pilha.push(caractere)
else:
## remove da pilha o último caractere
caractere_removido = pilha.pop()
## verifica se o caractere removido e o atual formam um par
if (caractere_removido, caractere) not in pares:
return False
return pilha.está_vazia()
if __name__ == '__main__':
if verificar_balanceamento('[{}]([])'):
print("Balanceado")
else:
print("Não Balanceado")
if verificar_balanceamento('{[}]([])'):
print("Balanceado")
else:
print("Não Balanceado")
As pilhas são úteis em muitos outros problemas de programação. Este exemplo é apenas um deles. Experimente aplicar o conceito de pilhas sempre que possível.
Conclusão
Parabéns, você concluiu este tutorial sobre pilhas. Espero que tenha sido útil para você. Este é o fim deste tutorial.
Bons estudos 🙂 👨💻