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

Ejercicios con Colas

Siguiente ►
►

Toca consolidar. En este módulo has aprendido cuatro estructuras (cola FIFO, cola circular, cola de prioridad y deque) y en esta lección no hay teoría nueva: hay seis ejercicios progresivos que las ponen a trabajar juntas —y con las pilas del módulo 3— sobre problemas reales de TaskFlow. Te recomendamos el método de siempre: lee el enunciado, decide primero qué estructura encaja y por qué (la elección es la mitad del ejercicio), escribe tu solución, pruébala con los casos dados, y solo entonces compárala con la solución comentada. Las soluciones reutilizan las clases del módulo: Cola (04-02), BandejaUrgencias (04-04) y collections.deque (04-05).

Contenido

  1. Ejercicio 1: notificaciones con reintentos
  2. Ejercicio 2: planificador round-robin con quantum
  3. Ejercicio 3: bandeja de urgencias con extracciones intercaladas
  4. Ejercicio 4: máximo de tareas completadas en ventana deslizante
  5. Ejercicio 5: generar los binarios de 1 a n con una cola
  6. Ejercicio 6: invertir los primeros k elementos de una cola
  7. Soluciones comentadas

Ejercicios

Ejercicio 1: notificaciones con reintentos

El envío de notificaciones de TaskFlow a veces falla (el servidor de correo no responde). Amplía la idea de la ColaNotificaciones de 04-02: escribe una función procesar_con_reintentos(notificaciones, enviar, max_intentos=3) que reciba una lista de notificaciones (dicts con al menos mensaje) y una función enviar(notif) que devuelve True (éxito) o False (fallo). Reglas:

  • Las notificaciones se procesan en orden FIFO.
  • Si un envío falla, la notificación vuelve a encolarse al final (no se reintenta en caliente: así un servidor caído no bloquea a las demás).
  • Cada notificación se intenta como máximo max_intentos veces; superado el límite, va a una lista de descartadas.
  • Devuelve la tupla (enviadas, descartadas) con las notificaciones en el orden en que se resolvieron.

Pruébalo con un enviar que falle siempre para los mensajes que contengan "@caido" y acierte para el resto.

Ejercicio 2: planificador round-robin con quantum

En el módulo 2, el RepartidorTareas giraba sobre una ListaCircular para repartir turnos. Los sistemas operativos hacen algo más fino: round-robin con quantum. Escribe planificar_round_robin(tareas, quantum) donde cada tarea es un dict con id, titulo y restante (unidades de trabajo pendientes). Reglas:

  • Las tareas esperan en una cola FIFO.
  • Se desencola la primera, se trabaja sobre ella como máximo quantum unidades, y:
    • si le queda trabajo, vuelve al final de la cola;
    • si termina, se anota en la lista de terminadas.
  • Devuelve la lista de id en orden de terminación y el registro de turnos como lista de tuplas (id, unidades_trabajadas).

Con tareas = [{id: 1, restante: 5}, {id: 2, restante: 2}, {id: 3, restante: 8}] y quantum = 3, el orden de terminación debe ser [2, 1, 3].

Ejercicio 3: bandeja de urgencias con extracciones intercaladas

Usando heapq con el idiom (prioridad, contador, tarea) de 04-04 (puedes usar la clase BandejaUrgencias o reescribirlo a mano), simula esta jornada de soporte y predice antes de ejecutar el orden de atención:

llega  ("Backup roto",        prioridad 2)
llega  ("Web lenta",          prioridad 3)
ATIENDE una tarea
llega  ("Servidor caído",     prioridad 1)
llega  ("Login falla",        prioridad 1)
ATIENDE una tarea
ATIENDE una tarea
llega  ("Backup secundario",  prioridad 2)
ATIENDE todas las restantes

Escribe el código que reproduce la simulación e imprime el orden de atención. Comprueba tu predicción, prestando atención al empate de prioridad 1.

Ejercicio 4: máximo de tareas completadas en ventana deslizante

En 04-05 calculamos la media móvil con una suma mantenida. El máximo en ventana es más difícil: cuando el día que sale era justamente el máximo, ¿cuál es el nuevo? Recalcularlo cada día es O(k). Existe una técnica O(1) amortizado por día: el deque monótono decreciente (guarda candidatos a máximo de mayor a menor; parientes del min-stack del módulo 3).

Escribe maximos_en_ventana(completadas_por_dia, k) que devuelva, para cada día desde el día k, el máximo de tareas completadas en los últimos k días. Reglas del deque monótono (guarda índices de días):

  1. Antes de añadir el día i, elimina por el final todos los índices cuyo valor sea <= que el del día i (nunca podrán ser máximos habiendo llegado i, más reciente y mayor).
  2. Añade i por el final.
  3. Elimina por el frente el índice i - k si sigue ahí (ha caducado: ya no está en la ventana).
  4. El máximo de la ventana es el valor del índice del frente.

