El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Colas Dobles (Deques)

Siguiente ►
►

Este es el capítulo donde saldamos la primera deuda del módulo 3. Nuestro HistorialConLimite apilaba acciones por un extremo pero, al llenarse, descartaba por el otro con un pop(0) O(n) que entonces calificamos de "tolerable"... prometiendo una solución elegante. La estructura que lo arregla es la cola doble o deque (double-ended queue): un TDA que permite insertar y extraer en O(1) por ambos extremos. En Python viene de serie como collections.deque, que ya mencionamos de pasada en el módulo 2 ("una doblemente enlazada por bloques"); hoy la estudiaremos a fondo: sus operaciones, sus costes, su parámetro estrella maxlen y —igual de importante— cuándo no usarla. También veremos que, en realidad, la implementación conceptual ya la tenemos casi escrita desde el módulo 2, y la pondremos a trabajar en TaskFlow con una ventana deslizante de productividad.

Contenido

  1. El TDA deque: un contrato con cuatro puertas
  2. Deque, pila y cola: una generalización
  3. collections.deque a fondo
  4. Cuándo NO usar un deque
  5. La promesa cumplida: HistorialConLimite con maxlen
  6. Implementación conceptual sobre ListaDoblementeEnlazada
  7. TaskFlow: ventana deslizante de tareas completadas
  8. Bonus clásico: palíndromos

El TDA deque: un contrato con cuatro puertas

Un deque es una secuencia con acceso restringido a los dos extremos, y con las cuatro combinaciones permitidas:

Operación Extremo Promesa de coste
encolar_final(x) Derecho (final) O(1)
encolar_frente(x) Izquierdo (frente) O(1)
desencolar_final() Derecho O(1)
desencolar_frente() Izquierdo O(1)
frente() / final() Consulta ambos extremos O(1)
esta_vacia() / tamano() — O(1) 
graph LR
    EF["encolar_frente / desencolar_frente"] <--> D["[ frente | ... | final ]"]
    D <--> EFin["encolar_final / desencolar_final"]

Lo que sigue prohibido —y esto define al deque frente a una lista general— es tocar el interior: no hay inserción ni borrado por el medio en el contrato. Toda la potencia se concentra en los bordes, y a cambio los bordes son siempre O(1).

Deque, pila y cola: una generalización

El deque es el TDA más general de los tres que conocemos de acceso restringido; pila y cola son casos particulares obtenidos cerrando puertas:

Para obtener... Usa solo... Política resultante
Una pila encolar_final + desencolar_final LIFO (un solo extremo)
Una cola encolar_final + desencolar_frente FIFO (extremos opuestos)
Un deque Las cuatro Ambas, a elección en cada operación

Esto explica por qué en Python profesional collections.deque se usa también como pila y como cola: una sola estructura bien hecha cubre los tres contratos. Cuidado, no obstante, con el razonamiento inverso: que pueda usarse de tres formas no significa que tu código deba mezclarlas. Si tu variable es conceptualmente una cola, usa solo el par FIFO; el nombre de la variable y la disciplina de acceso documentan la intención (es la lección de "expón solo el contrato" de 04-02).

collections.deque a fondo

collections.deque es la implementación de deque de la biblioteca estándar. Internamente —lo adelantamos en el módulo 2— es una lista doblemente enlazada de bloques: en lugar de un nodo por elemento, enlaza bloques de 64 casillas, lo que reduce muchísimo el coste en memoria y el número de saltos entre nodos, conservando O(1) en ambos extremos.

Su correspondencia con nuestro contrato:

Contrato del TDA collections.deque Coste
encolar_final(x) d.append(x) O(1)
encolar_frente(x) d.appendleft(x) O(1)
desencolar_final() d.pop() O(1)
desencolar_frente() d.popleft() O(1)
frente() / final() d[0] / d[-1] O(1)
tamano() len(d) O(1)
— (extra) d.extend(iterable), d.extendleft(iterable) O(k)
— (extra) d.rotate(n) (rota n posiciones) O(min(n, len))
— (extra) maxlen (longitud máxima) — 
from collections import deque

