COLAS EN C

Una cola es un tipo especial de lista abierta en la que sólo se pueden insertar nodos en uno de los extremos de la lista y sólo se pueden eliminar nodos en el otro. Además, como sucede con las pilas, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.

Este tipo de lista es conocido como lista FIFO (First In First Out), el primero en entrar es el primero en salir.

El símil cotidiano es una cola para comprar, por ejemplo, las entradas del cine. Los nuevos compradores sólo pueden colocarse al final de la cola, y sólo el primero de la cola puede comprar la entrada.

El nodo típico para construir pilas es el mismo que vimos en los capítulos anteriores para la construcción de listas y pilas:

struct nodo {

   int dato;

   struct nodo *siguiente;

};

Declaraciones de tipos para manejar colas en C

Los tipos que definiremos normalmente para manejar colas serán casi los mismos que para manejar listas y pilas, tan sólo cambiaremos algunos nombres:

typedef struct _nodo {

   int dato;

   struct _nodo *siguiente;

} tipoNodo;

 typedef tipoNodo *pNodo;

typedef tipoNodo *Cola;

tipoNodo es el tipo para declarar nodos, evidentemente.

pNodo es el tipo para declarar punteros a un nodo.

Es evidente, a la vista del gráfico, que una cola es una lista abierta. Así que sigue siendo muy importante que nuestro programa nunca pierda el valor del puntero al primer elemento, igual que pasa con las listas abiertas. Además, debido al funcionamiento de las colas, también deberemos mantener un puntero para el último elemento de la cola, que será el punto donde insertemos nuevos nodos.

Teniendo en cuenta que las lecturas y escrituras en una cola se hacen siempre en extremos distintos, lo más fácil será insertar nodos por el final, a continuación del nodo que no tiene nodo siguiente, y leerlos desde el principio, hay que recordar que leer un nodo implica eliminarlo de la cola.

EJEMPLO

#include <stdlib.h>

#include <stdio.h>

typedef struct _nodo {

   int valor;

   struct _nodo *siguiente;

} tipoNodo;

typedef tipoNodo *pNodo;

/* Funciones con colas: */

void Anadir(pNodo *primero, pNodo *ultimo, int v);

int Leer(pNodo *primero, pNodo *ultimo);

int main()

{

   pNodo primero = NULL, ultimo = NULL;

   Anadir(&primero, &ultimo, 20);

   printf("Aniadir(20)\n");

   Anadir(&primero, &ultimo, 10);

   printf("Aniadir(10)\n");

   printf("Leer: %d\n", Leer(&primero, &ultimo));

   Anadir(&primero, &ultimo, 40);

   printf("Aniadir(40)\n");

   Anadir(&primero, &ultimo, 30);

   printf("Aniadir(30)\n");

   printf("Leer: %d\n", Leer(&primero, &ultimo));

   printf("Leer: %d\n", Leer(&primero, &ultimo));

   Anadir(&primero, &ultimo, 90);

   printf("Aniadir(90)\n");

   printf("Leer: %d\n", Leer(&primero, &ultimo));

   printf("Leer: %d\n", Leer(&primero, &ultimo));

   system("PAUSE");

   return 0;

}

void Anadir(pNodo *primero, pNodo *ultimo, int v)

{

   pNodo nuevo;

   /* Crear un nodo nuevo */

   nuevo = (pNodo)malloc(sizeof(tipoNodo));

   nuevo->valor = v;

   /* Este será el último nodo, no debe tener siguiente */

   nuevo->siguiente = NULL;

   /* Si la cola no estaba vacía, añadimos el nuevo a continuación de ultimo */

   if(*ultimo) (*ultimo)->siguiente = nuevo;

   /* Ahora, el último elemento de la cola es el nuevo nodo */

   *ultimo = nuevo;

   /* Si primero es NULL, la cola estaba vacía, ahora primero apuntará también al nuevo nodo */

   if(!*primero) *primero = nuevo;

}

int Leer(pNodo *primero, pNodo *ultimo)

{

   pNodo nodo; /* variable auxiliar para manipular nodo */

   int v;      /* variable auxiliar para retorno */

   

   /* Nodo apunta al primer elemento de la pila */

   nodo = *primero;

   if(!nodo) return 0; /* Si no hay nodos en la pila retornamos 0 */

   /* Asignamos a primero la dirección del segundo nodo */

   *primero = nodo->siguiente;

   /* Guardamos el valor de retorno */

   v = nodo->valor; 

   /* Borrar el nodo */

   free(nodo);

   /* Si la cola quedó vacía, ultimo debe ser NULL también*/

   if(!*primero) *ultimo = NULL;

   return v;

}