COLAS

1. INTRODUCCIÓN.

Una Cola es otro tipo especial de lista en el cual los elementos se insertan por un extremo (el posterior) y se suprimen por el otro (el anterior o frente). Las colas se conocen tambien como listas FIFO (primero en entrar,primero en salir). Las operaciones para las colas son análogas a las de las pilas. Las diferencias sustanciales consisten en que las inserciones se hacen al final de la lista, y no al principio, y en que la terminología tradicional para colas y listas no es la misma. Las primitivas que vamos a considerar para las colas son las siguientes.

2. OPERACIONES PRIMITIVAS DE LAS COLAS.

Dentro del tipo abstracto de cola podemos proponer las siguientes primitivas:

• CREAR()
• DESTRUIR(C)
• FRENTE(C)
• PONER_EN_COLA(x,C)
• QUITAR_DE_COLA(C)
• VACIA(C)

ESPECIFICACIÓN SEMANTICA Y SINTACTICA.

• cola crear ()
  Argumentos: Ninguno.
  Efecto: Devuelve una cola vacia preparada para ser usada.
  
  
• void destruir(cola C)
  Argumentos: Una cola C.
  Efecto: Destruye el objeto C liberando los recursos que mantiene que empleaba.Para volver a usarlo habrá que crearlo de nuevo.
  
  
• tElemento frente (cola C)
  Argumentos: Recibe una cola C no vacía.
  Efecto: Devuelve el valor del primer elemento de la cloa C. Se puede escribir en función de las operaciones primitivas de las listas como: ELEMENTO(PRIMERO(C),C).
  
  
• void poner_en_cola (tElemento x, cola C)
  Argumentos:

  x: Elemento que queremos insertar en la cola.
  C: Cola en la que insertamos el elemento x.
  

  Efecto: Inserta el elemento x al final de la cola C. En función de las operaciones de las listas seria: INSERTA(x,FIN(C),C).
  
  
• void quitar_de_cola (cola C)
  Argumentos: Una cola C que debe ser no vacía.
  Efecto: Suprime el primer elemento de la cola C. En función de las operaciones de listas seria: BORRA(PRIMERO(C),C).
  
  
• int vacia (cola C)
  Argumentos: Una cola C.
  Efecto: Devuelve si la cola C es una cola vacía.
  
  

EQUIVALENCIA CON LAS LISTAS

3. IMPLEMENTACIÓN DE LAS COLAS.

IMPLEMENTACIÓN DE COLAS BASADA EN CELDAS ENLAZADAS.

Igual que en el caso de las pilas, cualquier implementación de listas es válida para las colas. No obstante, para aumentar la eficiencia de PONER_EN_COLA es posible aprovechar el hecho de que las inserciones se efectúan sólo en el extremo posterior de forma que en lugar de recorrer la lista de principio a fin cada vez que desea hacer una inserción se puede mantener un apuntador al último elemento. Como en las listas de cualquier clase, tambien se mantiene un puntero al frente de la lista. En las colas ese puntero es útil para ejecutar mandatos del tipo FRENTE o QUITA_DE_COLA. Utilizaremos al igual que para las listas, una celda cabecera con el puntero frontal apuntándola con lo que nos permitirá un manejo más cómodo. Gráficamente, la estructura de la cola es tal y como muestra la figura:

Una cola es pues un puntero a una estructura compuesta por dos punteros, uno al extremo anterior de la cola y otro al extremo posterior. La primera celda es una celda cabecera cuyo campo elemento se ignora.

La definición de tipos es la siguiente:

 typedef struct Celda{
     	 tElemento elemento;
 	 struct Celda *siguiente;
 } celda;

typedef struct {
	celda *ant,*post;
} tcola;

typedef tcola *cola;

FUNCIÓN DE ABSTRACCIÓN.

Dado el objeto del tipo rep c, *c = (ant, post), el objeto abstracto que representa es:

<c->ant->siguiente->elemento, c->ant->siguiente->siguiente->elemento, ..., c->ant->siguiente-> ⁽ⁿ⁾ ->siguiente->elemento>, tal que c->siguiente->siguiente-> ⁽ⁿ⁾ ->siguiente = c->post.

INVARIANTE DE LA REPRESENTACIÓN.

Dado un objeto del tipo rep c, *c = (ant, post), debe cumplir:

1. c tiene valores obtenidos de llamadas (tcola **) malloc(sizeof(tcola));
   
2. Los campos siguiente de los nodos, c->ant y c->post tienen direcciones válidas, obtenidas de llamadas a (celda) malloc(sizeof(celda)). Sólo es NULL el últimode los campos siguiente.
   

Con estas definiciones, la implementación de las primitivas es la siguiente:

cola CREAR () 
    
    

 {
  cola C;
  
  C = (tcola *) malloc(sizeof(tcola));
  if (C == NULL) 
     error("Memoria insuficiente."); 
  C->ant = C->post = (celda *)malloc(sizeof(celda));
  if (C->ant == NULL) 
     error("Memoria insuficiente.");
  C->ant->siguiente = NULL;
  return C;
 }

void DESTRUIR (cola C) 
    
    

 {
  while (!VACIA(C))
     QUITAR_DE_COLA(C);
  free(C->ant);
  free(C);
 }

int VACIA (cola C)  
    
    

 {
  return(C->ant == C->post);
 }

tElemento FRENTE (cola C) 
    
    

 {
  if (VACIA(C)) {
     error("Error: Cola Vacia.");
  }
  return(C->ant->siguiente->elemento);
 }

void PONER_EN_COLA (tElemento x,cola C) 
    
    

 {
  C->post->siguiente = (celda *) malloc(sizeof(celda));
  if (C->post->siguiente == NULL) 
     error("Memoria insuficiente.");
  C->post = C->post->siguiente;
  C->post->elemento = x;
  C->post->siguiente = NULL;
 }