d = deque(["B", "C"])       # se puede crear desde cualquier iterable
d.append("D")               # por el final:  B, C, D
d.appendleft("A")           # por el frente: A, B, C, D
print(d[0], d[-1])          # A D  (consultar extremos: O(1))
print(d.popleft())          # A    (FIFO si combinas append + popleft)
print(d.pop())              # D    (LIFO si combinas append + pop)
print(list(d))              # ['B', 'C']

Detalles que conviene conocer:

  • extendleft inserta los elementos uno a uno por la izquierda, así que el iterable queda invertido en el deque: deque([3]); d.extendleft([2, 1]) produce 1, 2, 3. Es sorpresa habitual.
  • rotate(1) mueve el último elemento al frente (y rotate(-1) al revés): es el "giro" de la ListaCircular del módulo 2, gratis.
  • Un deque vacío lanza IndexError en pop()/popleft(): la misma política EAFP que venimos usando en nuestras clases desde el módulo 3.

El parámetro maxlen

La joya para nuestros propósitos: un deque creado con deque(maxlen=k) nunca supera k elementos. Si está lleno y haces append, descarta automáticamente el elemento del extremo opuesto (el frente); con appendleft, descarta el del final. Todo en O(1):

from collections import deque

ultimos = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    ultimos.append(x)
    print(list(ultimos))
# [1]
# [1, 2]
# [1, 2, 3]
# [2, 3, 4]   ← el 1 se descartó solo, sin pop(0), sin O(n)
# [3, 4, 5]

Compara con la lección anterior de colas circulares: maxlen te da la política "descartar lo más antiguo" del RegistroEventos, pero sin escribir la clase. ¿Cuál usar? deque(maxlen=k) en Python del día a día; la ColaCircular artesanal cuando necesites control total (o cuando programes en un lenguaje sin deque de serie) — y, sobre todo, para entender qué hace la magia por dentro.

Cuándo NO usar un deque

Ninguna estructura es gratis en todas las operaciones; el deque paga su O(1) en los extremos con un interior caro:

Operación list deque
x[i] en los extremos O(1) O(1)
x[i] por el medio O(1) O(n) — hay que saltar de bloque en bloque
Rebanadas x[a:b] O(k) No soportadas directamente
insert/del por el medio O(n) O(n) (y contra el espíritu del TDA)
sort() O(n log n) No existe (hay que pasar por list)
append / pop final O(1) am. O(1)
insert(0) / pop(0) O(n) O(1) (appendleft/popleft)

Regla práctica: si tu patrón de acceso es "por los extremos", deque; si es "por índice a cualquier posición" o necesitas ordenar y rebanar, list. Un deque usado como array de acceso aleatorio (bucles con d[i] sobre el medio) esconde un O(n²) tan traicionero como el pop(0) en bucle que denunciamos en el módulo 1 — la trampa simétrica.

La promesa cumplida: HistorialConLimite con maxlen

Recordemos el problema del módulo 3: guardar las últimas k acciones del usuario para deshacer, descartando las más antiguas al superar el límite. Nuestra versión sobre list apilaba con append (bien) pero descartaba con pop(0) (O(n), "tolerable" para k pequeño). La reescritura con deque es casi anticlimática de tan corta:

from collections import deque

class HistorialConLimite:
    """Últimas k acciones del usuario. Versión deque: todo O(1).

    Mismo contrato que la versión del módulo 3; solo cambia el motor.
    """

    def __init__(self, limite):
        self._acciones = deque(maxlen=limite)

    def registrar(self, accion):
        self._acciones.append(accion)     # si está lleno, maxlen descarta
                                          # el más antiguo por el frente: O(1)

    def deshacer(self):
        if self.esta_vacia():
            raise IndexError("no hay acciones que deshacer")
        return self._acciones.pop()       # LIFO por el final: O(1)

    def esta_vacia(self):
        return len(self._acciones) == 0

    def tamano(self):
        return len(self._acciones)

Fíjate en la anatomía: registrar/deshacer trabajan por el final (comportamiento de pila, como exige "deshacer"), mientras maxlen descarta por el frente (comportamiento de cola). Dos extremos activos a la vez: por eso ni la pila ni la cola simples bastaban, y por eso el deque es la estructura de los historiales con límite. El contrato público no ha cambiado desde el módulo 3 — código cliente intacto, coste mejorado: la victoria perfecta del TDA.

Implementación conceptual sobre ListaDoblementeEnlazada

¿Y si tuviéramos que implementarlo nosotros? La sorpresa es que ya casi lo hicimos. La ListaDoblementeEnlazada del módulo 2 mantiene cabeza, cola y nodos NodoDoble con anterior y siguiente; por eso puede insertar y eliminar por ambos extremos en O(1) (para eliminar por la cola, el enlace anterior nos da el penúltimo sin recorrer — justo lo que a la lista simple le faltaba en 04-02). Un deque es, conceptualmente, una ListaDoblementeEnlazada con el contrato restringido a los extremos:

class ColaDoble:
    """Deque didáctico: envuelve la ListaDoblementeEnlazada del módulo 2
    y expone SOLO las operaciones de extremo."""

    def __init__(self):
        self._elementos = ListaDoblementeEnlazada()

    def encolar_frente(self, x):
        self._elementos.insertar_al_principio(x)   # O(1): reajusta cabeza

    def encolar_final(self, x):
        self._elementos.insertar_al_final(x)       # O(1): reajusta cola

    def desencolar_frente(self):
        if self.esta_vacia():
            raise IndexError("desencolar sobre un deque vacío")
        return self._elementos.eliminar_del_principio()   # O(1)

    def desencolar_final(self):
        if self.esta_vacia():
            raise IndexError("desencolar sobre un deque vacío")
        return self._elementos.eliminar_del_final()       # O(1) gracias a 'anterior'

    def frente(self):
        if self.esta_vacia():
            raise IndexError("frente sobre un deque vacío")
        return self._elementos.cabeza.dato

    def final(self):
        if self.esta_vacia():
            raise IndexError("final sobre un deque vacío")
        return self._elementos.cola.dato

    def esta_vacia(self):
        return self._elementos.tamano == 0

    def tamano(self):
        return self._elementos.tamano

No hay algoritmos nuevos: solo una muralla de contrato alrededor de una estructura que ya sabía hacerlo todo. Es la misma jugada que Cola sobre ListaEnlazada (04-02) y Pila sobre list (módulo 3). La diferencia entre esta clase y collections.deque es de ingeniería, no de concepto: los bloques de 64 elementos ahorran memoria y aceleran constantes, pero el Big O es idéntico.

TaskFlow: ventana deslizante de tareas completadas

Estrenemos el deque en TaskFlow con un patrón profesional de primera: la ventana deslizante (sliding window). El equipo quiere ver en el panel la media móvil de tareas completadas por día durante los últimos 7 días: cada día entra el dato nuevo y "cae" el de hace 8 días. Es exactamente deque(maxlen=7) más una suma mantenida:

from collections import deque

class VentanaProductividad:
    """Media móvil de tareas completadas/día sobre los últimos k días."""

    def __init__(self, dias=7):
        self._ventana = deque(maxlen=dias)
        self._suma = 0                        # suma mantenida: media en O(1)

    def cerrar_dia(self, completadas):
        if len(self._ventana) == self._ventana.maxlen:
            self._suma -= self._ventana[0]    # el día que va a caer (frente: O(1))
        self._ventana.append(completadas)     # entra el día nuevo (maxlen descarta)
        self._suma += completadas

    def media_movil(self):
        if not self._ventana:
            return 0.0
        return self._suma / len(self._ventana)