Con completadas = [3, 5, 2, 4, 6, 1, 0, 7] y k = 3, el resultado es [5, 5, 6, 6, 6, 7].

Ejercicio 5: generar los binarios de 1 a n con una cola

Un clásico sorprendente: genera las representaciones binarias de los números 1 a n sin convertir números (nada de bin()), solo con una cola de cadenas. La semilla es "1"; en cada paso se desencola una cadena b, se emite como resultado, y se encolan b + "0" y b + "1". Escribe binarios_hasta(n) y explica por qué la cola FIFO produce exactamente el orden 1, 10, 11, 100, 101... ¿Qué saldría si usaras una pila? (Anticipo: este patrón "procesar y encolar los descendientes" es exactamente el recorrido por niveles/BFS que verás en árboles y grafos, módulos 6 y 7.)

Ejercicio 6: invertir los primeros k elementos de una cola

Integración con el módulo 3: escribe invertir_primeros(cola, k) que invierta el orden de los primeros k elementos de una Cola, dejando el resto en su orden original, usando solo el contrato de la cola, una Pila auxiliar y O(1) variables extra. Con la cola 1, 2, 3, 4, 5 (frente a la izquierda) y k = 3, debe quedar 3, 2, 1, 4, 5. Pista: la pila invierte; para recolocar el resto sin tocar su orden te servirá la rotación completa que usamos en actividad_reciente (04-03). Trata los casos de error: k mayor que el tamaño o negativo.

Soluciones

Solución 1: notificaciones con reintentos

from collections import deque

def procesar_con_reintentos(notificaciones, enviar, max_intentos=3):
    cola = deque()                          # deque como cola FIFO (04-05)
    for notif in notificaciones:
        cola.append({**notif, "intentos": 0})   # copia + contador de intentos

    enviadas, descartadas = [], []
    while cola:
        notif = cola.popleft()              # FIFO: el que más espera
        notif["intentos"] += 1
        if enviar(notif):
            enviadas.append(notif)
        elif notif["intentos"] < max_intentos:
            cola.append(notif)              # al FINAL: no bloquea a los demás
        else:
            descartadas.append(notif)       # agotó sus oportunidades
    return enviadas, descartadas


# --- Prueba ---
def enviar_simulado(notif):
    return "@caido" not in notif["mensaje"]

notifs = [
    {"mensaje": "Tarea 1 asignada a ana"},
    {"mensaje": "Aviso a servidor @caido"},
    {"mensaje": "Tarea 2 completada"},
]
ok, ko = procesar_con_reintentos(notifs, enviar_simulado)
print([n["mensaje"] for n in ok])   # las dos buenas, en orden de llegada
print([n["intentos"] for n in ko])  # [3]: la fallida agotó sus 3 intentos

Comentario: los tres puntos con enjundia son (1) el contador intentos viaja dentro de la notificación (con una copia {**notif, ...} para no mutar la entrada del llamante); (2) el reencolado al final implementa la política "no bloquear": entre reintento y reintento se atiende al resto de la cola, dando tiempo a que el servidor se recupere; (3) el bucle termina siempre, porque cada notificación pasa por popleft a lo sumo max_intentos veces — coste total O(n · max_intentos).

Solución 2: round-robin con quantum

from collections import deque

def planificar_round_robin(tareas, quantum):
    cola = deque(dict(t) for t in tareas)   # copias: no mutamos la entrada
    terminadas, turnos = [], []

    while cola:
        tarea = cola.popleft()
        trabajado = min(quantum, tarea["restante"])   # nunca más del pendiente
        tarea["restante"] -= trabajado
        turnos.append((tarea["id"], trabajado))
        if tarea["restante"] > 0:
            cola.append(tarea)              # su turno acabó: al final de la fila
        else:
            terminadas.append(tarea["id"])
    return terminadas, turnos


tareas = [
    {"id": 1, "titulo": "Importar datos", "restante": 5},
    {"id": 2, "titulo": "Enviar resumen", "restante": 2},
    {"id": 3, "titulo": "Generar informe", "restante": 8},
]
fin, turnos = planificar_round_robin(tareas, quantum=3)
print(fin)     # [2, 1, 3]
print(turnos)  # [(1, 3), (2, 2), (3, 3), (1, 2), (3, 3), (3, 2)]

Comentario: sigamos la traza para verificar el [2, 1, 3]. Turno de 1 (trabaja 3, le quedan 2 → reencola), turno de 2 (trabaja 2, termina), turno de 3 (trabaja 3, quedan 5 → reencola), turno de 1 (trabaja 2, termina), turnos de 3 (3 y 2, termina). La gracia del round-robin es la justicia: la tarea corta (id 2) no espera a que termine la larga (id 3), y ninguna tarea monopoliza el procesador más de quantum seguidas. Es el RepartidorTareas del módulo 2 con contrato de cola en vez de lista circular: reencolar al final es el giro del anillo. El min(quantum, restante) evita "trabajar de más" y registrar turnos negativos — caso límite fácil de olvidar.

