Pilhas e Filas em Python: Implementacao com Listas e deque
7 min de leitura
Atualizado em 27 Apr 2026
Pilhas e Filas: Estruturas Fundamentais
Pilhas (stacks) e filas (queues) sao duas das estruturas de dados mais importantes da computacao. Elas controlam a ordem em que elementos sao processados e aparecem em inumeros cenarios reais: desde o “Desfazer” do seu editor de texto ate o agendamento de tarefas em servidores.
Em Python, podemos implementa-las com listas, collections.deque e modulos especializados como heapq e queue. Vamos explorar cada abordagem.
Pilha (Stack) — LIFO
Uma pilha segue o principio LIFO (Last In, First Out): o ultimo elemento adicionado e o primeiro a ser removido. Pense numa pilha de pratos — voce sempre pega o prato do topo.
Operacoes Principais
| Operacao | Descricao | Complexidade |
|---|---|---|
| push | Adicionar ao topo | O(1) |
| pop | Remover do topo | O(1) |
| peek/top | Ver o topo sem remover | O(1) |
| is_empty | Verificar se esta vazia | O(1) |
Implementacao com Lista
class Pilha:
def __init__(self):
self._dados = []
def push(self, item):
"""Adiciona item ao topo da pilha."""
self._dados.append(item)
def pop(self):
"""Remove e retorna o item do topo."""
if self.esta_vazia():
raise IndexError("Pilha vazia")
return self._dados.pop()
def topo(self):
"""Retorna o item do topo sem remover."""
if self.esta_vazia():
raise IndexError("Pilha vazia")
return self._dados[-1]
def esta_vazia(self):
return len(self._dados) == 0
def tamanho(self):
return len(self._dados)
def __repr__(self):
return f"Pilha({self._dados})"
# Uso
pilha = Pilha()
pilha.push(10)
pilha.push(20)
pilha.push(30)
print(pilha.topo()) # 30
print(pilha.pop()) # 30
print(pilha.pop()) # 20
print(pilha) # Pilha([10])
Implementacao com deque
from collections import deque
class PilhaDeque:
def __init__(self):
self._dados = deque()
def push(self, item):
self._dados.append(item)
def pop(self):
if not self._dados:
raise IndexError("Pilha vazia")
return self._dados.pop()
def topo(self):
if not self._dados:
raise IndexError("Pilha vazia")
return self._dados[-1]
def esta_vazia(self):
return len(self._dados) == 0
Caso de Uso: Sistema de Undo/Redo
class EditorTexto:
def __init__(self):
self.texto = ""
self._undo_stack = []
self._redo_stack = []
def digitar(self, novo_texto):
self._undo_stack.append(self.texto)
self._redo_stack.clear()
self.texto += novo_texto
def desfazer(self):
if not self._undo_stack:
print("Nada para desfazer")
return
self._redo_stack.append(self.texto)
self.texto = self._undo_stack.pop()
def refazer(self):
if not self._redo_stack:
print("Nada para refazer")
return
self._undo_stack.append(self.texto)
self.texto = self._redo_stack.pop()
# Uso
editor = EditorTexto()
editor.digitar("Ola ")
editor.digitar("mundo ")
editor.digitar("Python!")
print(editor.texto) # "Ola mundo Python!"
editor.desfazer()
print(editor.texto) # "Ola mundo "
editor.desfazer()
print(editor.texto) # "Ola "
editor.refazer()
print(editor.texto) # "Ola mundo "
Caso de Uso: Verificar Parenteses Balanceados
def parenteses_balanceados(expressao):
"""Verifica se parenteses, colchetes e chaves estao balanceados."""
pilha = []
pares = {")": "(", "]": "[", "}": "{"}
for char in expressao:
if char in "([{":
pilha.append(char)
elif char in ")]}":
if not pilha or pilha[-1] != pares[char]:
return False
pilha.pop()
return len(pilha) == 0
print(parenteses_balanceados("((a + b) * [c - d])")) # True
print(parenteses_balanceados("((a + b)")) # False
print(parenteses_balanceados("{[}]")) # False
Este e um problema classico de entrevistas Python.
Fila (Queue) — FIFO
Uma fila segue o principio FIFO (First In, First Out): o primeiro elemento adicionado e o primeiro a ser removido. Como uma fila de supermercado — quem chegou primeiro e atendido primeiro.
Operacoes Principais
| Operacao | Descricao | Complexidade (deque) |
|---|---|---|
| enqueue | Adicionar ao final | O(1) |
| dequeue | Remover do inicio | O(1) |
| front | Ver o primeiro sem remover | O(1) |
| is_empty | Verificar se esta vazia | O(1) |
Por que Nao Usar Lista para Filas
# NAO FACA ISSO — pop(0) e O(n)!
fila_ruim = [1, 2, 3, 4, 5]
fila_ruim.pop(0) # Remove o 1, mas desloca todos os outros elementos
Remover do inicio de uma lista e O(n) porque todos os elementos precisam ser deslocados. Use deque que oferece O(1) em ambas as pontas.
Implementacao com deque
from collections import deque
class Fila:
def __init__(self):
self._dados = deque()
def enfileirar(self, item):
"""Adiciona item ao final da fila."""
self._dados.append(item)
def desenfileirar(self):
"""Remove e retorna o primeiro item."""
if self.esta_vazia():
raise IndexError("Fila vazia")
return self._dados.popleft()
def primeiro(self):
"""Retorna o primeiro item sem remover."""
if self.esta_vazia():
raise IndexError("Fila vazia")
return self._dados[0]
def esta_vazia(self):
return len(self._dados) == 0
def tamanho(self):
return len(self._dados)
def __repr__(self):
return f"Fila({list(self._dados)})"
# Uso
fila = Fila()
fila.enfileirar("Cliente 1")
fila.enfileirar("Cliente 2")
fila.enfileirar("Cliente 3")
print(fila.primeiro()) # "Cliente 1"
print(fila.desenfileirar()) # "Cliente 1"
print(fila.desenfileirar()) # "Cliente 2"
print(fila) # Fila(['Cliente 3'])
Caso de Uso: BFS (Busca em Largura)
from collections import deque
def bfs(grafo, inicio):
"""Busca em largura usando fila."""
visitados = set()
fila = deque([inicio])
ordem = []
while fila:
vertice = fila.popleft()
if vertice not in visitados:
visitados.add(vertice)
ordem.append(vertice)
# Adicionar vizinhos nao visitados a fila
for vizinho in grafo.get(vertice, []):
if vizinho not in visitados:
fila.append(vizinho)
return ordem
# Grafo de exemplo
grafo = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"]
}
print(bfs(grafo, "A"))
# ['A', 'B', 'C', 'D', 'E', 'F']
Caso de Uso: Agendamento de Tarefas
from collections import deque
from datetime import datetime
class AgendadorTarefas:
def __init__(self):
self._fila = deque()
def adicionar_tarefa(self, nome, prioridade="normal"):
tarefa = {
"nome": nome,
"prioridade": prioridade,
"criada_em": datetime.now().isoformat()
}
if prioridade == "urgente":
self._fila.appendleft(tarefa) # Urgente vai para o inicio
else:
self._fila.append(tarefa)
def processar_proxima(self):
if not self._fila:
return "Nenhuma tarefa pendente"
tarefa = self._fila.popleft()
return f"Processando: {tarefa['nome']} ({tarefa['prioridade']})"
def pendentes(self):
return len(self._fila)
# Uso
agendador = AgendadorTarefas()
agendador.adicionar_tarefa("Enviar relatorio")
agendador.adicionar_tarefa("Backup do banco")
agendador.adicionar_tarefa("Fix bug critico", "urgente")
print(agendador.processar_proxima())
# "Processando: Fix bug critico (urgente)"
Para processamento assincrono de tarefas em producao, veja nosso artigo sobre Celery e async/await em Python.
Fila de Prioridade com heapq
Uma fila de prioridade remove sempre o elemento com menor prioridade (menor valor). O modulo heapq implementa um min-heap eficiente:
import heapq
class FilaPrioridade:
def __init__(self):
self._heap = []
self._contador = 0 # Desempate para mesma prioridade
def adicionar(self, item, prioridade):
heapq.heappush(self._heap, (prioridade, self._contador, item))
self._contador += 1
def remover(self):
if not self._heap:
raise IndexError("Fila vazia")
prioridade, _, item = heapq.heappop(self._heap)
return item, prioridade
def esta_vazia(self):
return len(self._heap) == 0
# Uso — menor numero = maior prioridade
fila = FilaPrioridade()
fila.adicionar("Tarefa baixa prioridade", prioridade=3)
fila.adicionar("Tarefa critica", prioridade=1)
fila.adicionar("Tarefa media", prioridade=2)
while not fila.esta_vazia():
item, prio = fila.remover()
print(f"[P{prio}] {item}")
# [P1] Tarefa critica
# [P2] Tarefa media
# [P3] Tarefa baixa prioridade
Operacoes do heapq
import heapq
numeros = [5, 3, 8, 1, 9, 2]
# Transformar lista em heap — O(n)
heapq.heapify(numeros)
print(numeros) # [1, 3, 2, 5, 9, 8]
# Inserir — O(log n)
heapq.heappush(numeros, 4)
# Remover o menor — O(log n)
menor = heapq.heappop(numeros) # 1
# N menores/maiores — O(n log k)
dados = [15, 3, 28, 7, 42, 1, 19]
print(heapq.nsmallest(3, dados)) # [1, 3, 7]
print(heapq.nlargest(3, dados)) # [42, 28, 19]
queue.Queue: Fila Thread-Safe
Para aplicacoes com multiprocessing ou threads, o modulo queue oferece filas seguras:
from queue import Queue, LifoQueue, PriorityQueue
import threading
# Fila FIFO thread-safe
fila = Queue(maxsize=10)
def produtor(fila):
for i in range(5):
fila.put(f"Item {i}")
print(f"Produzido: Item {i}")
def consumidor(fila):
while True:
item = fila.get()
if item is None:
break
print(f"Consumido: {item}")
fila.task_done()
# Iniciar threads
t_prod = threading.Thread(target=produtor, args=(fila,))
t_cons = threading.Thread(target=consumidor, args=(fila,))
t_prod.start()
t_cons.start()
t_prod.join()
fila.put(None) # Sinal de parada
t_cons.join()
| Classe | Ordem | Uso |
|---|---|---|
Queue | FIFO | Processamento em ordem |
LifoQueue | LIFO (pilha) | Pilha thread-safe |
PriorityQueue | Prioridade | Tarefas com prioridade |
Comparacao: Quando Usar Cada Estrutura
| Estrutura | Ordem | Implementacao | Melhor Para |
|---|---|---|---|
| Pilha (lista) | LIFO | list | Undo, avaliacao de expressoes |
| Pilha (deque) | LIFO | deque | Thread-safe, alta performance |
| Fila (deque) | FIFO | deque | BFS, agendamento |
| Fila de prioridade | Prioridade | heapq | Dijkstra, agendamento com prioridade |
| Queue | FIFO thread-safe | queue.Queue | Produtor-consumidor com threads |
Para decidir entre essas e outras estruturas como dicionarios e sets, veja nosso guia de estruturas de dados Python.
Conclusao
Pilhas e filas sao estruturas simples mas extremamente poderosas. Em Python, collections.deque e a ferramenta ideal para ambas — oferece O(1) em ambas as pontas e e mais eficiente que listas para filas. Para filas de prioridade, heapq e a escolha certa, e para cenarios com threads, use queue.Queue.
Domine essas estruturas e voce estara preparado para resolver problemas classicos de entrevistas e construir aplicacoes robustas.
Continue aprendendo: listas, dicionarios, ordenacao e busca binaria.
Veja como outras linguagens implementam essas estruturas: Go, Rust e Kotlin.