# --- Uso: dos semanas de trabajo del equipo ---
panel = VentanaProductividad(dias=7)
for dia, completadas in enumerate([3, 5, 2, 4, 6, 1, 0, 7, 8, 6, 5, 9, 4, 3], 1):
    panel.cerrar_dia(completadas)
    print(f"día {dia:2}: completadas={completadas}  media 7 días={panel.media_movil():.2f}")

Los detalles finos, que son los que convierten esto en O(1) por día:

  • La suma mantenida: recalcular sum(self._ventana) en cada consulta sería O(k). En su lugar, al deslizar la ventana restamos el valor que sale y sumamos el que entra: la media queda disponible en O(1). Este patrón "actualiza, no recalcules" es pariente directo de la PilaConMinimo del módulo 3, que mantenía el mínimo en lugar de buscarlo.
  • Leer self._ventana[0] antes del append: con maxlen alcanzado, el append descarta el frente silenciosamente; si no lo hubiéramos restado antes, la suma quedaría corrupta. El acceso [0] es extremo → O(1), dentro de las reglas del deque.
  • Durante los primeros días (ventana aún no llena) la media se calcula sobre los días disponibles: len(self._ventana) lo maneja solo.

Este mismo esqueleto de ventana deslizante resuelve medias de carga de servidores, sensores, cotizaciones... y una variante con truco (el máximo en ventana) te espera en los ejercicios de 04-06.

Bonus clásico: palíndromos

El ejercicio canónico de deques: ¿es una palabra un palíndromo (se lee igual del derecho y del revés)? Con un deque, la idea es física: compara los dos extremos y ve cerrando la pinza:

from collections import deque

def es_palindromo(texto):
    letras = deque(c.lower() for c in texto if c.isalnum())  # limpia espacios/signos
    while len(letras) > 1:
        if letras.popleft() != letras.pop():   # frente vs final: ambos O(1)
            return False
    return True                                # 0 o 1 letras restantes: simétrico

print(es_palindromo("Dábale arroz a la zorra el abad"))   # True
print(es_palindromo("TaskFlow"))                          # False

Cada vuelta consume una letra de cada extremo: n/2 comparaciones, todas O(1) → O(n) total. Hacerlo con una list y pop(0) sería O(n²); el deque es la diferencia entre el algoritmo y su caricatura.

Errores Comunes y Consejos

  • Indexar el interior de un deque en un bucle: for i in range(len(d)): usar(d[i]) es O(n²) porque cada d[i] central es O(n). Itera con for x in d (O(n) total) o convierte a list si de verdad necesitas índices.
  • Olvidar que maxlen descarta en silencio: no hay excepción ni aviso cuando un append expulsa al más antiguo. Si tu lógica depende del elemento que cae (como la suma de VentanaProductividad), captúralo antes del append.
  • extendleft invierte: d.extendleft([1, 2, 3]) deja 3, 2, 1, ... al frente. Si quieres conservar el orden, d.extendleft(reversed(secuencia)).
  • Usar deque cuando necesitas ordenar o rebanar: ni sort() ni d[2:5] existen. Si tu algoritmo los pide a menudo, la estructura correcta era una list (o mantener orden con inserción ordenada, módulo 2).
  • Consejo: cuando dudes entre list y deque, escribe primero las operaciones que hará tu código (no las que "quizá" hará) y márcalas en la tabla de costes de esta lección. La estructura correcta suele quedar señalada sola — es el método que venimos aplicando desde la tabla de costes del módulo 1.

Ejercicios

Ejercicio 1: traza de las cuatro puertas

Partiendo de un deque vacío, traza el contenido (de frente a final) tras cada operación: encolar_final(2), encolar_frente(1), encolar_final(3), desencolar_frente(), encolar_frente(0), desencolar_final(), desencolar_final(). Indica también qué devuelve cada desencolar_*. ¿Qué estructura clásica habrías obtenido si todas las operaciones hubieran sido encolar_final/desencolar_frente?

Ejercicio 2: últimos k errores, con lectura no destructiva