Solución 3: urgencias intercaladas

import heapq
from itertools import count

monticulo, c, atencion = [], count(), []

def llega(titulo, prioridad):
    heapq.heappush(monticulo, (prioridad, next(c),
                   {"titulo": titulo, "prioridad": prioridad}))

def atiende():
    tarea = heapq.heappop(monticulo)[2]
    atencion.append(tarea["titulo"])

llega("Backup roto", 2)
llega("Web lenta", 3)
atiende()                       # 1ª
llega("Servidor caído", 1)
llega("Login falla", 1)
atiende(); atiende()            # 2ª y 3ª
llega("Backup secundario", 2)
while monticulo:
    atiende()                   # el resto

print(atencion)
# ['Backup roto', 'Servidor caído', 'Login falla', 'Backup secundario', 'Web lenta']

Comentario, atención por atención: (1) en la primera solo hay prioridades 2 y 3 → sale Backup roto; las urgencias de prioridad 1 aún no habían llegado — una cola de prioridad ordena lo presente, no adivina el futuro. (2) y (3): ya con las dos de prioridad 1 dentro, salen ambas, y el empate lo resuelve el contador: Servidor caído llegó antes que Login falla (estabilidad). (4) Backup secundario (prioridad 2) adelanta a Web lenta (prioridad 3) aunque llegó muchísimo después: en una cola de prioridad la antigüedad solo desempata, nunca manda. Si tu predicción falló, casi seguro fue en la primera atención o en el orden del empate: son los dos puntos donde la intuición FIFO traiciona.

Solución 4: máximo en ventana con deque monótono

from collections import deque

def maximos_en_ventana(completadas_por_dia, k):
    candidatos = deque()        # índices de días, con valores DECRECIENTES
    maximos = []

    for i, valor in enumerate(completadas_por_dia):
        # (1) Expulsar por el final los candidatos que 'valor' deja obsoletos:
        #     son más antiguos que i Y no mayores que él → nunca serán máximo.
        while candidatos and completadas_por_dia[candidatos[-1]] <= valor:
            candidatos.pop()
        # (2) El día i entra como candidato por el final.
        candidatos.append(i)
        # (3) Caducar por el frente el día que sale de la ventana.
        if candidatos[0] <= i - k:
            candidatos.popleft()
        # (4) Con la ventana completa, el frente es el máximo.
        if i >= k - 1:
            maximos.append(completadas_por_dia[candidatos[0]])
    return maximos


print(maximos_en_ventana([3, 5, 2, 4, 6, 1, 0, 7], k=3))
# [5, 5, 6, 6, 6, 7]

Comentario: el invariante es que candidatos guarda índices cuyos valores van de mayor (frente) a menor (final), todos dentro de la ventana. El paso (1) lo mantiene: si el día nuevo iguala o supera al último candidato, ese candidato ya nunca podrá ser máximo (el nuevo es igual de grande y caducará más tarde), así que se elimina — es la misma lógica de "descartar dominados" de la PilaConMinimo del módulo 3, ahora por los dos extremos. El paso (3) usa el frente como fecha de caducidad. ¿Coste? Cada índice entra una vez y sale a lo sumo una vez (por final o por frente): O(n) total, O(1) amortizado por día — el concepto de 04-02 reaparece. La solución ingenua con max(ventana) diaria sería O(n·k); con k = 30 días y años de historial, la diferencia se nota.

Solución 5: binarios con una cola

from collections import deque

def binarios_hasta(n):
    resultado = []
    cola = deque(["1"])                 # semilla
    for _ in range(n):
        b = cola.popleft()              # el más antiguo = el más corto pendiente
        resultado.append(b)
        cola.append(b + "0")            # sus dos "descendientes"
        cola.append(b + "1")
    return resultado

print(binarios_hasta(10))
# ['1', '10', '11', '100', '101', '110', '111', '1000', '1001', '1010']

Comentario: ¿por qué sale el orden numérico correcto? Porque la cola FIFO procesa las cadenas por longitud creciente (todas las de 1 bit, luego todas las de 2 bits...), y dentro de cada longitud, en el orden en que fueron generadas, que es el orden numérico (de "10" se generan "100" y "101" antes de que "11" genere "110" y "111"). Es un recorrido por niveles del árbol binario implícito de las cadenas — literalmente el BFS que formalizaremos en los módulos 6 y 7; este ejercicio es tu primer BFS sin saberlo. Con una pila (LIFO) el recorrido sería en profundidad: 1, 11, 111, 1111... — se hundiría por la rama de los unos y, con generación infinita, no volvería jamás; acotado a n elementos produciría un orden completamente distinto.

