4.2.1 Concepto de Cola.

Una cola (queue en inglés) es una lista de elementos en donde siempre se insertan nuevos elementos al final de la lista y se extraen elementos desde el inicio de la lista. También se conoce a las colas como listas FIFO (FIRST IN - FIRST OUT: el primero que entra es el primero que sale).

Las operaciones básicas en una cola son:

• encolar(x): inserta el elemento x al final de la cola (enqueue en inglés).
• sacar(): retorna el elemento que se ubica al inicio de la cola (dequeue en inglés).
• estaVacia(): retorna verdadero si la cola esta vacía, falso en caso contrario.

Al igual que con el TDA pila, una cola se puede implementar tanto con arreglos como con listas enlazadas. A continuación se verá la implementación usando un arreglo.

Las variables de instancia necesarias en la implementación son:

• primero: indica el índice de la posición del primer elemento de la cola, es decir, la posición el elemento a retornar cuando se invoque sacar.
• ultimo: indica el índice de la posición de último elemento de la cola. Si se invoca encolar, el elemento debe ser insertado en el casillero siguiente al que indica la variable.
• numElem: indica cuántos elementos posee la cola. Definiendo MAX_ELEM como el tamaño máximo del arreglo, y por lo tanto de la cola, entonces la cola esta vacía si numElem==0 y está llena si numElem==MAX_ELEM.

Un detalle faltante es el siguiente: ¿qué pasa si la variable ultimo sobrepasa el rango de índices del arreglo? Esto se soluciona definiendo que si después de insertar un elemento el índice ultimo == MAX_ELEM, entonces se asigna ultimo = 0 , y los siguientes elementos serán insertados al comienzo del arreglo. Esto no produce ningún efecto en la lógica de las operaciones del TDA, pues siempre se saca el elemento referenciado por el índice primero, aunque en valor absoluto primero > ultimo. Este enfoque es conocido como implementación con arreglo circular, y la forma más fácil de implementarlo es haciendo la aritmética de subíndices módulo MAX_ELEM.