Al cerrar el módulo de pilas dejamos tres cabos sueltos: un HistorialConLimite que necesitaba trabajar por los dos extremos, un min-stack que podía consultar el elemento más prioritario pero no extraerlo, y una promesa: procesar las tareas de TaskFlow "por orden justo de llegada". Los tres cabos se atan en este módulo, y los tres apuntan a la misma familia de estructuras: las colas. En esta lección presentamos el TDA cola, su principio FIFO, su contrato de operaciones y los lugares (muy reales) donde las colas sostienen sistemas enteros. Todavía no implementaremos nada en detalle: primero hay que entender bien qué es una cola y para qué sirve; el cómo llega en la siguiente lección.

1. De la pila a la cola: los tres puentes pendientes
2. El principio FIFO
3. LIFO vs FIFO: dos políticas opuestas
4. El contrato del TDA cola
5. Analogías: el supermercado y la impresora
6. Colas en sistemas reales
7. La cola de notificaciones de TaskFlow
8. El mapa del módulo 4

Recordemos exactamente dónde nos quedamos al final del módulo 3:

• El historial con límite: nuestro HistorialConLimite apilaba por arriba pero, al llenarse, descartaba por el fondo con un pop(0) de coste O(n). Necesitábamos una estructura eficiente por los dos extremos. Esa estructura existe, se llama deque (cola doble), y la veremos en la lección 04-05.
• El "más prioritario": la PilaConMinimo respondía en O(1) "¿cuál es el elemento mínimo?", pero no permitía extraerlo si no estaba en la cima. Extraer siempre el más prioritario es justo lo que hace una cola de prioridad (lección 04-04).
• El orden justo: una pila atiende primero lo último que llegó. Para muchas situaciones eso es exactamente lo contrario de lo que queremos: las notificaciones de TaskFlow deben enviarse en el orden en que se generaron. Esa política es el FIFO, y es el corazón de este módulo.

Fíjate en el patrón: no cambiamos de estructura por capricho, sino porque el problema nos empuja. Igual que la pila era la estructura natural del "deshacer", la cola es la estructura natural del "atender por orden de llegada".

FIFO son las siglas de First In, First Out: el primero que entra es el primero que sale. Una cola es un TDA (tipo de dato abstracto, como vimos en el módulo 1) con dos reglas de acceso muy estrictas:

• Los elementos entran siempre por un extremo, llamado el final (o cola, en el sentido de "final de la fila").
• Los elementos salen siempre por el otro extremo, llamado el frente.

Esa separación de extremos es la diferencia esencial con la pila, donde todo ocurría por el mismo lado (la cima). Al usar extremos opuestos, el orden de salida reproduce exactamente el orden de llegada:

Si encolamos las notificaciones 1, 2 y 3 (en ese orden) y luego desencolamos tres veces, obtenemos 1, 2 y 3, en ese mismo orden. Con una pila habríamos obtenido 3, 2 y 1.

Conviene tener las dos políticas frente a frente, porque elegir mal entre ellas produce errores silenciosos (el programa funciona, pero atiende las cosas en el orden equivocado):

Una forma útil de decidir cuál necesitas: pregúntate qué elemento debe atenderse a continuación. Si la respuesta es "el más reciente" (deshacer, volver atrás, cerrar el último paréntesis abierto), es una pila. Si es "el que más tiempo lleva esperando" (atender peticiones, enviar mensajes, repartir trabajo con justicia), es una cola.

Como hicimos con la pila, definimos la cola por su contrato: qué operaciones ofrece y qué promete cada una, sin decir todavía nada de cómo se implementa por dentro. Ese es el espíritu del TDA del módulo 1: primero la interfaz, después la implementación.

Dos observaciones que ya conoces del módulo 3 y que siguen vigentes:

