Python Deque: Colas de Doble Extremo Rápidas con collections.deque

Name

Soren Atelier

Updated on 10/2/2026

Usar una lista de Python como cola o pila parece natural -- hasta que empiezas a sacar elementos del lado izquierdo. Llamar a list.pop(0) es una operación O(n) porque cada elemento restante debe desplazarse una posición hacia adelante. En un bucle que procesa millones de elementos, este costo oculto convierte un pipeline rápido en algo lento. El mismo problema afecta a list.insert(0, x), que también es O(n). Para cualquier carga de trabajo que toque ambos extremos de una secuencia, las listas simples se convierten en una trampa de rendimiento.

collections.deque de Python (cola de doble extremo, pronunciado "dek") soluciona esto proporcionando operaciones append y pop O(1) desde ambos extremos. Está implementado como una lista doblemente enlazada de bloques de longitud fija, dándole rendimiento de tiempo constante en cada extremo mientras sigue soportando acceso indexado. Esta guía cubre todo lo que necesitas saber sobre deque: creación, operaciones principales, colas limitadas, seguridad de hilos y patrones prácticos.

Crear una Deque

from collections import deque
 
# Desde una lista
d = deque([1, 2, 3, 4, 5])
print(d)  # deque([1, 2, 3, 4, 5])
 
# Desde un string
letters = deque("hello")
print(letters)  # deque(['h', 'e', 'l', 'l', 'o'])
 
# Deque vacía
d = deque()
 
# Con maxlen (deque limitada)
d = deque(maxlen=3)
d.append(1)
d.append(2)
d.append(3)
d.append(4)  # Agregar a la derecha elimina el elemento más a la izquierda
print(d)  # deque([2, 3, 4], maxlen=3)

Operaciones Principales

Deque proporciona operaciones simétricas para ambos extremos de la secuencia.

from collections import deque
 
d = deque([2, 3, 4])
 
# append y appendleft
d.append(5)        # Agregar al extremo derecho
d.appendleft(1)    # Agregar al extremo izquierdo
print(d)  # deque([1, 2, 3, 4, 5])
 
# pop y popleft
right = d.pop()       # Remover del extremo derecho
left = d.popleft()    # Remover del extremo izquierdo
print(right)  # 5
print(left)   # 1
 
# extend y extendleft
d = deque([3, 4, 5])
d.extend([6, 7, 8])        # Agregar múltiples elementos a la derecha
d.extendleft([2, 1, 0])    # Agregar a la izquierda (nota: orden invertido)
print(d)  # deque([0, 1, 2, 3, 4, 5, 6, 7, 8])

Nota que extendleft procesa elementos uno a la vez, insertando cada uno en la posición 0. El orden resultante está invertido comparado con el iterable de entrada.

Otros Métodos Útiles

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)          # Remover primera ocurrencia
d.insert(1, 99)      # Insertar en posición
d.reverse()          # Invertir en su lugar
d.clear()            # Limpiar todos los elementos

Rotación con rotate()

El método rotate() rota la deque n pasos a la derecha. Un n negativo rota a la izquierda.

from collections import deque
 
d = deque([1, 2, 3, 4, 5])
 
d.rotate(2)    # Rotar 2 pasos a la derecha
print(d)       # deque([4, 5, 1, 2, 3])
 
d.rotate(-3)   # Rotar 3 pasos a la izquierda
print(d)       # deque([2, 3, 4, 5, 1])

Deques Limitadas con maxlen

Las deques limitadas son una de las características más prácticas. Al establecer maxlen, creas un buffer de tamaño fijo que automáticamente descarta los elementos más antiguos cuando se alcanza la capacidad.

Ventana Deslizante / Promedio Móvil

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))
# [102.0, 103.0, 104.0, 105.0, 106.0, 107.0, 108.0, 109.0]

Cola de un Archivo (Últimas N Líneas)

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)

Esto es notablemente eficiente. La deque limitada lee todo el archivo pero solo mantiene las últimas n líneas en memoria.

Deque como Cola (FIFO)

Usa append() para encolar y popleft() para desencolar:

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

Aquí es donde deque realmente brilla sobre una lista. Con una lista, list.pop(0) es O(n). Con deque, popleft() es O(1).

Deque como Pila (LIFO)

