Colas

Este capı́tulo presenta dos TADs: la Cola y la Cola Priorizada. En la vida real, una cola es una fila de clientes esperando un servicio de algún tipo. En la mayorı́a de los casos, el primer cliente de la fila es el primero al que se va a servir. Sin embargo, hay excepciones. En los aeropuertos, a veces se saca de la cola a los clientes cuyos vuelos van a salir pronto. En los supermercados, un cliente educado puede dejar que alguien que lleva pocos productos pase antes.

La regla que determina quién va primero se llama táctica de encolamiento. La táctica de encolamiento más simple se llama FIFO, de “first-in-first-out”,
“el primero que entra es el primero que sale”. La táctica de encolamiento más general es el encolamiento priorizado, en la que a cada cliente se le asigna una prioridad y el cliente con la prioridad más alta pasa primero, sin importar el orden de llegada. Decimos que es la táctica más general porque la prioridad se puede basar en cualquier cosa: a qué hora sale el vuelo; cuántos productos lleva el cliente; cuán importante es el cliente. Por supuesto, no todas las tácticas de prioridad son “justas”, pero la justicia siempre es subjetiva.

El TAD Cola y el TAD Cola Priorizada tienen el mismo conjunto de operaciones. La diferencia está en la semántica de las operaciones: una cola usa la táctica FIFO, y una cola priorizada (como su propio nombre indica) usa una táctica de encolamiento priorizado.

TEMARIO: