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.
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.
deque(["first", "second"])🚶🚶 Duas pessoas já esperandoqueue.append("third")🚶 Uma pessoa nova entra no fimqueue.popleft()🎫 A pessoa da frente é atendidalist(queue)👀 Quem ainda está esperandoUma 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
deque(["first", "second"])cria uma fila que já tem dois itens.queue.append("third")adiciona um item no fim.queue.popleft()remove e devolve o item da frente, aqui"first".dequeremove 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
heapqpara uma fila de prioridade. - Várias threads compartilham a fila:
queue.Queuecuida 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
from collections import deque
queue = deque(["first", "second"])
queue.append("third")
print("served:", queue.popleft())
print("waiting:", list(queue))
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.
- Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
- Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
- Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Erros comuns
Usar uma lista e pop(0)
pop(0) desloca todos os itens restantes, o que fica lento em filas longas.
queue = ["first", "second"]
queue.pop(0)
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.
- Ordem dos Cursos Ordene os cursos para que todos os pré-requisitos venham antes. Difícil
- Can We Split Into Two Teams? Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. Médio