Filas e collections.deque
Insira e remova rapidamente pelas duas extremidades.
Filas e collections.deque é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
Primeiro a entrar, primeiro a sair
Uma fila atende os itens na ordem em que chegaram, como uma fila em uma loja. O primeiro a entrar é o primeiro a sair.
Por que não usar uma lista
Uma lista pode remover elementos da frente, mas pop(0) custa O(n), pois todos os outros itens precisam ser deslocados para a esquerda. Isso é lento demais para entradas grandes.
q = []
q.pop(0) # O(n), avoid thisConheça collections.deque
O collections.deque é uma fila de duas extremidades que adiciona e remove elementos de ambos os lados em O(1). É a opção preferida em competições.
from collections import deque
q = deque()Enfileire no final
Coloque novos itens na extremidade direita usando append, exatamente como em uma lista. Essa é a parte de trás da fila.
q.append(1)
q.append(2)Desenfileire pela frente
Remova o item mais antigo pela esquerda usando popleft, que executa em tempo constante e proporciona o comportamento FIFO verdadeiro.
first = q.popleft() # returns 1As duas extremidades estão abertas
Um deque também aceita appendleft e pop pela direita. Essa flexibilidade permite que uma única estrutura funcione como pilha ou fila.
q.appendleft(0)
last = q.pop()Verifique antes de remover
Remover elementos de um deque vazio gera um erro; portanto, verifique while q nos laços para manter seu percurso seguro.
while q:
x = q.popleft()As filas impulsionam o BFS
O uso mais comum em competições é o BFS. Você enfileira um nó inicial, depois continua removendo o elemento da frente e colocando seus vizinhos na fila.
Um pequeno esqueleto de BFS
Este laço visita os nós camada por camada. Cada vizinho é append e processado mais tarde na ordem de chegada.
while q:
node = q.popleft()
for nb in graph[node]:
q.append(nb)Limite o tamanho do deque
Definir maxlen faz um deque descartar o item mais antigo quando está cheio, o que é perfeito para janelas deslizantes e acompanhamento do histórico recente.
window = deque(maxlen=3)Uma estrutura, muitas funções
Lembre-se de que um deque é rápido nas duas extremidades. Portanto, use-o sempre que precisar de uma fila, uma pilha ou um buffer deslizante.
Verificação rápida
Você precisa remover rapidamente elementos da frente de uma fila. Qual opção é a correta?
Recapitulação: deque é a fila rápida
Você conheceu collections.deque: append e popleft para FIFO em O(1), duas extremidades abertas e maxlen para janelas. Essa estrutura é a base do BFS. 🎯
Perguntas Frequentes
A aula “Filas e collections.deque” é grátis?
Sim — o texto completo de “Filas e collections.deque” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Filas e collections.deque”?
Insira e remova rapidamente pelas duas extremidades. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Filas e collections.deque”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Pilhas para Correspondência de Parênteses
- Pilha Monotônica: Próximo Elemento Maior
- Filas e collections.deque
- Máximo em Janela Deslizante com Deque