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 quien va primero se llama táctica de encolamiento. La táctica de encolamiento mas simple se llama FIFO, de “first-in-firrst-out", el primero que entra es el primero que sale". La táctica de encolamiento mas general es el encolamiento priorizado, en la que a cada cliente se le asigna una prioridad y el cliente con la prioridad mas alta pasa primero, sin importar el orden de llegada. Decimos que es la tactica mas general porque la prioridad se puede basar en cualquier cosa: a que hora sale el vuelo; cuantos productos lleva el cliente; cuan 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 esta 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.