El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia

HOME

En la lección anterior definimos el contrato del TDA cola; ahora toca cumplirlo. Veremos las tres operaciones fundamentales —encolar, desencolar y frente— paso a paso, con trazas del estado interno, y nos enfrentaremos al problema central de la lección: la implementación "obvia" sobre una list de Python rompe la promesa de coste O(1) por culpa del pop(0) que ya desenmascaramos en el módulo 1. La solución elegante la tenemos desde el módulo 2: la ListaEnlazada, que inserta y elimina en O(1) justo por los extremos que la cola necesita. Cerraremos con una construcción sorprendente —una cola hecha con dos pilas— y con la primera pieza de TaskFlow de este módulo: la ColaNotificaciones.

Contenido

Las tres operaciones, paso a paso
Primer intento: cola sobre list (y por qué falla)
La implementación correcta: Cola sobre ListaEnlazada
Curiosidad formativa: ColaConDosPilas
Tabla de costes comparada
TaskFlow: la clase ColaNotificaciones

Las tres operaciones, paso a paso

Antes de escribir código, tracemos a mano una secuencia de operaciones. Representamos la cola con el frente a la izquierda y el final a la derecha:

Paso	Operación	Estado de la cola (frente → final)	Devuelve
1	`encolar("N1")`	`N1`	—
2	`encolar("N2")`	`N1, N2`	—
3	`encolar("N3")`	`N1, N2, N3`	—
4	`frente()`	`N1, N2, N3` (sin cambios)	`"N1"`
5	`desencolar()`	`N2, N3`	`"N1"`
6	`desencolar()`	`N3`	`"N2"`
7	`encolar("N4")`	`N3, N4`	—
8	`desencolar()`	`N4`	`"N3"`

Tres invariantes que se cumplen en toda la traza y que debe garantizar cualquier implementación:

desencolar devuelve los elementos exactamente en el orden en que se encolaron (N1, N2, N3...), aunque entre medias haya nuevas inserciones (paso 7).
frente es una consulta pura: el paso 4 no altera el estado.
Los dos extremos trabajan a la vez: el final crece, el frente mengua. Este es el detalle que complicará la implementación.

sequenceDiagram
    participant P as Productor
    participant C as Cola
    participant W as Consumidor
    P->>C: encolar(N1)
    P->>C: encolar(N2)
    W->>C: desencolar()
    C-->>W: N1
    P->>C: encolar(N3)
    W->>C: desencolar()
    C-->>W: N2
    Note over C: El orden de salida = orden de llegada,<br/>aunque productor y consumidor se intercalen

Primer intento: cola sobre `list` (y por qué falla)

La tentación natural es calcar lo que hicimos con la Pila del módulo 3: envolver una list. Encolamos con append (por el final) y desencolamos con pop(0) (por el frente):

class ColaLenta:
    """Cola sobre list. Funcionalmente correcta, pero con una trampa de coste."""

    def __init__(self):
        self._elementos = []

    def encolar(self, elemento):
        self._elementos.append(elemento)      # O(1) amortizado: bien

    def desencolar(self):
        if self.esta_vacia():
            raise IndexError("desencolar sobre una cola vacía")
        return self._elementos.pop(0)         # O(n): AQUÍ está el problema

    def frente(self):
        if self.esta_vacia():
            raise IndexError("frente sobre una cola vacía")
        return self._elementos[0]

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

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

Esta clase cumple el contrato funcional (pasa cualquier prueba de orden FIFO), pero incumple la promesa de coste. En el módulo 1 demostramos con timeit que pop(0) es O(n): al quitar el primer elemento, Python desplaza en memoria todos los demás una posición a la izquierda, porque una list es un array dinámico y debe mantener sus elementos contiguos. Puedes repetir aquí el experimento del módulo 1:

import timeit

def vaciar(cola_cls, n):
    cola = cola_cls()
    for i in range(n):
        cola.encolar(i)
    while not cola.esta_vacia():
        cola.desencolar()

# Duplicar n debería duplicar el tiempo si desencolar fuera O(1)...
print(timeit.timeit(lambda: vaciar(ColaLenta, 10_000), number=1))
print(timeit.timeit(lambda: vaciar(ColaLenta, 20_000), number=1))
# ...pero se multiplica por ~4: el vaciado completo es O(n²)