Usa append() para apilar y pop() para desapilar del mismo extremo:

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

Comparación de Rendimiento: Deque vs Lista

La conclusión: usa deque cuando necesites operaciones rápidas en ambos extremos. Usa list cuando necesites acceso aleatorio rápido por índice.

Benchmark

from collections import deque
import time
 
def benchmark_left_operations(n):
    """Compare popleft/appendleft performance."""
    # List: pop from position 0
    data = list(range(n))
    start = time.perf_counter()
    while data:
        data.pop(0)
    list_time = time.perf_counter() - start
 
    # Deque: popleft
    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)

Seguridad de Hilos

deque de Python proporciona operaciones append(), appendleft(), pop() y popleft() seguras para hilos. Estos métodos son atómicos en CPython porque se ejecutan dentro de una sola instrucción de bytecode, protegidos por el GIL.

Para sistemas de producción que necesitan comportamiento bloqueante (esperar elementos), usa queue.Queue en su lugar, que envuelve deque internamente y agrega bloqueos y variables de condición apropiados.

Patrones Prácticos

Recorrido 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 en Ventana Deslizante

from collections import deque
 
def sliding_window_max(nums, k):
    """Find maximum in each sliding window of size k."""
    result = []
    window = deque()  # Stores indices of useful elements
    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]

Historial de Deshacer

Una deque limitada es excelente como historial de deshacer que automáticamente olvida las acciones más antiguas:

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

Probar Rendimiento de Estructuras de Datos en Jupyter

Al hacer benchmarking de deques contra listas o ajustar maxlen para tu carga de trabajo específica, los notebooks interactivos son invaluables. RunCell (opens in a new tab) proporciona un entorno Jupyter impulsado por IA donde puedes perfilar operaciones de estructuras de datos, visualizar diferencias de rendimiento y obtener sugerencias inteligentes de optimización.

FAQ

¿Qué es una deque en Python?

Una deque (cola de doble extremo) es una estructura de datos del módulo collections de Python que soporta operaciones append y pop O(1) desde ambos extremos. A diferencia de una lista, que toma O(n) tiempo para insertar o remover del frente, una deque proporciona rendimiento de tiempo constante para operaciones en cualquier extremo.

¿Cuándo debería usar deque en lugar de list?

Usa deque cuando necesites inserción o remoción rápida en ambos extremos de la secuencia, como implementar colas (FIFO), mantener ventanas deslizantes o hacer recorridos BFS. Quédate con list cuando necesites acceso aleatorio rápido por índice (O(1) para lista vs O(n) para deque).

¿Es Python deque seguro para hilos?

Sí, los métodos append(), appendleft(), pop() y popleft() son seguros para hilos en CPython. Estas operaciones son atómicas porque se completan dentro de una sola instrucción de bytecode, protegidas por el GIL. Sin embargo, las operaciones compuestas no son atómicas, así que usa queue.Queue para patrones productor-consumidor que necesiten semántica bloqueante.

¿Qué hace maxlen en deque?

El parámetro maxlen crea una deque limitada con un tamaño máximo fijo. Cuando la deque está llena y se agrega un nuevo elemento, el elemento en el extremo opuesto se descarta automáticamente. Esto es útil para implementar ventanas móviles, registros de actividad reciente e historiales de deshacer.

¿Cómo se compara deque con queue.Queue?

collections.deque está diseñado para velocidad. queue.Queue envuelve una deque internamente pero agrega primitivas de sincronización de hilos como bloqueos y variables de condición. Usa deque para código de un solo hilo. Usa queue.Queue cuando necesites operaciones get() y put() bloqueantes en escenarios productor-consumidor multi-hilo.

Conclusión

collections.deque de Python es una de las estructuras de datos más útiles pero menos apreciadas de la biblioteca estándar. Elimina la penalización O(n) de las operaciones del lado izquierdo de listas, proporciona buffering limitado incorporado con maxlen, ofrece operaciones atómicas seguras para hilos y sirve como base para colas, pilas, ventanas deslizantes y algoritmos de recorrido de grafos.

La decisión es sencilla: si tu código toca ambos extremos de una secuencia, usa deque. Si necesitas acceso aleatorio rápido por índice, usa list. Para la mayoría de patrones de cola y pila, deque debería ser tu elección predeterminada.