void QUITAR_DE_COLA (cola C) 
    
    

 {
  celda *aux;

  if (VACIA(C))
     error("Cola vacia.");
  aux = C->ant;
  C->ant = C->ant->siguiente;
  free(aux);
 }

Este procedimiento QUITAR_DE_COLA suprime el primer elemento de C desconectando el encabezado antiguo de la cola,de forma que el primer elemento de la cola se convierte en la nueva cabecera.

En la figura siguiente puede verse esquematicamente el resultado de hacer consecutivamente las siguientes operaciones:

• C=CREAR(C);
• PONER_EN_COLA(x,C);PONER_EN_COLA(y,C);
• QUITAR_DE_COLA(C);
• DESTRUIR(C);

Se puede observar que en el primer caso, la memoria que se obtiene del sistema es la de la estructura de tipo celda que hace de cabecera y la memoria para ubicar los dos punteros anterior y posterior. En los dos últimos casos, la línea punteada indica la memoria que es liberada.

IMPLEMENTACIÓN DE LAS COLAS USANDO MATRICES CIRCULARES.

La implementación matrical de las listas no es muy eficiente para las colas, puesto que si bien con el uso de un apuntador al último elemento es posible ejecutar PONER_EN_COLA en un tiempo constante, QUITAR_DE_COLA, que suprime le primer elemento, requiere que la cola completa ascienda una posición en la matriz con lo que tiene un orden de eficiencia lineal proporcional al tamaño de la cola. Para evitarlo se puede adoptar un criterio diferente. Imaginemos a la matriz como un circulo en el que la primera posición sigue a la última, en la forma en la que se ve en la figura siguiente. La cola se encuentra en alguna parte de ese círculo ocupando posiciones consecutivas. Para insertar un elemento en la cola se mueve el apuntador post una posición en el sentido de las agujas del reloj y se escribe el elemento en esa posición. Para suprimir un elemento simplemente se mueve ant una posición en el sentido de las agujas del reloj. De esta forma, la cola se mueve en ese sentido conforme se insertan y suprimen elementos. Obsérvese que utilizando este modelo los procedimientos PONER_EN_COLA y QUITAR_DE_COLA se pueden implementar de manera que su ejecución se realice en tiempo constante.

Existe un probelma que aparece en la representación de la figura anterior y en cualquier variación menor de esta estrategia (p.e. que post apunte a la última posición en el sentido de las agujas del reloj). El problema es que no hay forma de distinguir una cola vacia de una que llene el círculo completo salvo que mantengamos un bit que sea verdad si y solo si la cola está vacia. Si no deseamos mantener este bit debemos prevenir que la cola llene alguna vez la matriz. Para ver por qué puede pasar esto, supongamos que la cola de la figura anterior tuviera MAX_LONG elementos. Entonces, post apuntaría a la posición anterior en el sentido de las agujas del reloj de ant. ¿Qué pasaria si la cola estuviese vacia?. Para ver como se representa una cola vacia, consideramos primero una cola de un elemento. Entonces post y ant apuntarian a la misma posición. Si extraemos un elemento, ant se mueve una posición en el sentido de las agujas del reloj, formando una cola vacia. Por tanto una cola vacia tiene post a una posición de ant en el sentido de las agujas del reloj, que es exactamente la misma posición relativa que cuando la cola tenia MAX_LONG elementos. Por tanto vemos que aún cuando la matriz tenga MAX_LONG casillas, no podemos hacer crecer la cola más allá de MAX_LONG-1 casillas, a menos que introduzcamos un mecanismo para distinguir si la cola está vacía o llena.

Ahora escribimos las primitivas de las colas usando esta representación para una cola:

 typedef struct {
  tElemento *elementos;
  int Lmax;
  int ant,post;
 } tipocola;

 typedef tipocola *cola;
 
cola CREAR (int tamanoMax)
 {
  cola C;

  C = (cola) malloc(sizeof(tipocola));
  if (C == NULL) 
     error("No hay memoria.");
  C->Lmax = tamanoMax+1;
  C->ant = 0;
  C->post = C->Lmax-1;
  C->elementos = (tElemento *) calloc((tamanoMax+1), sizeof(tElemento));
  if (C->elementos == NULL) 
     error("No hay memoria.");
  return C;
 }

void DESTRUIR (cola *C)
 {
  free(*C->elementos);
  free(*C);
  *C == NULL;
 }

int VACIA (cola C)
 {
  return((C->post+1)%(C->Lmax) == C->ant)
 }

tElemento FRENTE (cola C)
 {
  if (VACIA(C))
     error("Cola vacia.");
  return(C->elementos[C->ant]);
 }

void PONER_EN_COLA (tElemento x,cola C)
 {
  if ((C->post+2) % (C->Lmax) == C->ant) 
     error("Cola llena.");
  C->post = (C->post+1) % (C->Lmax);
  C->elementos[C->post] = x;
 }

void QUITAR_DE_COLA (cola C)
 {
  if (VACIA(C))
     error("Cola vacia.");
  C->ant = (C->ant+1) % (C->Lmax);
 }

En esta implementación podemos observar que se reserva una posicón más que la especificada en el parametro de la función CREAR. La razón de hacerlo es que no se podrán ocupar todos los elementos de la matriz ya que debemos distinguir la cola llena de la cola vacía. Estas dos situaciones por lo tanto vienen representadas tal y como se muestra en la figura siguiente.

Se puede observar en el caso de la cola llena en la figura como la posición siguiente a post no es usada y por lo tanto es necesario crear una matriz de un tamaño N+1 para tener una capacidad para almacenar N elementos en cola.