* Definición
* Implementación mediante array circular
* Implementación mediante lista enlazada
* Otras consideraciones

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 dos operaciones 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 en salir.

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 incluye comprobació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 su tamañ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:

Esta versió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 i por 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 se determina 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 el elemento 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 elementos, es decir, una cola de DOS elementos.

Cola vacía:

Se encola un 3.

Se desencola el 3; ahora se tiene una cola vacía.

Se encolan el 5 y el 7. Se obtiene una cola llena.

Si se desencola se obtiene el 5. ¡Si en lugar de desencolar se encola un elemento cualquiera se obtiene una cola vacía!.

- Declaración:

struct tcola
{
  int entrada, salida;
  int elementos[MAX_COLA];
};

Una cola que tenga un elemento requiere que MAX_COLA = 2.

- Función que devuelve la posición siguiente a i en el array circular.

int siguiente(int i)
{
  return ((i+1) % MAX_COLA);
}

- Creación:

void crear(struct tcola *cola)
{
  cola->salida = 0;
  cola->entrada = MAX_COLA - 1;
}

- Función que devuelve verdadero si la cola está vacía, cosa que ocurre cuando el siguiente tras entrada es salida:

int vacia(struct tcola *cola)
{
  return (siguiente(cola->entrada) == cola->salida);
}

- Función que devuelve verdadero si la cola está llena, caso que se da cuando el siguiente elemento que sigue a entrada es salida:

int llena(struct tcola *cola)
{
  return (siguiente(siguiente(cola->entrada)) == cola->salida);
}

- Encolado:

void encolar(struct tcola *cola, int elem)
{
  cola->entrada = siguiente(cola->entrada);
  cola->elementos[cola->entrada] = elem;
}

- Desencolado:

void desencolar(struct tcola *cola, int *elem)
{
  *elem = cola->elementos[cola->salida];
  cola->salida = siguiente(cola->salida);
}

- Programa de prueba:

#include <stdio.h>

#define MAX_COLA 50 /* cola de 49 elementos */

int main(void)
{
  struct tcola cola;
  int elem;
  
  crear(&cola);
  if (vacia(&cola)) printf("\nCola vacia.");
  if (llena(&cola)) printf("\nCola llena.");
  encolar(&cola, 1);
  desencolar(&cola, &elem);
  return 0;
}

Segunda versión:

En este caso se omite la función siguiente, y se aprovechan todos los elementos. Sin embargo se contabiliza en una variable el número de elementos que hay en un momento dado en la cola. Esta implementación es parecida a la secuencial, pero vigilando que los índices no se pasen de rosca.

¿Como se determina la siguiente posición? Se avanza una posición, y si llega al límite del array el índice se actualiza al primer elemento. La lógica es la siguiente:

Para encolar: se encola en la posición indicada por entrada, y se avanza una posición.
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 el número de elementos es cero.
Cola llena: la cola está llena si el número de elementos es el máximo admitido.

- Declaración:

struct tcola
{
  int elems;
  int entrada, salida;
  int elementos[MAX_COLA];
};

Una cola que tenga dos elementos requiere que MAX_COLA = 2.

- Creación:

void crear(struct tcola *cola)
{
  cola->elems = cola->salida = cola->entrada = 0;
}

- Función que devuelve verdadero si la cola está vacía:

int vacia(struct tcola *cola)
{
  return (cola->elems == 0);
}

- Función que devuelve verdadero si la cola está llena:

int llena(struct tcola *cola)
{
  return (cola->elems == MAX_COLA);
}

- Encolado:

void encolar(struct tcola *cola, int elem)
{
  cola->elems++;
  cola->elementos[cola->entrada++] = elem;
  if (cola->entrada == MAX_COLA)
    cola->entrada = 0;
}

- Desencolado:

void desencolar(struct tcola *cola, int *elem)
{
  cola->elems--;
  *elem = cola->elementos[cola->salida++];
  if (cola->salida == MAX_COLA)
    cola->salida = 0;
}

- Programa de prueba:

  El mismo de antes sirve.

Implementación mediante lista enlazada

Para hacer la implementación se utilizará una lista circular sin cabecera.
La cola estará inicialmente vacía. Cuando se añadan elementos el puntero que mantiene la cola apunta al último elemento introducido, y el siguiente elemento al que apunta es al primero que está esperando para salir.

- ¿Cómo encolar?. Se crea el nuevo elemento, se enlaza con el primero de la cola. Si no está vacía hay que actualizar el enlace del, hasta el momento de la inserción, último elemento introducido. Por último se actualiza el comienzo de la cola, esté vacía o no.
- ¿Cómo desencolar?. Si tiene un sólo elemento se borra y se actualiza el puntero a un valor nulo. Si tiene dos o más elementos entonces se elimina el primero y el último apuntará al segundo.

Ejemplo gráfico de encolado. Partiendo de una cola que tiene el elemento 3, se van añadiendo el 5 y el 7 (observar de izquierda a derecha). A la hora de desencolar se extrae el siguiente al que apunta Cola.

Ejemplo gráfico de desencolado. Partiendo de la cola formada anteriormente, se han quitado los dos primeros elementos introducidos (observar de izquierda a derecha).

- Declaración:

struct tcola
{
  int clave;
  struct tcola *sig;
};

- Creación:

void crear(struct tcola **cola)
{
  *cola = NULL;
}

- Función que devuelve cierto si la cola está vacía:

int vacia(struct tcola *cola)
{
  return (cola == NULL);
}

- Encolado:

void encolar(struct tcola **cola, int elem)
{
  struct tcola *nuevo;

  nuevo = (struct tcola *) malloc(sizeof(struct tcola));
  nuevo->clave = elem;
  if (*cola == NULL)
    nuevo->sig = nuevo;
  else {
    nuevo->sig = (*cola)->sig;
    (*cola)->sig = nuevo;
  }
  (*cola) = nuevo;
}

- Desencolado:

void desencolar(struct tcola **c1, int *elem)
{
  struct tcola *aux;

  *elem = (*c1)->sig->clave;
  if ((*c1) == (*c1)->sig) {
    free(*c1);
    *c1 = NULL;
  }
  else {
    aux = (*c1)->sig;
    (*c1)->sig = aux->sig;
    free(aux);
  }
}

- Programa de prueba:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
  struct tcola *cola;
  int elem;

  crear(&cola);
  if (vacia(cola)) printf("\nCola vacia!");
  encolar(&cola, 3);
  desencolar(&cola, &elem);

  return 0;
}

Ver colasle.c para tener una implementación completa con listas enlazadas.

Al igual que en las pilas implementadas por listas enlazadas, es recomendable analizar el código devuelto por la función de asignación de memoria para evitar posibles problemas en un futuro.

Otras consideraciones

En algunos casos puede ser interesante implementar una función para contar el número de elementos que hay en la cola. Una manera de hacer esto con listas enlazadas es empleando la siguiente declaración:

struct nodo
{
  int clave;
  struct nodo *sig;
};
struct tcola
{
  int numero_elems; /* mantiene el numero de elementos */
  struct nodo *cola;
};

Los detalles de la implementación no se incluyen, pues es sencilla.

¿Qué implementación es mejor, arrays o listas?

Al igual que con las pilas, la mejor implementación depende de la situación particular. Si se conocen de antemano el número de elementos entonces lo ideal es una implementación por array. En otro caso se recomienda el uso de lista enlazada circular.