Implementação de Filas e Deque
Crie uma fila com o deque do Python, implemente uma fila circular e resolva o máximo em uma janela deslizante usando um deque monotônico.
Implementação de Filas e Deque é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 2 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 Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
A estrutura de dados Queue
Uma fila é uma estrutura de dados do tipo primeiro a entrar, primeiro a sair (FIFO). O primeiro elemento inserido com enqueue é o primeiro elemento removido com dequeue — como em uma fila de atendimento em uma loja. As operações fundamentais são enqueue (adicionar ao fim) e dequeue (remover do início). Ambas devem custar O(1) para que a fila seja eficiente.
Usar uma lista do Python como fila parece tentador, mas está errado: list.pop(0) custa O(n), porque desloca todos os elementos. A ferramenta correta é collections.deque, que fornece appendleft, append, popleft e pop em O(1).
from collections import deque
queue = deque()
# Enqueue (add to rear)
queue.append(10)
queue.append(20)
queue.append(30)
print('Queue:', queue) # deque([10, 20, 30])
# Peek front
print('Front:', queue[0]) # 10
# Dequeue (remove from front)
print('Dequeued:', queue.popleft()) # 10
print('Queue after:', queue) # deque([20, 30])Classe Queue usando deque
Encapsule deque em uma classe Queue com operações nomeadas, de acordo com o que os entrevistadores esperam. Internamente, enqueue chama append e dequeue chama popleft. A operação peek lê queue[0] sem removê-lo.
from collections import deque
class Queue:
def __init__(self):
self._data = deque()
def enqueue(self, val):
self._data.append(val)
def dequeue(self):
if self.is_empty():
raise IndexError('dequeue from empty queue')
return self._data.popleft()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty queue')
return self._data[0]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
q = Queue()
q.enqueue(1); q.enqueue(2); q.enqueue(3)
print(q.peek()) # 1
print(q.dequeue()) # 1
print(len(q)) # 2BFS com uma fila
A aplicação clássica de uma fila é a Busca em largura (BFS). Faça enqueue da raiz; enquanto a fila não estiver vazia, faça dequeue de um nó, processe-o e faça enqueue de seus vizinhos não visitados. Como os nós são processados nível a nível, a BFS encontra naturalmente o caminho mais curto em um grafo não ponderado. A fila sempre contém nós de, no máximo, dois níveis adjacentes.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
return order
graph = {0:[1,2], 1:[0,3,4], 2:[0,5], 3:[1], 4:[1], 5:[2]}
print(bfs(graph, 0)) # [0, 1, 2, 3, 4, 5]Fila circular (LeetCode 622)
LeetCode 622 'Projetar fila circular': implemente uma fila de capacidade fixa que dê a volta ao chegar ao fim. Use um vetor de tamanho k e dois ponteiros: head e tail. Faça enqueue no fim, dequeue no início e calcule as posições módulo k. Uma variável de contagem distingue a fila cheia da vazia; caso contrário, ambas têm a mesma posição de início e fim módulo k.
class MyCircularQueue:
def __init__(self, k):
self.data = [0] * k
self.head = 0
self.tail = 0
self.count = 0
self.k = k
def enQueue(self, value):
if self.isFull(): return False
self.data[self.tail] = value
self.tail = (self.tail + 1) % self.k
self.count += 1
return True
def deQueue(self):
if self.isEmpty(): return False
self.head = (self.head + 1) % self.k
self.count -= 1
return True
def Front(self):
return -1 if self.isEmpty() else self.data[self.head]
def Rear(self):
return -1 if self.isEmpty() else self.data[(self.tail - 1) % self.k]
def isEmpty(self): return self.count == 0
def isFull(self): return self.count == self.k
cq = MyCircularQueue(3)
print(cq.enQueue(1), cq.enQueue(2), cq.enQueue(3)) # True True True
print(cq.enQueue(4)) # False (full)
print(cq.Rear()) # 3
print(cq.isFull()) # True
print(cq.deQueue()) # True
print(cq.enQueue(4)) # TrueMáximo da janela deslizante com deque monotônico
LeetCode 239 'Máximo da janela deslizante': para cada janela de tamanho k, encontre o maior elemento. A solução de força bruta custa O(n*k). A abordagem O(n) usa um deque monotonicamente decrescente que armazena índices. Para cada novo elemento: remova do início os índices que estão fora da janela; remova do fim os índices com valores menores (eles nunca poderão ser o máximo em nenhuma janela futura). O início sempre contém o máximo.
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements from back
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]Por que usar deque em vez de uma lista para uma fila?
list.pop(0) do Python remove o primeiro elemento em O(n), porque todos os elementos restantes precisam ser deslocados uma posição para a esquerda. Para n inserções e n remoções, isso resulta em O(n²) no total. collections.deque é uma lista duplamente encadeada de blocos de tamanho fixo; popleft custa O(1), porque apenas ajusta um ponteiro. Em uma BFS em um grafo com 10^5 nós, a diferença entre O(n) e O(n²) é a diferença entre 100 ms e 100 segundos.
import timeit
n = 10000
# Using list (O(n) per popleft)
list_time = timeit.timeit(
stmt='q = list(range(n)); [q.pop(0) for _ in range(n)]',
globals={'n': n}, number=10
)
# Using deque (O(1) per popleft)
from collections import deque
deque_time = timeit.timeit(
stmt='q = deque(range(n)); [q.popleft() for _ in range(n)]',
globals={'n': n, 'deque': deque}, number=10
)
print(f'List: {list_time:.4f}s')
print(f'Deque: {deque_time:.4f}s')
print(f'Speedup: {list_time / deque_time:.1f}x')Percurso em largura de árvore binária (LeetCode 102)
LeetCode 102 'Percurso em largura de árvore binária': retorne todos os valores dos nós, nível por nível. Use uma fila; no início de cada nível, registre o tamanho da fila (essa é a quantidade de nós nesse nível). Faça dequeue exatamente dessa quantidade de nós, coletando seus valores e fazendo enqueue de seus filhos. Repita até que a fila fique vazia.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(levelOrder(root)) # [[3], [9, 20], [15, 7]]Fila de prioridade com heapq
O módulo heapq do Python fornece um heap mínimo (fila de prioridade): o menor elemento é sempre removido primeiro. heapq.heappush(h, item) adiciona um elemento em O(log n), e heapq.heappop(h) remove o mínimo em O(log n). Para tarefas como o algoritmo de Dijkstra e problemas dos k maiores elementos, heapq substitui a fila simples.
import heapq
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
heapq.heappush(pq, 2)
print('Min:', heapq.heappop(pq)) # 1
print('Min:', heapq.heappop(pq)) # 2
print('Min:', heapq.heappop(pq)) # 3
# Tasks with priorities
tasks = [(2, 'send email'), (1, 'fix bug'), (3, 'write docs')]
heapq.heapify(tasks)
while tasks:
priority, task = heapq.heappop(tasks)
print(f'Priority {priority}: {task}')Padrão de plano de fundo: fila para Escada de Palavras
LeetCode 127 «Escada de Palavras»: encontre o número mínimo de substituições de um único caractere para transformar uma palavra em outra, usando apenas palavras do dicionário. Modele o problema como um grafo em que as arestas conectam palavras que diferem em um caractere. O BFS nesse grafo encontra o caminho mais curto (o número mínimo de etapas) em O(n * L²), onde n é o tamanho do dicionário e L é o comprimento das palavras.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + ch + word[i+1:]
if new_word == endWord:
return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
print(ladderLength('hit', 'cog', ['hot','dot','dog','lot','log','cog'])) # 5fila de duas pontas como fila com extremidades duplas
collections.deque é uma fila de duas pontas: pode adicionar e remover elementos com eficiência em ambas as extremidades. Métodos: appendleft e popleft para a frente; append e pop para a parte de trás. Isso permite que a fila de duas pontas funcione tanto como uma fila FIFO (adicionar à direita + popleft) quanto como uma pilha LIFO (append + pop). O máximo em uma janela deslizante usa as duas extremidades: remove índices antigos pela esquerda e valores menores pela direita.
from collections import deque
dq = deque([3, 4, 5])
dq.appendleft(2) # add to front: [2,3,4,5]
dq.appendleft(1) # add to front: [1,2,3,4,5]
dq.append(6) # add to rear: [1,2,3,4,5,6]
print(dq.popleft()) # 1 (from front)
print(dq.pop()) # 6 (from rear)
print(list(dq)) # [2, 3, 4, 5]Resumo: fila, fila de duas pontas e heap
Escolha a ferramenta certa para o problema. Use uma fila simples (fila de duas pontas) para processamento FIFO e BFS. Use uma fila de duas pontas monotônica quando precisar do máximo ou mínimo em uma janela deslizante — ela mantém uma invariante ordenada removendo elementos dominados. Use uma fila de prioridade (heapq) quando precisar do mínimo ou máximo global, independentemente da ordem, como nos problemas de Dijkstra ou dos k maiores elementos. Saber qual ferramenta escolher e por quê é uma habilidade importante que os entrevistadores avaliam.
Verificação rápida
Verifique sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação apresentados nesta lição.
Recapitulação da lição
Nesta lição, você aprendeu que: collections.deque fornece operações de inserção e remoção da fila em O(1), sendo a implementação correta de uma fila em Python, o BFS usa uma fila para processar nós nível a nível, encontrando os caminhos mais curtos em grafos não ponderados e uma fila de duas pontas monotônica decrescente resolve o máximo em uma janela deslizante em O(n), removendo índices dominados. A seguir, exploraremos em profundidade o padrão de pilha monotônica.
Perguntas Frequentes
A aula “Implementação de Filas e Deque” é grátis?
Sim — o texto completo de “Implementação de Filas e 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 Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Implementação de Filas e Deque”?
Crie uma fila com o deque do Python, implemente uma fila circular e resolva o máximo em uma janela deslizante usando um deque monotônico. Você pratica Coding Interview Prep 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 Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep 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 2 de 4.
Quanto tempo leva a aula “Implementação de Filas e 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 Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep 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
- Implementação e Aplicações de Pilhas
- Implementação de Filas e Deque
- Padrão da Pilha Monotônica
- Simulação Mútua de Pilha e Fila