• Error en cola vacía: mantendremos la decisión que tomamos con la pila: desencolar() y frente() sobre una cola vacía lanzan una excepción (estilo EAFP), en lugar de devolver None. Un None silencioso se confunde con un elemento válido y esconde errores.
• Contrato estable, implementación intercambiable: igual que Pila y PilaEnlazada compartían contrato (y lo verificábamos con probar_contrato), en este módulo veremos varias implementaciones de cola con este mismo contrato. El código cliente no debería notar el cambio.

Aunque aún no hemos implementado nada, ya podemos escribir código contra el contrato, que es como piensa un buen diseñador de software:

Observa que la tarea con prioridad: 1 (la máxima en TaskFlow) no sale la primera: en una cola FIFO manda el orden de llegada, no la urgencia. Cuando queramos que mande la urgencia necesitaremos otra estructura —la cola de prioridad de la lección 04-04—. Distinguir ambas necesidades es media batalla ganada.

La cola del supermercado. Las personas se incorporan por el final y la cajera atiende por el frente. Nadie (en un mundo civilizado) se cuela: quien más tiempo lleva esperando es atendido primero. Las dos operaciones del contrato están a la vista: llegar a la fila es encolar, ser atendido es desencolar, y mirar quién es el siguiente sin atenderlo aún es frente.

La cola de impresión. Varias personas envían documentos a una impresora compartida. La impresora solo puede imprimir un documento a la vez, así que los trabajos esperan en una cola: se imprimen en el orden exacto en que se enviaron. Esta analogía añade un matiz importante que el supermercado no tiene: la cola actúa de amortiguador entre un productor rápido y un consumidor lento. Diez personas pueden enviar documentos en un segundo; la impresora tardará minutos en procesarlos, pero ninguno se pierde y ninguno adelanta a otro. Guarda esta idea: es la clave de casi todos los usos profesionales de las colas.

Las colas no son un ejercicio académico; son una de las estructuras más usadas en sistemas en producción:

• Colas de mensajes (RabbitMQ, Amazon SQS, Kafka en su versión más simple): un servicio deja mensajes en una cola y otro servicio los consume a su ritmo. Es la impresora a escala industrial: desacopla productores de consumidores y absorbe picos de carga sin perder trabajo.
• Buffers de entrada/salida: cuando escribes en el teclado más rápido de lo que el programa lee, las pulsaciones esperan en un buffer FIFO. Lo mismo ocurre con paquetes de red en un router o con audio en streaming. Muchos de estos buffers tienen tamaño fijo y "dan la vuelta": son las colas circulares de la lección 04-03.
• Planificadores de procesos: el sistema operativo mantiene colas de procesos listos para ejecutarse. La variante más famosa, el round-robin, reparte turnos de CPU por orden de llegada; conecta directamente con el RepartidorTareas que construimos sobre la ListaCircular en el módulo 2, y lo retomaremos en los ejercicios (04-06).
• Recorridos de grafos: el algoritmo BFS (búsqueda en anchura) explora un grafo "por capas" usando una cola. Solo lo dejamos anotado como anticipo: se desarrolla en el módulo 7.

Situemos todo esto en nuestra aplicación. Cada vez que en TaskFlow ocurre algo relevante —se asigna una tarea, cambia un estado, se acerca una fecha límite— hay que notificar al usuario afectado. Enviar una notificación (correo, aviso móvil) es lento comparado con generar el evento, así que no podemos enviarlas "en el momento": las acumularíamos y bloquearíamos la aplicación.

La solución profesional es la de la impresora: un productor (la aplicación) encola notificaciones al instante, y un consumidor (el proceso de envío) las va desencolando y enviando a su ritmo. Requisitos:

1. Ninguna notificación se pierde.
2. Se envían en el orden en que se generaron (sería absurdo recibir "tarea completada" antes que "tarea creada").
3. Encolar debe ser instantáneo, porque ocurre en medio de la acción del usuario.