Solución 6: invertir los primeros k con una pila

def invertir_primeros(cola, k):
    if k < 0 or k > cola.tamano():
        raise ValueError("k fuera de rango")
    if k <= 1:
        return                          # nada que invertir

    pila = Pila()                       # la Pila del módulo 3

    # Fase 1: los k primeros pasan a la pila (quedan invertidos).
    for _ in range(k):
        pila.apilar(cola.desencolar())

    # Fase 2: la pila vuelve a la cola POR EL FINAL, ya invertida.
    while not pila.esta_vacia():
        cola.encolar(pila.desapilar())

    # Fase 3: los n-k restantes están ahora DELANTE del bloque invertido;
    # una rotación completa de n-k elementos los manda detrás (04-03).
    for _ in range(cola.tamano() - k):
        cola.encolar(cola.desencolar())


# --- Prueba ---
cola = Cola()
for x in [1, 2, 3, 4, 5]:
    cola.encolar(x)
invertir_primeros(cola, 3)
salida = [cola.desencolar() for _ in range(cola.tamano())]
print(salida)                           # [3, 2, 1, 4, 5]

Comentario, siguiendo el ejemplo 1..5 con k = 3: tras la fase 1, la cola queda 4, 5 y la pila [1, 2, 3] (3 en la cima). La fase 2 desapila 3, 2, 1 y los encola: la cola queda 4, 5, 3, 2, 1 — el bloque está invertido, pero en el sitio equivocado. La fase 3 rota los n - k = 2 elementos del frente hacia el final: 5, 3, 2, 1, 4 → 3, 2, 1, 4, 5. Listo. Cada elemento se mueve un número constante de veces → O(n). El ejercicio destila el módulo entero: la pila como inversora (módulo 3), la cola como conservadora del orden (este módulo), y la rotación como forma de recolocar sin salirse del contrato. Errores típicos: olvidar la fase 3 (deja el bloque invertido al final), o hacer la fase 3 con k rotaciones en vez de n - k.

Errores Comunes y Consejos

  • Reencolar sin límite (ejercicios 1 y 2): todo bucle while cola: que reencola debe tener una garantía de progreso — un contador de intentos, un restante que decrece. Sin ella, un elemento "inmortal" convierte el programa en un bucle infinito. Verifica siempre: ¿qué magnitud decrece estrictamente en cada vuelta?
  • Mutar los dicts del llamante: las soluciones 1 y 2 copian ({**notif, ...}, dict(t)) antes de añadir campos o restar trabajo. Devolver datos modificados que el llamante no esperaba es fuente clásica de errores difíciles de rastrear.
  • En el deque monótono, comparar con < en vez de <=: con <, los empates se acumulan como candidatos redundantes; funciona, pero el deque crece más de lo necesario. Con <= el invariante queda estricto. Lo grave sería expulsar por el frente por valor en lugar de por índice caducado: mezclar los dos criterios rompe el algoritmo.
  • Elegir la estructura por inercia: antes de programar, di en voz alta qué necesita el problema: ¿orden de llegada (cola)? ¿el más urgente (prioridad)? ¿los dos extremos (deque)? ¿invertir (pila)? Los seis ejercicios se resuelven mal con la estructura equivocada y casi solos con la correcta.
  • Consejo final del módulo: guarda tus soluciones. El planificador (ej. 2) y la bandeja (ej. 3) reaparecerán en los proyectos del módulo 8, y el patrón del ejercicio 5 es el corazón del BFS del módulo 7.

Conclusión

Fin del módulo 4. Has aplicado la cola FIFO a reintentos y planificación round-robin (cerrando el círculo con el RepartidorTareas del módulo 2), la cola de prioridad con heapq a una jornada de soporte con empates estables, el deque a la técnica del deque monótono para máximos en ventana, y has combinado pila y cola para invertir por bloques — además de descubrir, con los números binarios, que "encolar los descendientes de lo que proceso" genera recorridos por niveles: la semilla del BFS que germinará en el módulo 7. Las tres estructuras de acceso restringido (pila, cola, deque) ya son tuyas, contrato y costes incluidos. Pero fíjate en algo que hemos hecho todo el módulo sin cuestionarlo: cada tarea de TaskFlow es un dict, y dentro de él saltamos de tarea["id"] a tarea["prioridad"] dando por hecho que esa consulta es instantánea. ¿Por qué un dict encuentra una clave entre miles en tiempo constante, cuando buscar en una lista es O(n)? La respuesta —funciones hash, colisiones y una de las ideas más influyentes de la informática— es el programa del módulo 5: tablas hash y diccionarios. Nos vemos allí.

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