Uma fila (queue) é uma estrutura de dados que organiza elementos seguindo a regra First-In, First-Out (FIFO). Ou seja, o primeiro elemento a entrar é o primeiro a sair. Pense na fila do supermercado: quem chegou primeiro é atendido primeiro.
Exemplo simples com listas em Python (não recomendado para desempenho extremo):
fila = [10, 20, 30, 40, 50]
fila.append(60) # insere no final
print(fila.pop(0)) # retira o primeiro (FIFO)
print(fila) # [20, 30, 40, 50, 60]
Observação importante: usar listas para filas pode ser ineficiente para remoções do início (pop(0) é O(n)). Uma alternativa mais eficiente é o deque do módulo collections, que permite inserção e remoção eficientes em ambos extremos.
Para criar uma fila simples em Python, encapsulamos a operação em uma classe que usa uma lista interna para armazenar os dados. Os dois métodos principais são:
Versão sugerida (conforme o texto):
class Fila(object):
def __init__(self):
self.dados = []
def insere(self, elemento):
self.dados.append(elemento)
def retira(self):
return self.dados.pop(0)
def vazia(self):
return len(self.dados) == 0
Observação: o artigo também menciona o uso de deque como alternativa de desempenho superior.
Filas de prioridade são filas nas quais cada elemento tem uma prioridade associada. Elementos com maior prioridade são processados antes dos demais, independentemente da ordem de chegada. Em Python, a estrutura de fila de prioridade pode ser implementada com heap (heapq) para manter eficiência na remoção do elemento com maior prioridade. Em uma fila de prioridade, não basta apenas FIFO; a prioridade determina a ordem de saída.
Uma pilha (stack) é uma estrutura de dados que segue o Last-In, First-Out (LIFO). O último elemento inserido é o primeiro a sair. Pense numa pilha de papéis: você coloca no topo e retira do topo.
Exemplo conceitual com p0, p1, p2, p3, p4 inseridos, depois p5 é inserido e removido em sequência:
| | |----p5----| | |
|----p4----| |----p4----| |----p4----| | |
|----p3----| |----p3----| |----p3----| |----p3----|
|----p2----| |----p2----| |----p2----| |----p2----|
|----p1----| |----p1----| |----p1----| |----p1----|
|----p0----| |----p0----| |----p0----| |----p0----|
Operações-chave:
Entre várias aplicações, duas são muito comuns:
Para implementar pilha em Python, use uma lista e manipule o topo no final (mais eficiente em Python):
class Pilha(object):
def __init__(self):
self.dados = []
def empilha(self, elemento):
self.dados.append(elemento)
def desempilha(self):
if not self.vazia():
return self.dados.pop(-1)
def vazia(self):
return len(self.dados) == 0
Exemplo de uso: empilha 10, 20, 30, 40 e desempilha quatro vezes, imprimindo 40, 30, 20, 10.
Tanto fila quanto pilha são estruturas básicas com alta aplicabilidade. Em produção, o Python oferece módulos prontos como queue, que fornecem implantações eficientes para filas e pilhas com comportamento adequado e segura concorrência.
Fila completa:
class Fila(object):
def __init__(self):
self.dados = []
def insere(self, elemento):
self.dados.append(elemento)
def retira(self):
return self.dados.pop(0)
def vazia(self):
return len(self.dados) == 0
Pilha completa:
class Pilha(object):
def __init__(self):
self.dados = []
def empilha(self, elemento):
self.dados.append(elemento)
def desempilha(self):
if not self.vazia():
return self.dados.pop(-1)
def vazia(self):
return len(self.dados) == 0
Resumo: Estrutura FIFO; inserir no final e retirar do início; mantém ordem de chegada. Desempenho de listas para remoção do início é ruim (O(n)); deque é recomendado para melhor desempenho.
Resumo: Class Fila com insere (append) e retira (pop(0)); método vazia para checar se está vazia. Exemplo de código mostrado na explicação.
Resumo: Filas onde a saída depende da prioridade dos elementos, não apenas da ordem de chegada. Em Python, pode-se usar heaps (heapq) para manter a eficiência de remoção do elemento de maior prioridade.
Resumo: Estrutura LIFO; inserir e retirar no topo (final da lista). Operações empilha e desempilha. Demonstração com sequência de inserções e retiradas.
Resumo: Emprego típico no gerenciamento de chamadas de função (call stack) e balanceamento de parênteses (verificação de balanceamento com pilha).
Resumo: Classe Pilha com empilha (append), desempilha (pop(-1)) e vazia. Demonstração de uso com impressão dos itens desempilhados.
Resumo: Fila e pilha são estruturas de uso frequente; para aplicações reais, prefira implementações prontas como queue do Python para melhor desempenho e segurança.
Resumo: Foram apresentados os códigos completos de Fila e Pilha com as operações básicas descritas acima.
Questão 1 (Média) - Qual afirmação é verdadeira sobre filas?
Resposta correta: C) Retira o primeiro elemento (FIFO).
Explicação: Em uma fila, os elementos são processados na ordem de chegada. A remoção ocorre do início da estrutura.
Questão 2 (Difícil) - Sobre filas implementadas com listas em Python, qual afirmação é correta?
Resposta correta: B) Remover o primeiro elemento com pop(0) é O(n).
Explicação: Em uma lista Python, pop(0) exige deslocamento de todos os demais elementos, resultando em complexidade linear.
Questão 3 (Difícil) - Em uma Pilha, qual opção descreve corretamente o comportamento LIFO?
Resposta correta: A) Inserir no final e remover no final.
Explicação: Em uma pilha, o topo é o último elemento inserido; empilha no final da lista e desempilha do final (LIFO).
Questão 4 (Extrema) - Sobre balanceamento de parênteses com pilha, qual afirmação está correta?
Resposta correta: A) A pilha fica vazia se e somente se a sequência está balanceada.
Explicação: Ao ler cada '(', empilhamos; ao ler ')', desempilhamos. No final, pilha vazia indica que cada abertura tem correspondente fechamento.