Con deque(maxlen=k), escribe la clase UltimosErrores para TaskFlow: anotar(mensaje) guarda un error (descartando el más antiguo si se supera k) y listado() devuelve una list con los errores del más reciente al más antiguo, sin modificar el deque. Todo anotar debe ser O(1).

Ejercicio 3: media móvil robusta a días sin datos

Amplía VentanaProductividad con un método cerrar_dia_sin_datos() para días festivos: la ventana debe deslizarse (el día cuenta, y expulsa al más antiguo si toca) pero el día no aporta tareas y no debe contar en el denominador de la media. Pista: encola tuplas (valor, cuenta_en_media) o el valor None, y mantén además de _suma un contador _dias_validos.

Soluciones

Solución 1:

Operación Deque (frente → final) Devuelve
encolar_final(2) 2 —
encolar_frente(1) 1, 2 —
encolar_final(3) 1, 2, 3 —
desencolar_frente() 2, 3 1
encolar_frente(0) 0, 2, 3 —
desencolar_final() 0, 2 3
desencolar_final() 0 2

Solo con encolar_final + desencolar_frente habríamos usado el deque como cola FIFO (el par de operaciones de la tabla de generalización).

Solución 2:

from collections import deque

class UltimosErrores:
    def __init__(self, k=10):
        self._errores = deque(maxlen=k)

    def anotar(self, mensaje):
        self._errores.append(mensaje)          # O(1); maxlen descarta el viejo

    def listado(self):
        return list(reversed(self._errores))   # copia, más reciente primero

reversed(deque) itera del final al frente en O(n) sin tocar el deque, y list(...) materializa la copia: el cliente puede hacer lo que quiera con ella sin corromper el historial. Anotar sigue siendo O(1) porque el coste O(n) solo se paga al consultar.

Solución 3:

class VentanaProductividad(VentanaProductividad):   # ampliamos la clase
    def __init__(self, dias=7):
        super().__init__(dias)
        self._dias_validos = 0

    def _deslizar(self, entrante):
        if len(self._ventana) == self._ventana.maxlen:
            saliente = self._ventana[0]
            if saliente is not None:          # solo restar si contaba
                self._suma -= saliente
                self._dias_validos -= 1
        self._ventana.append(entrante)

    def cerrar_dia(self, completadas):
        self._deslizar(completadas)
        self._suma += completadas
        self._dias_validos += 1

    def cerrar_dia_sin_datos(self):
        self._deslizar(None)                  # ocupa hueco, no aporta datos

    def media_movil(self):
        if self._dias_validos == 0:
            return 0.0
        return self._suma / self._dias_validos

La idea: None es un "hueco con derecho a casilla": desliza la ventana (y puede expulsar días antiguos) pero ni suma ni cuenta. Al salir de la ventana, un None tampoco resta nada. Error común aquí: usar 0 en lugar de None — la suma saldría bien, ¡pero el denominador contaría el festivo y hundiría la media injustamente!

Conclusión

El deque completa nuestra familia de colas: cuatro operaciones de extremo, todas O(1), de las que pila y cola son casos particulares. Hemos exprimido collections.deque —append/appendleft/pop/popleft, rotate, y el decisivo maxlen que descarta lo antiguo gratis—, aprendido su límite real (el interior es O(n): no es un array de acceso aleatorio), cumplido la promesa del módulo 3 reescribiendo HistorialConLimite en cuatro líneas O(1), y comprobado que la implementación conceptual era la ListaDoblementeEnlazada del módulo 2 con el contrato restringido. De propina, TaskFlow estrena panel de productividad con una ventana deslizante de media móvil en O(1) por día. Con esto, la teoría del módulo está completa: cola FIFO, cola circular, cola de prioridad y deque. En la próxima lección no hay conceptos nuevos: hay seis ejercicios progresivos donde estas cuatro estructuras —y las pilas del módulo 3— trabajan juntas sobre TaskFlow. Es el momento de consolidar; nos vemos en el gimnasio.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados