Colas de espera (definición).

Definición.

   Una cola de espera o simplemente cola, es un conjunto ordenado de elementos del que se pueden eliminar dichos elementos de un extremo (llamado inicio de la cola), y en el que pueden insertarse elementos en el extremo opuesto (llamado fin de la cola).

   El primer elemento insertado en una cola es el primer elemento en ser eliminado, mientras que el último elemento insertado es el último en ser eliminado. Por esta razón, se dice que una cola es una estructura de datos de tipo FIFO (First In First Out).

   En el mundo real abundan ejemplos de este tipo de estructuras:

• Líneas aéreas.
• Líneas de autobuses.
• Colas de espera en los supermercados.
• Colas de espera en los bancos.
• Etcétera, etcétera, etcétera.

   La siguiente figura muestra en (a) una representación de una cola de espera que permite visualizar los elementos almacenados en la misma:

Inserción y eliminación de elementos en una cola de espera.

   La eliminación de uno de los elementos (A) se muestra en la figura anterior en (b), mientras que la inserción de los elementos D y E se muestra en (c). Observe también cómo las referencias al inicio y fin de la cola son modificadas en cada inserción y eliminación respectivamente.

Operaciones primitivas.

   Se definen tres operaciones primitivas sobre una cola de espera:

1. La operación inserta agrega un elemento en la parte final de la cola. También se dice que esta operación forma o encola un elemento en la estructura de datos.
2. La operación elimina suprime un elemento de la parte inicial de la cola. Esta operación despacha o atiende al elemento que se encuentra al inicio de la cola.
3. La operación estaVacia (esta operación fue definida como opcional o deseable para la pila. Para el caso de la cola dicha operación es ahora una primitiva, por lo que su implementación es requerida) regresa verdadero o falso dependiendo de si la cola de espera contiene o no elementos respectivamente.

   Una operación deseable para una cola de espera, sería la de imprimir todos los elementos de la cola, la cual se denotará como imprime.

Representación.

   La representación mostrada en la siguiente figura es una abstracción de la implementación que se realizará en la entrada correspondiente a la implementación:

Abstracción de una cola de espera como una secuencia de nodos.

 

    Observe cómo la figura anterior luce muy similar a la de la pila. Sin embargo, esta figura muestra el uso de dos referencias: inicio y fin, las cuales denotan, respectivamente, el primero y último de los elementos almacenados en la cola de espera. Note también que, para el caso de un solo elemento, dichas referencias harán referencia, valga la redundancia, al mismo nodo.

   Por otro lado, los diagramas de clases UML siguientes muestran el diseño de clases para la cola de espera que se desea implementar. Dicho diseño complementa, en consecuencia, la definición de dicha estructura de datos. A su vez, los diagramas de clases muestran también la relación que existe entre las clases más importantes que se involucrarán durante la implementación de la estructura de datos en cuestión.

Diagrama de clases UML para la cola de espera (Java).

Diagrama de clases UML para la cola de espera (C++).

    En este sentido valdría la pena hacer una aclaración: lo más deseable sería generar un diagrama de clases que representara la idea general del diseño de la estructura de datos con independencia del lenguaje de implementación; sin embargo, con la finalidad de enfatizar las diferencias a considerar en la implementación, se ha optado por manejar dos diagramas de clases que, aunque esencialmente iguales, especifican diferencias sutiles con respecto a los lenguajes de programación utilizados para los ejemplos.