Los requisitos 1 y 2 los garantiza el contrato FIFO. El requisito 3 es una exigencia de coste: encolar y desencolar deben ser O(1). Y aquí viene el aviso para la próxima lección: la implementación "obvia" con una list de Python incumple ese requisito, por la misma trampa del pop(0) que medimos con timeit en el módulo 1. Resolverlo con elegancia —reutilizando la ListaEnlazada del módulo 2— es el objetivo de la lección 04-02.

Para que sepas qué te espera, este es el plan del módulo, y no es casual: cada lección responde a uno de los puentes del módulo 3.

• Confundir la política con la estructura: FIFO es una política (un contrato); la cola puede implementarse de muchas formas (lista enlazada, dos pilas, array circular). No digas "una cola es una lista": una cola es un contrato que una lista puede (mal o bien) implementar.
• Usar una pila donde toca una cola (o viceversa): el código no fallará, pero el orden de atención será el inverso al esperado. Si procesas notificaciones con una pila, el usuario recibirá primero la última generada. Pregúntate siempre: ¿debe salir "lo más reciente" o "lo más antiguo"?
• Esperar que la cola FIFO respete prioridades: no lo hace, y no debe hacerlo. Si una tarea de prioridad 1 debe adelantar a las demás, necesitas una cola de prioridad (04-04), no un FIFO con parches.
• Consejo: cuando leas documentación de sistemas (mensajería, sistemas operativos, redes), busca las palabras queue, enqueue, dequeue, front/head y rear/tail. Reconocer el contrato bajo distintos nombres es señal de que has interiorizado el TDA.

Sin ejecutar nada, indica qué imprime este código (asumiendo una Cola que cumple el contrato):

Para cada escenario de TaskFlow, decide si la estructura adecuada es una pila (LIFO) o una cola (FIFO), y justifica en una frase:

1. Reproducir los cambios de una tarea en orden cronológico para auditoría.
2. Deshacer las últimas modificaciones de la descripción de una tarea.
3. Repartir las peticiones de exportación de informes entre los usuarios, atendiéndolas con justicia.
4. Comprobar que los paréntesis de una fórmula de filtro están balanceados.

La impresora de la oficina necesita, además del contrato básico de cola, una operación para que un administrador cancele todos los trabajos pendientes. Escribe la tabla de contrato completa (operación, qué hace, qué promete) de esa ColaImpresion, sin implementarla. Pista: cancelar todo no debe obligar a desencolar en bucle desde fuera.

Solución 1:

La clave está en la tercera línea: frente() no extrae, por eso después desencolar() sigue devolviendo "B".

Solución 2:

1. Cola: la auditoría exige orden cronológico de llegada (FIFO).
2. Pila: deshacer atiende siempre lo más reciente (LIFO), como el GestorDeshacerRehacer del módulo 3.
3. Cola: "con justicia" = por orden de llegada, nadie se cuela.
4. Pila: cada cierre casa con la apertura más reciente, exactamente el filtro_balanceado del módulo 3.

Solución 3:

Fíjate en que ampliar un contrato es legítimo; lo importante es prometer con precisión qué hace la nueva operación, incluidos los casos límite.

Hemos definido la cola como TDA: un contrato FIFO con encolar, desencolar, frente, esta_vacia y tamano, donde los elementos entran por el final y salen por el frente, garantizando el orden de llegada. La hemos contrastado punto por punto con la pila, hemos visto que sostiene sistemas reales (colas de mensajes, buffers, planificadores) y hemos identificado su papel en TaskFlow: la cola de notificaciones pendientes de enviar, que exige además costes O(1) en ambos extremos. Justo ahí está el reto: la implementación ingenua sobre list cae en la trampa del pop(0) que ya conocemos. En la próxima lección ejecutaremos las operaciones paso a paso, mediremos esa trampa y construiremos la clase Cola correcta reutilizando la ListaEnlazada del módulo 2 — con una sorpresa final: una cola hecha con dos pilas.