La diferencia con las pilas es en el modo de entrada / salida de datos; en las colas se realizan las inserciones al final de la lista, no al principio.

Por eso, se usan para almacenar datos que necesitan ser procesados según el orden de llegada.

Las eliminaciones se realizan al principio de la lista frente (front), y las inserciones se realizan en el otro extremo final (rear).

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Las Colas también se utilizan en muchas maneras en los sistemas operativos para planificar el uso de los distintos recursos de la computadora. Uno de estos recursos es la propia CPU (Unidad Central de Procesamiento).

Si esta trabajando en una sistema multiusuario, cuando le dice a la computadora que ejecute un programa concreto, el sistema operativo añade su petición a su "cola de trabajo".

Cuando su petición llega al frente de la cola, el programa solicitado pasa a ejecutarse. Igualmente, las colas se utilizan para asignar tiempo a los distintos usuarios de los dispositivos de entrada/salida (E/S), impresoras, discos, cintas y demás. El sistema operativo mantiene colas para peticiones de imprimir, leer o escribir en cada uno de estos dispositivos.

Se las puede representar por listas enlazadas o por arrays

C= Q(1), Q(2)......., Q(n).

En cualquier caso se necesitan dos punteros

• frente (f)
• final (r)

parte no utilizada de la lista Cola parte no utilizada de la lista

Para ver el gráfico seleccione la opción "Descargar" del menú superior

• Representación de una Cola mediante una lista enlazada

frente final

Las operaciones que se pueden realizar con una cola son:

1. Acceder al primer elemento de la Cola
2. Añadir un elemento al final de la Cola
3. Eliminar el primer elemento de la Cola
4. Vaciar una Cola
5. Verificar el estado de la Cola: vacía, Llena.

Función: Inicializa Cola al estado vacío

Entrada: Cola a inicializar

Precondiciones: Ninguna

Salida: Cola (inicializada)

Postcondiciones: Cola está vacía

Función: Indica si la Cola esta vacía

Entrada: Cola a ser comprobada

Precondiciones: Ninguna

Salida: Cola Vacía (indicador Booleano)

Postcondiciones: ColaVacía= (cola está vacía)

Función: Indica si esta llena

Entrada: Cola a ser comprobada

Precondiciones: Ninguna

Salida: Cola llena (indicador Booleano)

Postcondiciones: ColaLlena = (cola está llena)

Función: Añade Nuevo Elemento al final de la Cola

Entrada: Cola, Nuevo Elemento a ser añadido

Precondiciones: Hay espacio en la Cola

Salida: Cola (cambiada)

Postcondiciones: Cola = Cola original con Nuevo Elemento añadido al final

Entrada: Cola

Precondiciones: Cola no esta vacía

Salida: Cola (cambiada)

ElemSuprimido

Postcondiciones: Cola = Cola original con el frente quitado

ElemSuprimido = elemento frente de la cola original

Definimos el array.

COLA = COLA(1), COLA(2), ...., COLA(n).

n = longitud máxima

f y r = punteros frente y final

x = elementos a insertar

procedimiento inserción

inicio

si r > = n

entonces escribir "desbordamiento de la pila"

sino r r + 1

si r > n

entonces r 1

finsi

COLA(r) x

finsi

{ poner el puntero f al valor 1, a fin de poder hacer eliminaciones posteriores }

si f = 0

entonces f 1

finsi

fin

El primer elemento introducido Q(n) que es el eliminado, se almacena en una variable auxiliar x, para eliminar se tendrá que verificar que la cadena este vacía.

Procedimiento eliminar

Inicio

{verificar cola vacía}

si f = 0

entonces escribir ‘cola vacía’

sino x cola (f)

f f + 1

si f > n

entonces f 1

finsi

finsi

{ verificar si la cola se ha quedado vacía y en ese caso dejar los puntero frontal y final en condiciones iniciales, cero}

si f = 0 {condición de pila vacía}

entonces f 0

r 0

finsi

fin

Una operación muy útil es ver si la cola está vacía. Cola Vacía (Cola) devuelve True si la Cola está vacía y False en los demás casos. Ponemos SupCola cuando la cola no está vacía. Teóricamente ponemos siempre InsCola, porque en principio, una cola no tiene un tamaño limitado. Sin embargo, sabemos de nuestra experiencia con las pilas que ciertas implementaciones requiere que veamos si la estructura está llena antes de añadir otro elemento.

Las colas pueden necesitar cantidad de memoria sobre todo si se diseña con un gran numero de elementos. Para evitar este desperdicio de memoria, existe un procedimiento para diseñar las colas mediante una lista circular.

Para ver el gráfico seleccione la opción "Descargar" del menú superior

De tal forma que el elemento Q(1), quede a continuación de Q (n).

Los subalgoritmos (procedimientos) de inserción y eliminación de una cola circular se indican a continuación.