¿Y al revés? Si encolamos con insert(0, ...) y desencolamos con pop(), solo movemos el problema de extremo: insert(0) también es O(n), como vimos en el módulo 1. Con un array, uno de los dos extremos siempre sale caro. La cola necesita los dos extremos baratos, así que la list a pelo no es la herramienta adecuada.

La implementación correcta: `Cola` sobre `ListaEnlazada`

Aquí es donde cobra sentido el trabajo del módulo 2. Nuestra ListaEnlazada mantiene referencias a la cabeza y a la cola (el último nodo), y por eso puede insertar por el final y eliminar por el principio en O(1): no hay que desplazar nada, solo reajustar enlaces. Recordemos la parte que necesitamos:

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


class ListaEnlazada:
    """Versión reducida de la clase del módulo 2: solo lo que la cola necesita."""

    def __init__(self):
        self.cabeza = None
        self.cola = None
        self.tamano = 0

    def insertar_al_final(self, dato):        # O(1) gracias a self.cola
        nuevo = Nodo(dato)
        if self.cola is None:                 # lista vacía
            self.cabeza = nuevo
            self.cola = nuevo
        else:
            self.cola.siguiente = nuevo       # el último apunta al nuevo
            self.cola = nuevo                 # el nuevo pasa a ser el último
        self.tamano += 1

    def eliminar_del_principio(self):         # O(1): solo se toca la cabeza
        if self.cabeza is None:
            raise IndexError("eliminar de una lista vacía")
        dato = self.cabeza.dato
        self.cabeza = self.cabeza.siguiente   # la cabeza avanza un nodo
        if self.cabeza is None:               # si era el único nodo...
            self.cola = None                  # ...la cola también queda vacía
        self.tamano -= 1
        return dato

La decisión clave de diseño es por qué extremo entra y por qué extremo sale:

Encolar por el final (insertar_al_final): O(1) porque guardamos la referencia self.cola.
Desencolar por la cabeza (eliminar_del_principio): O(1) porque basta avanzar self.cabeza.

¿Podríamos hacerlo al revés (encolar por la cabeza, desencolar por la cola)? Encolar seguiría siendo O(1), pero desencolar por la cola sería O(n): para eliminar el último nodo necesitamos el penúltimo, y en una lista enlazada simple solo se llega a él recorriendo desde la cabeza. La orientación correcta no es opcional: es la única que da O(1) en ambas operaciones.

Con la lista lista, la clase Cola es una capa fina que restringe el acceso al contrato FIFO (igual que la Pila restringía la list al contrato LIFO):

class Cola:
    """Cola FIFO con encolar y desencolar en O(1), sobre ListaEnlazada."""

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

    def encolar(self, elemento):
        self._elementos.insertar_al_final(elemento)

    def desencolar(self):
        if self.esta_vacia():
            raise IndexError("desencolar sobre una cola vacía")
        return self._elementos.eliminar_del_principio()

    def frente(self):
        if self.esta_vacia():
            raise IndexError("frente sobre una cola vacía")
        return self._elementos.cabeza.dato

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

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

Como Cola y ColaLenta comparten contrato, puedes verificar que se comportan igual con la misma técnica del probar_contrato del módulo 3: ejecutar la misma secuencia de operaciones sobre ambas y comparar resultados. Solo cambia el coste, no el comportamiento — esa es la esencia del TDA.

Curiosidad formativa: `ColaConDosPilas`

Hay una construcción clásica que parece un acertijo: implementar una cola usando solo dos pilas. Merece la pena verla porque enseña un concepto nuevo, el coste amortizado, y porque aparece con frecuencia en entrevistas técnicas.

La idea: una pila invierte el orden; dos inversiones lo restauran.

entrada: pila donde apilamos todo lo que se encola.
salida: pila de donde desapilamos. Cuando está vacía, volcamos toda entrada en salida, lo que invierte el orden y deja el elemento más antiguo en la cima.

