Algoritmos em Python

Estrutura de dados fila (queue) em Python

Nesta lição, você vai implementar uma fila eficiente, no esquema primeiro a entrar, primeiro a sair, com collections.deque.

  • Intermediário
  • 2 min de leitura
  • 1 exemplo executável

Introdução

O problema

Trabalhos de impressão, chamados de suporte e mensagens entre programas precisam ser tratados na ordem em que chegam. Uma fila (queue) mantém essa ordem. No Python, escolher a ferramenta certa garante que ela continue rápida mesmo com milhões de itens.

Pense assim

Uma fila é como a fila de um guichê de ingressos. Pessoas novas entram no fim, e quem está na frente é atendido primeiro. Ninguém fura a fila, então todos são atendidos na ordem em que chegaram.

Da fila do guichê ao código
deque(["first", "second"])🚶🚶 Duas pessoas já esperando
queue.append("third")🚶 Uma pessoa nova entra no fim
queue.popleft()🎫 A pessoa da frente é atendida
list(queue)👀 Quem ainda está esperando
O primeiro a entrar é o primeiro a sair: a ordem de chegada é a ordem de atendimento.
Em uma frase

Uma fila é uma coleção FIFO (first in, first out, ou seja, o primeiro a entrar é o primeiro a sair): itens são adicionados no fim e removidos da frente.

Pontos-chave

  1. deque(["first", "second"]) cria uma fila que já tem dois itens.
  2. queue.append("third") adiciona um item no fim.
  3. queue.popleft() remove e devolve o item da frente, aqui "first".
  4. deque remove da frente rapidamente. Uma lista teria que deslocar todos os itens restantes.

Quando usar?

  • Processar tarefas ou pedidos na ordem de chegada.
  • Busca em largura em grafos e grades.
  • Buffers entre produtores e consumidores, como mensagens ou eventos.

Quando não é preciso

  • O item mais recente deve sair primeiro: use uma pilha.
  • Os itens têm prioridades: use heapq para uma fila de prioridade.
  • Várias threads compartilham a fila: queue.Queue cuida dos locks para você.

Veja como funciona

Faça enqueue e dequeue para ver que os itens saem na mesma ordem em que chegaram.

Código de exemplo

Executar código →
main.py
from collections import deque

queue = deque(["first", "second"])
queue.append("third")

print("served:", queue.popleft())
print("waiting:", list(queue))
Gerar um botão Run para este exemplo

Resultado da execução

served: first
waiting: ['second', 'third']

Explicação do código

O deque permite adicionar elementos à direita com append() e removê-los da esquerda com popleft(), ambos em O(1). Com uma lista comum, remover o primeiro elemento custa O(n), porque todos os elementos seguintes precisam se deslocar, por isso o deque é a escolha certa para filas.

Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.

Exercícios práticos

Tente modificar o código seguindo as sugestões abaixo. Mudar o código e observar o resultado ajuda você a entender muito mais do que só ler.

  1. Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
  2. Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
  3. Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Executar no compilador Python →

Erros comuns

Usar uma lista e pop(0)

pop(0) desloca todos os itens restantes, o que fica lento em filas longas.

Problema
queue = ["first", "second"]
queue.pop(0)
Correção
queue = deque(["first", "second"])
queue.popleft()

Terminou esta lição?

Marque como aprendida para acompanhar seu progresso.

Pratique com um desafio

Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.

Todos os desafios