Python Deque: Filas de Dupla Extremidade Rápidas com collections.deque

Name

Soren Atelier

Updated on 10/02/2026

Usar uma lista Python como fila ou pilha parece natural -- até você começar a remover do lado esquerdo. Chamar list.pop(0) é uma operação O(n) porque cada elemento restante precisa se deslocar uma posição para frente. Em um loop que processa milhões de itens, esse custo oculto transforma um pipeline rápido em algo lento. O mesmo problema afeta list.insert(0, x), que também é O(n). Para qualquer carga de trabalho que toca ambas as extremidades de uma sequência, listas simples se tornam uma armadilha de desempenho.

O collections.deque do Python (fila de dupla extremidade, pronunciado "dek") resolve isso fornecendo operações append e pop O(1) de ambas as extremidades. É implementado como uma lista duplamente encadeada de blocos de comprimento fixo, proporcionando desempenho em tempo constante em cada extremidade enquanto ainda suporta acesso indexado. Este guia cobre tudo que você precisa saber sobre deque: criação, operações principais, filas limitadas, segurança de threads e padrões práticos.

Criando uma Deque

from collections import deque
 
d = deque([1, 2, 3, 4, 5])
print(d)  # deque([1, 2, 3, 4, 5])
 
letters = deque("hello")
print(letters)  # deque(['h', 'e', 'l', 'l', 'o'])
 
d = deque()
 
d = deque(maxlen=3)
d.append(1)
d.append(2)
d.append(3)
d.append(4)  # Adicionar à direita remove o item mais à esquerda
print(d)  # deque([2, 3, 4], maxlen=3)

Operações Principais

Deque fornece operações simétricas para ambas as extremidades da sequência.

from collections import deque
 
d = deque([2, 3, 4])
 
d.append(5)
d.appendleft(1)
print(d)  # deque([1, 2, 3, 4, 5])
 
right = d.pop()
left = d.popleft()
print(right)  # 5
print(left)   # 1
 
d = deque([3, 4, 5])
d.extend([6, 7, 8])
d.extendleft([2, 1, 0])    # nota: ordem invertida
print(d)  # deque([0, 1, 2, 3, 4, 5, 6, 7, 8])

Note que extendleft processa itens um de cada vez, inserindo cada um na posição 0. A ordem resultante é invertida comparada ao iterável de entrada.

Outros Métodos Úteis

from collections import deque
 
d = deque([1, 2, 3, 2, 4, 2, 5])
 
print(d.count(2))   # 3
print(d.index(3))   # 2
d.remove(2)
d.insert(1, 99)
d.reverse()
d.clear()

Rotação com rotate()

O método rotate() rotaciona a deque n passos para a direita. N negativo rotaciona para a esquerda.

from collections import deque
 
d = deque([1, 2, 3, 4, 5])
 
d.rotate(2)
print(d)       # deque([4, 5, 1, 2, 3])
 
d.rotate(-3)
print(d)       # deque([2, 3, 4, 5, 1])

Deques Limitadas com maxlen

Deques limitadas são uma das funcionalidades mais práticas. Ao definir maxlen, você cria um buffer de tamanho fixo que automaticamente descarta os itens mais antigos quando a capacidade é atingida.

Janela Deslizante / Média Móvel

from collections import deque
 
def moving_average(data, window_size):
    """Calculate moving average using a bounded deque."""
    window = deque(maxlen=window_size)
    averages = []
    for value in data:
        window.append(value)
        if len(window) == window_size:
            averages.append(sum(window) / window_size)
    return averages
 
prices = [100, 102, 104, 103, 105, 107, 106, 108, 110, 109]
print(moving_average(prices, 3))

Fim de Arquivo (Últimas N Linhas)

from collections import deque
 
def tail(filename, n=10):
    """Return the last n lines of a file."""
    with open(filename) as f:
        return deque(f, maxlen=n)

Deque como Fila (FIFO)

from collections import deque
 
queue = deque()
queue.append("first")
queue.append("second")
queue.append("third")
 
print(queue.popleft())    # first
print(queue.popleft())    # second
print(queue.popleft())    # third

Aqui é onde deque realmente brilha sobre uma lista. Com uma lista, list.pop(0) é O(n). Com deque, popleft() é O(1).

Deque como Pilha (LIFO)

from collections import deque
 
stack = deque()
stack.append("first")
stack.append("second")
stack.append("third")
 
print(stack.pop())    # third
print(stack.pop())    # second
print(stack.pop())    # first

Comparação de Desempenho: Deque vs Lista

Benchmark

from collections import deque
import time
 
def benchmark_left_operations(n):
    """Compare popleft/appendleft performance."""
    data = list(range(n))
    start = time.perf_counter()
    while data:
        data.pop(0)
    list_time = time.perf_counter() - start
 
    data = deque(range(n))
    start = time.perf_counter()
    while data:
        data.popleft()
    deque_time = time.perf_counter() - start
 
    print(f"n={n:>8,}")
    print(f"  list.pop(0):     {list_time:.4f}s")
    print(f"  deque.popleft(): {deque_time:.4f}s")
    print(f"  Speedup: {list_time / deque_time:.1f}x")
 