class ColaConDosPilas:
    def __init__(self):
        self._entrada = Pila()    # la Pila del módulo 3 (apilar/desapilar/esta_vacia)
        self._salida = Pila()

    def encolar(self, elemento):
        self._entrada.apilar(elemento)            # O(1) siempre

    def desencolar(self):
        if self._salida.esta_vacia():
            # Volcado: invierte el orden de 'entrada' dentro de 'salida'
            while not self._entrada.esta_vacia():
                self._salida.apilar(self._entrada.desapilar())
        if self._salida.esta_vacia():
            raise IndexError("desencolar sobre una cola vacía")
        return self._salida.desapilar()

    def esta_vacia(self):
        return self._entrada.esta_vacia() and self._salida.esta_vacia()

    def tamano(self):
        return self._entrada.tamano() + self._salida.tamano()

Traza: encolamos A, B, C → entrada = [A, B, C] (C en la cima). Primer desencolar: volcado → salida = [C, B, A] (A en la cima) → devuelve A. Correcto: A fue el primero en entrar. Los siguientes desencolar devuelven B y C sin volcar nada, porque ya están ordenados en salida.

¿Y el coste? Un desencolar concreto puede costar O(n) (el que provoca el volcado), pero cada elemento se apila y desapila como máximo dos veces en toda su vida (una en cada pila). Repartido entre n operaciones, el coste medio por operación es O(1): se dice que es O(1) amortizado. Es la misma idea con la que el append de list es O(1) amortizado pese a los redimensionados ocasionales (módulo 1). No usaremos esta clase en TaskFlow —la versión enlazada es más simple y O(1) siempre—, pero el concepto de coste amortizado te acompañará toda la carrera.

Tabla de costes comparada

Operación	`ColaLenta` (`list`)	`Cola` (`ListaEnlazada`)	`ColaConDosPilas`
`encolar`	O(1) amortizado	O(1)	O(1)
`desencolar`	O(n)	O(1)	O(1) amortizado
`frente`	O(1)	O(1)	O(1) amortizado
`esta_vacia` / `tamano`	O(1)	O(1)	O(1)
Memoria extra por elemento	Ninguna	Un nodo (referencia extra)	Ninguna

La lista enlazada paga un pequeño sobrecoste de memoria (cada dato viaja dentro de un Nodo), a cambio de garantías de tiempo constantes. Adelanto honesto: en Python profesional, la implementación de referencia para colas es collections.deque, que ya presentamos en el módulo 2 como "lista doblemente enlazada por bloques" y que estudiaremos a fondo en la lección 04-05. Aquí construimos la nuestra porque entender por qué es O(1) vale más que usarla a ciegas.

TaskFlow: la clase `ColaNotificaciones`

Apliquemos la Cola al caso que motivó el módulo: las notificaciones pendientes de enviar. Cada notificación referencia la tarea que la provocó (nuestro dict habitual con id/titulo/prioridad/estado):

class ColaNotificaciones:
    """Gestiona el envío de notificaciones de TaskFlow por orden de llegada."""

    def __init__(self):
        self._pendientes = Cola()

    def notificar(self, tarea, mensaje):
        """El productor: la app encola al instante (O(1)) y sigue trabajando."""
        notificacion = {
            "tarea_id": tarea["id"],
            "destinatario": tarea.get("asignada_a", "sin asignar"),
            "mensaje": mensaje,
        }
        self._pendientes.encolar(notificacion)

    def pendientes(self):
        return self._pendientes.tamano()

    def procesar(self, maximo=None):
        """El consumidor: envía por orden de llegada, hasta 'maximo' envíos."""
        enviadas = 0
        while not self._pendientes.esta_vacia():
            if maximo is not None and enviadas == maximo:
                break                              # respeta el lote pedido
            notif = self._pendientes.desencolar()
            print(f"[envío] a {notif['destinatario']}: "
                  f"{notif['mensaje']} (tarea {notif['tarea_id']})")
            enviadas += 1
        return enviadas


# --- Uso ---
tarea_a = {"id": 7, "titulo": "Migrar base de datos", "prioridad": 1,
           "estado": "en curso", "asignada_a": "ana"}
tarea_b = {"id": 8, "titulo": "Redactar changelog", "prioridad": 3,
           "estado": "pendiente", "asignada_a": "luis"}

buzon = ColaNotificaciones()
buzon.notificar(tarea_a, "Se te ha asignado la tarea")
buzon.notificar(tarea_b, "Se te ha asignado la tarea")
buzon.notificar(tarea_a, "La tarea ha cambiado a 'en curso'")

print(buzon.pendientes())   # 3
buzon.procesar(maximo=2)    # envía las DOS más antiguas, en su orden
buzon.procesar()            # envía el resto

Detalles de diseño que conviene subrayar:

El parámetro maximo permite procesar por lotes: en una aplicación real, el consumidor corre periódicamente y envía unas pocas notificaciones cada vez, sin bloquear nada. La cola conserva el resto, en orden, para el siguiente lote.
Ana recibe sus dos notificaciones en el orden correcto (asignación antes que cambio de estado): esa coherencia la regala el FIFO.
La prioridad de la tarea viaja en el dict pero no se usa para ordenar: en un FIFO no debe usarse. La bandeja donde la prioridad manda llega en la lección 04-04.

Errores Comunes y Consejos

Usar list.pop(0) en producción "porque funciona": funciona hasta que la cola crece. Un vaciado completo pasa de lineal a cuadrático, y son los errores que no aparecen en las pruebas (con 10 elementos) pero tumban el sistema con 100.000. Mide con timeit ante la duda, como en el módulo 1.
Olvidar actualizar self.cola al vaciar la lista enlazada: en eliminar_del_principio, si se elimina el único nodo, self.cola debe ponerse a None. Si lo olvidas, el siguiente insertar_al_final encadenará el nuevo nodo a un nodo fantasma ya eliminado. Es el error más frecuente al implementar colas enlazadas.
Desencolar por el extremo equivocado: encolar y desencolar por la cabeza convierte tu "cola" en una pila. Escribe una prueba que encole 1, 2, 3 y compruebe que salen 1, 2, 3.
En ColaConDosPilas, volcar cuando salida no está vacía: mezclarías los órdenes y romperías el FIFO. El volcado solo procede con salida vacía; es un invariante, protégelo con la condición y, si quieres, con una aserción.
Consejo: cuando envuelvas una estructura (como Cola envuelve ListaEnlazada), expón solo el contrato. Si publicas cabeza o insertar_al_principio, algún código cliente acabará usándolos y tu cola dejará de ser una cola.

Ejercicios

Ejercicio 1: traza sobre la lista enlazada

Parte de una Cola vacía y ejecuta: encolar(10), encolar(20), desencolar(), encolar(30), desencolar(), desencolar(). Dibuja (o escribe) el estado de cabeza, cola y tamano de la ListaEnlazada interna después de cada operación. Presta especial atención al momento en que la cola queda vacía.

Ejercicio 2: `vaciar` y `recorrer` sin romper el contrato

Añade a la clase Cola dos métodos: vaciar() (deja la cola sin elementos, en O(1)) y en_espera() (devuelve una list de Python con los elementos en orden de frente a final, sin modificar la cola, en O(n)). Pista: para en_espera tendrás que recorrer los nodos internos; hazlo dentro de la clase para no exponer los nodos fuera.

Ejercicio 3: la traza de las dos pilas

Con ColaConDosPilas, ejecuta: encolar(1), encolar(2), desencolar(), encolar(3), encolar(4), desencolar(), desencolar(), desencolar(). Indica, tras cada operación, el contenido de entrada y salida (de fondo a cima) y cuándo se produce cada volcado. ¿Cuántas veces pasa el elemento 3 por una operación de apilar/desapilar en total?

Soluciones

Solución 1:

Operación	cabeza	cola	tamano
(inicial)	`None`	`None`	0
`encolar(10)`	nodo(10)	nodo(10)	1
`encolar(20)`	nodo(10)	nodo(20)	2
`desencolar()` → 10	nodo(20)	nodo(20)	1
`encolar(30)`	nodo(20)	nodo(30)	2
`desencolar()` → 20	nodo(30)	nodo(30)	1
`desencolar()` → 30	`None`	`None`	0

El punto crítico es la última fila: al eliminar el único nodo, cabeza queda a None y también cola; si no, la estructura queda corrupta.

Solución 2:

class Cola(Cola):  # ampliamos la clase anterior
    def vaciar(self):
        # Basta con sustituir la lista interna: los nodos antiguos
        # quedan sin referencias y el recolector de basura los libera.
        self._elementos = ListaEnlazada()

    def en_espera(self):
        resultado = []
        actual = self._elementos.cabeza
        while actual is not None:      # recorrido O(n) clásico del módulo 2
            resultado.append(actual.dato)
            actual = actual.siguiente
        return resultado               # copia: modificarla no toca la cola

