Na aula de hoje, exploramos duas estruturas de dados fundamentais na ciência da computação: pilhas (stacks) e filas (queues). Ambas são estruturas lineares que organizam elementos de forma sequencial, mas diferem na política de acesso. Pilhas seguem o princípio LIFO (Last In, First Out), enquanto filas seguem FIFO (First In, First Out). Discutimos suas implementações, operações básicas e principais aplicações.
O que é uma Pilha?
Uma pilha é uma coleção de elementos onde a inserção e remoção ocorrem em uma única extremidade chamada topo. Imagine uma pilha de pratos: o último prato colocado é o primeiro a ser retirado. Isso caracteriza o comportamento LIFO.
As operações fundamentais são:
- push: insere um elemento no topo.
- pop: remove o elemento do topo.
- top (ou peek): acessa o elemento do topo sem removê-lo.
- is_empty: verifica se a pilha está vazia.
Implementação em Python:
class Pilha:
def __init__(self):
self.itens = []
def push(self, item):
self.itens.append(item)
def pop(self):
if not self.is_empty():
return self.itens.pop()
raise IndexError("pop de pilha vazia")
def top(self):
if not self.is_empty():
return self.itens[-1]
raise IndexError("top de pilha vazia")
def is_empty(self):
return len(self.itens) == 0Complexidade: push e pop são O(1) quando usamos lista dinâmica.
Implementação com lista encadeada
Outra forma comum de implementar uma pilha é usando uma lista encadeada (linked list). Cada nó armazena o valor e um ponteiro para o nó anterior (ou próximo, dependendo da orientação). A operação push insere um novo nó no topo e pop remove o nó do topo. Ambas as operações são O(1), sem necessidade de realocação de memória como em listas dinâmicas.
class Node:
def __init__(self, valor):
self.valor = valor
self.proximo = None
class PilhaEncadeada:
def __init__(self):
self.topo = None
def push(self, item):
novo = Node(item)
novo.proximo = self.topo
self.topo = novo
def pop(self):
if self.is_empty():
raise IndexError("pop de pilha vazia")
valor = self.topo.valor
self.topo = self.topo.proximo
return valor
def top(self):
if self.is_empty():
raise IndexError("top de pilha vazia")
return self.topo.valor
def is_empty(self):
return self.topo is NoneEssa implementação consome um pouco mais de memória por nó (armazenamento do ponteiro), mas é adequada quando o tamanho máximo da pilha é desconhecido ou varia muito.
O que é uma Fila?
Uma fila é uma estrutura em que a inserção ocorre em uma extremidade (fim) e a remoção na outra (início), seguindo o princípio FIFO. É como uma fila de banco: o primeiro a chegar é o primeiro a ser atendido.
Operações básicas:
- enqueue: insere no fim.
- dequeue: remove do início.
- front: acessa o primeiro elemento.
- is_empty: verifica se a fila vazia.
Implementação simples:
class Fila:
def __init__(self):
self.itens = []
def enqueue(self, item):
self.itens.append(item)
def dequeue(self):
if not self.is_empty():
return self.itens.pop(0)
raise IndexError("dequeue de fila vazia")
def front(self):
if not self.is_empty():
return self.itens[0]
raise IndexError("fila vazia")
def is_empty(self):
return len(self.itens) == 0Nota: usar pop(0) tem custo O(n) para listas Python; em implementações reais, usa-se deque (collections.deque) para operações O(1) em ambas extremidades.
Implementação eficiente com deque
A biblioteca padrão do Python oferece a classe collections.deque, uma fila duplamente terminada que suporta operações O(1) de inserção e remoção em ambas as extremidades. Para usar como fila, basta fazer:
from collections import deque
class FilaDeque:
def __init__(self):
self.itens = deque()
def enqueue(self, item):
self.itens.append(item)
def dequeue(self):
if self.is_empty():
raise IndexError("dequeue de fila vazia")
return self.itens.popleft()
def front(self):
if self.is_empty():
raise IndexError("fila vazia")
return self.itens[0]
def is_empty(self):
return len(self.itens) == 0O uso de deque é recomendado para a maioria dos casos, pois combina desempenho e simplicidade. Além disso, ela também pode ser usada como pilha (append/pop) com a mesma eficiência.
Implementação com lista encadeada
Assim como a pilha, a fila também pode ser implementada com lista encadeada. A diferença é que precisamos manter referências tanto para o início quanto para o fim da fila, para que enqueue e dequeue sejam O(1). Veja o exemplo:
class Node:
def __init__(self, valor):
self.valor = valor
self.proximo = None
class FilaEncadeada:
def __init__(self):
self.inicio = None
self.fim = None
def enqueue(self, item):
novo = Node(item)
if self.fim:
self.fim.proximo = novo
self.fim = novo
if not self.inicio:
self.inicio = novo
def dequeue(self):
if self.is_empty():
raise IndexError("dequeue de fila vazia")
valor = self.inicio.valor
self.inicio = self.inicio.proximo
if not self.inicio:
self.fim = None
return valor
def front(self):
if self.is_empty():
raise IndexError("fila vazia")
return self.inicio.valor
def is_empty(self):
return self.inicio is NoneA implementação encadeada é útil em cenários onde o tamanho da fila é imprevisível e não queremos desperdiçar memória com capacidade ociosa.
Aplicações
Pilhas são usadas em:
- Expressões aritméticas e avaliação (notação polonesa reversa);
- Gerenciamento de chamadas de função (call stack);
- Desfazer/refazer (undo/redo);
- Algoritmos de backtracking (como em busca em profundidade).
Filas são usadas em:
- Gerenciamento de tarefas (scheduling);
- Filas de impressão;
- BFS (busca em largura) em grafos;
- Buffers de dados (produtor-consumidor).
Exemplos práticos
Verificação de parênteses com pilha
Um uso clássico de pilha é verificar se uma expressão matemática tem os parênteses balanceados. Veja a implementação:
def parenteses_balanceados(expr):
pilha = Pilha() # usando a classe Pilha definida anteriormente
for ch in expr:
if ch == '(':
pilha.push(ch)
elif ch == ')':
if pilha.is_empty():
return False
pilha.pop()
return pilha.is_empty()
# Exemplos
print(parenteses_balanceados("(())")) # True
print(parenteses_balanceados("(()")) # FalseEsse mesmo princípio pode ser estendido para colchetes e chaves, e é a base para parsers de linguagens de programação.
Busca em largura (BFS) com fila
A busca em largura em grafos utiliza uma fila para percorrer os vértices nível a nível. Exemplo simplificado:
from collections import deque
def bfs(grafo, inicio):
visitados = set()
fila = deque([inicio])
visitados.add(inicio)
while fila:
vertice = fila.popleft()
print(f"Visitando: {vertice}")
for vizinho in grafo[vertice]:
if vizinho not in visitados:
visitados.add(vizinho)
fila.append(vizinho)
# Exemplo de grafo
grafo = {
1: [2, 3],
2: [4],
3: [5],
4: [],
5: []
}
bfs(grafo, 1)A fila garante que os vértices sejam explorados na ordem correta, gerando uma busca por níveis.
Comparação
| Característica | Pilha | Fila |
|---|---|---|
| Princípio | LIFO | FIFO |
| Inserção/Remoção | mesmo lado | lados opostos |
| Exemplo típico | pilha de pratos | fila de pessoas |
Variações
Deque (Double-Ended Queue)
O deque (fila duplamente terminada) permite inserção e remoção tanto no início quanto no fim. Em Python, a classe collections.deque implementa essa estrutura. Deques são úteis em problemas que exigem acesso eficiente a ambas as extremidades, como em algoritmos de janela deslizante ou na implementação de filas com prioridade dupla.
Fila de Prioridade (Priority Queue)
Uma fila de prioridade é uma fila onde cada elemento possui uma prioridade e o desenfileiramento ocorre na ordem de maior (ou menor) prioridade, não na ordem de chegada. Em Python, o módulo heapq implementa uma heap mínima, que pode ser usada como fila de prioridade:
import heapq
class FilaPrioridade:
def __init__(self):
self.itens = []
def enqueue(self, item, prioridade):
heapq.heappush(self.itens, (prioridade, item))
def dequeue(self):
if self.itens:
return heapq.heappop(self.itens)[1]
raise IndexError("fila de prioridade vazia")
def is_empty(self):
return len(self.itens) == 0Filas de prioridade são amplamente usadas em algoritmos como Dijkstra, scheduling de processos e sistemas de mensageria.
Perguntas Frequentes
Qual a diferença fundamental entre pilha e fila?
A diferença está na ordem de remoção: pilha remove o elemento mais recente (LIFO); fila remove o mais antigo (FIFO).
Onde são usadas pilhas e filas no dia a dia da programação?
Pilhas aparecem em avaliação de expressões, call stack e undo; filas aparecem em processamento assíncrono, filas de mensagens e BFS.
Posso implementar pilha e fila com listas encadeadas?
Sim, ambas podem ser implementadas com listas ligadas, com vantagens de não ter realocação de memória e operações O(1) para inserção/remoção quando feitas nas extremidades corretas.
Como implementar uma fila circular?
Uma fila circular utiliza um array de tamanho fixo e dois ponteiros (início e fim) que se movem circularmente. Quando um ponteiro atinge o final do array, ele volta ao início, otimizando o uso do espaço. Essa abordagem é comum em sistemas embarcados e buffers de baixo nível. Implementar uma fila circular em Python pode ser feito com uma lista de tamanho fixo e controle manual de índices.
Qual a relação entre pilha e recursão?
A recursão utiliza implicitamente a pilha de chamadas (call stack) do sistema. Cada chamada recursiva empilha um novo quadro (frame) na pilha, contendo variáveis locais e o ponto de retorno. Quando a condição de base é atingida, os quadros começam a ser desempilhados. Por isso, recursões muito profundas podem causar estouro de pilha (stack overflow). Compreender pilhas ajuda a escrever funções recursivas eficientes e, quando necessário, convertê-las em iteração usando uma pilha explícita.
Resumo
- Pilhas e filas são estruturas lineares simples e poderosas.
- Implementá-las bem é essencial para resolver problemas clássicos.
- Python oferece listas e deque como ferramentas práticas.
Confira outros artigos sobre ciência da computação em nossa listagem de posts.
Dominar pilhas e filas é um passo fundamental para avançar em estruturas de dados mais complexas, como árvores, heaps e grafos, bem como para entender algoritmos clássicos de ordenação e busca.