🎢 Colas

init

Pruébalo: Encola/desencola en la cinta. Cambia a buffer circular para ver cómo la indexación circular reutiliza memoria fija — sin desplazamientos, nunca.

Por qué importa

Las colas modelan filas de espera, planificación de tareas y exploración en anchura. Siempre que importa el orden de llegada, necesitas una cola. Son fundamentales para los sistemas operativos, las redes y los algoritmos de grafos.

La idea

Piensa en una fila en una cafetería. La primera persona en la fila es atendida primero. Los nuevos clientes se unen al final.

El primero en entrar, el primero en salir (FIFO).

Donde las pilas tratan de deshacer y retroceder, las colas tratan de justicia y orden:

• Cola de impresión: Los documentos se imprimen en el orden en que se enviaron
• Planificador de tareas: Los procesos se ejecutan en orden de llegada (round-robin)
• BFS: Explora nodos nivel por nivel, visitando primero los nodos descubiertos antes

Encolar (añadir al final) y desencolar (quitar del frente) son ambas O(1).

Puntos clave

• Encolar y desencolar son O(1)
• Orden FIFO — el primero en entrar, el primero en salir
• Se usa en BFS, planificación de tareas, almacenamiento en buffer
• El buffer circular es una implementación eficiente basada en arreglos

Profundizando

Las colas de doble extremo (deques) permiten inserción/eliminación en ambos extremos — útiles para algoritmos de ventana deslizante y el truco de la deque monótona para "el máximo en cada ventana de tamaño k" en O(n) total. Las colas de prioridad (cubiertas en la lección de montículos) son colas "injustas" donde la importancia prevalece sobre el orden de llegada — generaliza esta lección con una sola perilla y tienes un montículo. Los buffers circulares implementan colas de forma eficiente en arreglos de tamaño fijo dando la vuelta al llegar al final.

En la práctica

• Colas de tópicos de ROS. Cada publicador en ROS (Robot Operating System) escribe en una cola de buffer circular de capacidad fija por tópico. Cuando los suscriptores no pueden seguir el ritmo, se descartan los mensajes más antiguos. Ajustar esa profundidad de cola es una de las primeras cosas que aprende un ingeniero de robótica.
• Brokers de mensajes (Kafka, RabbitMQ, NATS, Redis Streams). Todos construidos sobre la abstracción de cola con persistencia y replicación añadidas encima. Un consumidor lee desde la cabeza; los productores agregan a la cola.
• Frontera BFS en el mapa de un robot. El modo de cuadrícula de la lección de grafos muestra esto directamente — la planificación de rutas por frente de onda es BFS con una cola, y así es como se inicializan la mayoría de los planificadores de cuadrícula de ocupación (A*, JPS, theta*).
• Colas de impresión (spoolers), colas de ejecución del planificador del SO, colas de peticiones de servidores web. Donde sea que "el primero que llega, el primero que se atiende" sea la política.

Por qué el buffer circular es O(1) amortizado — aunque el redimensionamiento sea O(n)

Una cola ingenua respaldada por arreglo desencola desde el frente desplazando los n elementos restantes hacia la izquierda — O(n). El buffer circular esquiva esto con los índices modulares que viste en la demostración: front y rear avanzan módulo la capacidad, sin dejar huecos que rellenar.

¿Pero qué pasa cuando el anillo se llena? Asignas un nuevo buffer del doble de tamaño y copias. Eso es O(n) — el mismo truco de redimensionamiento que usa la prueba de duplicación de arreglos. A lo largo de n encolados, el trabajo total es 2n − 1, así que por operación es O(1) amortizado. Sin duplicar — digamos que crecieras una constante cada vez — el trabajo total se dispararía a O(n²).

Esta es la segunda vez que ves el patrón de duplicación; lo verás de nuevo en el rehashing de tablas hash e implícitamente en la construcción de montículos. Reconoce la forma: "operación cara y rara, pagada por muchas baratas previas" — eso es el análisis amortizado en una sola frase.

Detalles matemáticos

Complejidad temporal

Enqueue: O(1)

Dequeue: O(1)

Peek front: O(1)

Search: O(n)

Buffer circular

front = (front + 1) mod capacity

rear = (rear + 1) mod capacity

Implementación

Cola con VecDeque

use std::collections::VecDeque;

let mut queue = VecDeque::new();

queue.push_back(1);  // Encolar
queue.push_back(2);
queue.push_back(3);  // Cola: [1, 2, 3]

let front = queue.pop_front();  // Devuelve Some(1)
// La cola ahora es [2, 3]

Aplicaciones clásicas

• Recorrido de grafos BFS
• Planificación de tareas/trabajos
• Cola de impresión (spooler)
• Buffer para datos en streaming

Práctica

Tres problemas de colas que se apoyan, cada uno, en una faceta distinta de la disciplina FIFO:

• Cola a partir de dos pilas — medio · simular FIFO con dos LIFO mediante vaciado perezoso (O(1) amortizado)
• Máximo en ventana deslizante — difícil · el patrón de la deque monótona, O(n) en lugar de O(n log k)
• Buffer circular acotado (Robótica) — medio · el FIFO de capacidad fija sobre el que se construye cada tópico de ROS y cada controlador UART

→ Explora todos los problemas de práctica