Informatica

Definición
Una cola es una estructura de datos de acceso restrictivo a sus elementos. Un ejemplo sencillo es la cola del cine o del autobús, el primero que llegue será el primero en entrar, y afortunadamente en un sistema informático no se cuela nadie salvo que el programador lo diga.
Las colas serán de ayuda fundamental para ciertos recorridos de árboles y grafos.
Las colas ofrecen dosoperaciones fundamentales, que son encolar (al final de la cola) y desencolar (del comienzo de la cola). Al igual que con las pilas, la implementación de las colas suele encapsularse, es decir, basta con conocer las operaciones de manipulación de la cola para poder usarla, olvidando su implementación interna.
Es una estructra de tipo FIFO (First In First Out), es decir: primero en entrar, primero ensalir.
A continuación se expone la implementación de colas, con arrays y con listas enlazadas circulares. En ambos casos se cubren cuatro operaciones básicas: Inicializar, Encolar, Desencolar, y Vacía. Las claves que contendrán serán simplemente números enteros.
 
Implementación mediante array circular
Esta implementación es estática, es decir, da un tamaño máximo fijo a la cola. No se incluyecomprobación de errores dentro del encolado y el desencolado, pero se implementan como funciones aparte.
¿Por qué un array circular? ¿Qué es eso? Como se aprecia en la implemetación de las pilas, los elementos se quitan y se ponen sobre la cima, pero en este caso se introducen por un sitio y se quitan por otro.
Podría hacerse con un array secuencial, como se muestra en las siguientes figuras.'Entrada' es la posición de entrada a la cola, y 'Salida' por donde salen.
En esta primera figura se observa que se han introducido tres elementos: 3, 1 y 4 (en ese orden):

se desencola, obteniendo un 3:

se encola un 7:

Enseguida se aprecia que esto tiene un grave defecto, y es que llega un momento en el que se desborda la capacidad del array. Una solución nada efectiva es incrementar sutamaño. Esta implementación es sencilla pero totalmente ineficaz.
Como alternativa se usa el array circular. Esta estructura nos permite volver al comienzo del array cuando se llegue al final, ya sea el índice de entrada o el índice de salida.
Se implementarán dos versiones de arrays circulares, con lo que el programador podrá escoger entre la que más le guste.
 
Primera versión:
Estaversión requiere el uso de la operación módulo de la división para determinar la siguiente posición en el array.
Por ejemplo, supóngase un array de N = 2 elementos, contando desde 0 hasta 1. Suponer que entrada = 0, salida = 1; Para determinar la posición siguiente del índice i en el array se procede así:
i <- (i+1) Mod N
siendo Mod la operación resto de la división entera. Asi:
- sustituyendo ipor salida se determina que salida = 0.
- sustituyendo i por entrada se determina que entrada = 1.
Nota: si el array está indexado entre 1 y N -como suele ser habitual en Pascal- entonces la expresión que determina la posición siguiente es esta:
i <- (i Mod N) + 1
si entrada = 1, salida = 2, entonces:
- sustituyendo i por salida se determina que salida = 1.
- sustituyendo i por entrada sedetermina que entrada = 2.

De esta manera se van dando vueltas sobre el array. La lógica es la siguiente:
Para encolar: se avanza el índice entrada a la siguiente posición, y se encola en la posición que apunte éste.
Para desencolar: el elemento desencolado es el que apunta el índice salida, y posteriormente se avanza salida a la siguiente posición.
Cola vacía: la cola está vacía si elelemento siguiente a entrada es salida, como sucede en el ejemplo anterior.
Cola llena: la cola está llena si el elemento que sigue al que sigue a entrada es salida.
Esto obliga a dejar un elemento vacío en el array, puesto que se reserva una posición para separar los índices entrada y salida.
Para aclararlo, se muestran una serie de gráficos explicativos, partiendo de un array de tres...