Colas en Python - Deque (Double-Ended Queue)

7.1 Concepto y ventajas

Un deque es una cola doblemente terminada que permite insertar y extraer elementos tanto por el frente como por el final. Mantiene el orden de llegada, pero admite patrones de acceso más flexibles que una cola FIFO estricta.

Simetría: las operaciones son equivalentes en ambos extremos, lo que simplifica algoritmos que alternan productores y consumidores.
Compatibilidad con stacks: puede comportarse como pila o como cola dependiendo del extremo utilizado.
Reducción de copias: evita desplazar elementos internos, incluso cuando se convierte en una estructura circular.

Es la base de planificadores, caches LRU y estructuras de datos avanzadas como los algoritmos de ventana deslizante.

7.2 Operaciones básicas

La interfaz mínima se compone de cuatro operaciones de modificación y dos accesos de solo lectura:

appendleft / append: insertan en el frente o en el final.
popleft / pop: retiran y retornan el valor asociado.
front / back: leen sin extraer, devolviendo None si la estructura está vacía.

En Python collections.deque ya ofrece estas operaciones con complejidad O(1) amortizada.

7.3 Representación en Python

Python provee collections.deque, que internamente es un buffer de bloques doblemente enlazados optimizado para inserciones y extracciones en los extremos.

Si necesitas un control total sobre nodos y recorridos, también puedes implementar tu propio deque con una lista doblemente enlazada.

7.4 Enfoque con `collections.deque`

deque del módulo collections es la opción recomendada en Python para doble extremo. Usa bloques enlazados y ofrece complejidad O(1) amortizada.

from collections import deque


def demo_deque():
  d = deque()
  d.append(10)        # push back
  d.appendleft(5)     # push front
  d.append(20)

  print("front:", d[0])
  print("back:", d[-1])

  print("pop front:", d.popleft())
  print("pop back:", d.pop())
  print("estado final:", list(d))


if __name__ == "__main__":
  demo_deque()

Los pop simétricos aplican el mismo principio y pueden integrarse en ciclos que consumen mientras la estructura no esté vacía.

7.5 Implementación con lista doble

Si necesitas personalizar validaciones o almacenar metadatos en cada nodo, puedes implementar tu propio deque con una lista doblemente enlazada.

class Nodo:
  def __init__(self, dato):
    self.dato = dato
    self.anterior = None
    self.siguiente = None


class DequeLista:
  def __init__(self):
    self.frente = None
    self.final = None
    self.cantidad = 0

  def push_front(self, valor):
    nuevo = Nodo(valor)
    nuevo.siguiente = self.frente
    if self.frente:
      self.frente.anterior = nuevo
    else:
      self.final = nuevo
    self.frente = nuevo
    self.cantidad += 1

  def push_back(self, valor):
    nuevo = Nodo(valor)
    nuevo.anterior = self.final
    if self.final:
      self.final.siguiente = nuevo
    else:
      self.frente = nuevo
    self.final = nuevo
    self.cantidad += 1

  def pop_front(self):
    if not self.frente:
      return None
    nodo = self.frente
    self.frente = nodo.siguiente
    if self.frente:
      self.frente.anterior = None
    else:
      self.final = None
    self.cantidad -= 1
    return nodo.dato

  def pop_back(self):
    if not self.final:
      return None
    nodo = self.final
    self.final = nodo.anterior
    if self.final:
      self.final.siguiente = None
    else:
      self.frente = None
    self.cantidad -= 1
    return nodo.dato

Este estilo evita reasignar buffers y mantiene la complejidad constante aun cuando el deque crece o se vacía repetidamente.

7.6 Casos de uso prácticos

Ventana deslizante: los algoritmos de máximo en ventanas utilizan un deque para expulsar elementos fuera de rango por el frente y agregar nuevos por el final.
Planificadores de tareas: sistemas operativos como FreeBSD emplean deques para alternar tareas interactivas y de fondo.
Backtracking: combinar pops en ambos extremos facilita explorar grafos en ordenes personalizados.

Siempre documenta si el deque es seguro para hilos o si requiere protección externa (mutex, spinlocks) antes de exponerlo a un scheduler.

7.7 Ejemplo completo en Python

El siguiente programa implementa un deque mediante lista doble y expone todas las operaciones, además de una función imprimir para depurar el estado.

class Nodo:
  def __init__(self, dato):
    self.dato = dato
    self.anterior = None
    self.siguiente = None


class Deque:
  def __init__(self):
    self.frente = None
    self.final = None
    self.cantidad = 0

  def push_front(self, valor):
    nuevo = Nodo(valor)
    nuevo.siguiente = self.frente
    if self.frente:
      self.frente.anterior = nuevo
    else:
      self.final = nuevo
    self.frente = nuevo
    self.cantidad += 1

  def push_back(self, valor):
    nuevo = Nodo(valor)
    nuevo.anterior = self.final
    if self.final:
      self.final.siguiente = nuevo
    else:
      self.frente = nuevo
    self.final = nuevo
    self.cantidad += 1

  def pop_front(self):
    if not self.frente:
      return None
    nodo = self.frente
    self.frente = nodo.siguiente
    if self.frente:
      self.frente.anterior = None
    else:
      self.final = None
    self.cantidad -= 1
    return nodo.dato

  def pop_back(self):
    if not self.final:
      return None
    nodo = self.final
    self.final = nodo.anterior
    if self.final:
      self.final.siguiente = None
    else:
      self.frente = None
    self.cantidad -= 1
    return nodo.dato

  def imprimir(self):
    elementos = []
    actual = self.frente
    while actual:
      elementos.append(str(actual.dato))
      actual = actual.siguiente
    print(f"[deque] cantidad={self.cantidad} -> {' '.join(elementos)}")


if __name__ == "__main__":
  deque = Deque()

  deque.push_back(10)
  deque.push_back(20)
  deque.push_front(5)
  deque.imprimir()

  print("pop_front =", deque.pop_front())
  deque.imprimir()

  deque.push_front(1)
  deque.push_back(99)
  deque.imprimir()

  print("pop_back =", deque.pop_back())
  deque.imprimir()

Ejecutar en el editor online

Ejecuta el programa y observa cómo las operaciones afectan al contador y a los nodos interiores para validar que no quedan referencias colgantes.

Retornar

7 - Deque (Double-Ended Queue)