vaciar es O(1) porque no eliminamos nodo a nodo: soltamos la lista entera. en_espera devuelve una copia, de modo que el cliente no puede alterar la cola a través de ella.

Solución 3:

Operación	`entrada` (fondo→cima)	`salida` (fondo→cima)	Devuelve
`encolar(1)`	1	—	—
`encolar(2)`	1, 2	—	—
`desencolar()`	—	2, 1 → 2	1 (volcado nº 1)
`encolar(3)`	3	2	—
`encolar(4)`	3, 4	2	—
`desencolar()`	3, 4	—	2 (sin volcado)
`desencolar()`	—	4, 3 → 4	3 (volcado nº 2)
`desencolar()`	—	—	4

Hay dos volcados (cuando salida se queda vacía y se pide desencolar). El elemento 3 participa en 4 operaciones: apilar en entrada, desapilar de entrada, apilar en salida, desapilar de salida. Ningún elemento supera ese máximo de 2 apilados + 2 desapilados: por eso el coste amortizado es O(1).

Conclusión

Ya tenemos una cola de verdad: trazamos sus operaciones, comprobamos que la list a pelo condena desencolar (o encolar) a O(n), y la implementamos correctamente sobre la ListaEnlazada del módulo 2 —encolar por la cola, desencolar por la cabeza, ambos O(1)—. De regalo, la ColaConDosPilas nos presentó el coste amortizado, y la ColaNotificaciones de TaskFlow ya procesa avisos por orden justo de llegada y por lotes. Pero nuestra cola crece sin límite, y hay contextos —buffers de red, registros de eventos— donde la memoria es fija y lo razonable es que lo nuevo acabe ocupando el sitio de lo viejo. Para eso hay que hacer que los índices "den la vuelta": es la cola circular, prima de la ListaCircular del módulo 2, y protagonista de la próxima lección.

Operaciones Básicas con Colas

Contenido

Las tres operaciones, paso a paso

Primer intento: cola sobre `list` (y por qué falla)

La implementación correcta: `Cola` sobre `ListaEnlazada`

Curiosidad formativa: `ColaConDosPilas`

Tabla de costes comparada

TaskFlow: la clase `ColaNotificaciones`

Errores Comunes y Consejos

Ejercicios

Ejercicio 1: traza sobre la lista enlazada

Ejercicio 2: `vaciar` y `recorrer` sin romper el contrato

Ejercicio 3: la traza de las dos pilas

Soluciones

Conclusión

Curso de Estructuras de Datos

Módulo 1: Introducción a las Estructuras de Datos

Módulo 2: Listas

Módulo 3: Pilas

Módulo 4: Colas

Módulo 5: Tablas Hash y Diccionarios

Módulo 6: Árboles

Módulo 7: Grafos

Módulo 8: Conclusiones y Recursos Adicionales

Operaciones Básicas con Colas

Contenido

Las tres operaciones, paso a paso

Primer intento: cola sobre list (y por qué falla)

La implementación correcta: Cola sobre ListaEnlazada

Curiosidad formativa: ColaConDosPilas

Tabla de costes comparada

TaskFlow: la clase ColaNotificaciones

Errores Comunes y Consejos

Ejercicios

Ejercicio 1: traza sobre la lista enlazada

Ejercicio 2: vaciar y recorrer sin romper el contrato

Ejercicio 3: la traza de las dos pilas

Soluciones

Conclusión

Curso de Estructuras de Datos

Módulo 1: Introducción a las Estructuras de Datos

Módulo 2: Listas

Módulo 3: Pilas

Módulo 4: Colas

Módulo 5: Tablas Hash y Diccionarios

Módulo 6: Árboles

Módulo 7: Grafos

Módulo 8: Conclusiones y Recursos Adicionales

Primer intento: cola sobre `list` (y por qué falla)

La implementación correcta: `Cola` sobre `ListaEnlazada`

Curiosidad formativa: `ColaConDosPilas`

TaskFlow: la clase `ColaNotificaciones`

Ejercicio 2: `vaciar` y `recorrer` sin romper el contrato