benchmark_left_operations(100_000)

Segurança de Threads

O deque do Python fornece operações append(), appendleft(), pop() e popleft() thread-safe. Estes métodos são atômicos no CPython porque executam dentro de uma única instrução de bytecode, protegidos pelo GIL.

Para sistemas de produção que precisam de comportamento bloqueante, use queue.Queue em vez disso.

Padrões Práticos

Travessia BFS de Grafos

from collections import deque
 
def bfs(graph, start):
    """Breadth-first search using deque as queue."""
    visited = set()
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            order.append(node)
            queue.extend(
                neighbor for neighbor in graph[node]
                if neighbor not in visited
            )
    return order
 
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
 
print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

Máximo da Janela Deslizante

from collections import deque
 
def sliding_window_max(nums, k):
    """Find maximum in each sliding window of size k."""
    result = []
    window = deque()
    for i, num in enumerate(nums):
        while window and window[0] < i - k + 1:
            window.popleft()
        while window and nums[window[-1]] < num:
            window.pop()
        window.append(i)
        if i >= k - 1:
            result.append(nums[window[0]])
    return result
 
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(nums, 3))
# [3, 3, 5, 5, 6, 7]

Histórico de Desfazer

Uma deque limitada funciona como um excelente histórico de desfazer que automaticamente esquece as ações mais antigas:

from collections import deque
 
class TextEditor:
    def __init__(self, max_undo=50):
        self.content = ""
        self._undo_stack = deque(maxlen=max_undo)
 
    def type_text(self, text):
        self._undo_stack.append(self.content)
        self.content += text
 
    def delete_last(self, n=1):
        self._undo_stack.append(self.content)
        self.content = self.content[:-n]
 
    def undo(self):
        if self._undo_stack:
            self.content = self._undo_stack.pop()
 
editor = TextEditor(max_undo=10)
editor.type_text("Hello")
editor.type_text(" World")
print(editor.content)   # Hello World
editor.undo()
print(editor.content)   # Hello

Testando Desempenho de Estruturas de Dados no Jupyter

Ao fazer benchmarking de deques contra listas ou ajustar maxlen para sua carga de trabalho específica, notebooks interativos são inestimáveis. RunCell (opens in a new tab) fornece um ambiente Jupyter com IA onde você pode perfilar operações de estruturas de dados, visualizar diferenças de desempenho e receber sugestões inteligentes de otimização.

FAQ

O que é uma deque em Python?

Uma deque (fila de dupla extremidade) é uma estrutura de dados do módulo collections do Python que suporta operações append e pop O(1) de ambas as extremidades. Diferente de uma lista, que leva O(n) para inserir ou remover do início, uma deque fornece desempenho em tempo constante para operações em qualquer extremidade.

Quando devo usar deque em vez de list?

Use deque quando precisar de inserção ou remoção rápida em ambas as extremidades da sequência, como implementar filas (FIFO), manter janelas deslizantes ou fazer travessias BFS. Fique com list quando precisar de acesso aleatório rápido por índice (O(1) para lista vs O(n) para deque).

Python deque é thread-safe?

Sim, os métodos append(), appendleft(), pop() e popleft() são thread-safe no CPython. Estas operações são atômicas porque completam dentro de uma única instrução de bytecode, protegidas pelo GIL. No entanto, operações compostas não são atômicas, então use queue.Queue para padrões produtor-consumidor que precisam de semântica bloqueante.

O que maxlen faz na deque?

O parâmetro maxlen cria uma deque limitada com um tamanho máximo fixo. Quando a deque está cheia e um novo item é adicionado, o item na extremidade oposta é automaticamente descartado. Isto é útil para implementar janelas deslizantes, logs de atividade recente e históricos de desfazer.

Como deque se compara a queue.Queue?

collections.deque é projetado para velocidade. queue.Queue encapsula uma deque internamente mas adiciona primitivas de sincronização de threads. Use deque para código single-thread. Use queue.Queue quando precisar de operações get() e put() bloqueantes em cenários produtor-consumidor multi-thread.

Conclusão

O collections.deque do Python é uma das estruturas de dados mais úteis mas subestimadas da biblioteca padrão. Ele elimina a penalidade O(n) das operações do lado esquerdo de listas, fornece buffering limitado integrado com maxlen, oferece operações atômicas thread-safe e serve como base para filas, pilhas, janelas deslizantes e algoritmos de travessia de grafos.

A decisão chave é direta: se seu código toca ambas as extremidades de uma sequência, use deque. Se você precisa de acesso aleatório rápido por índice, use list. Para a maioria dos padrões de fila e pilha, deque deve ser sua escolha padrão.