Una lista se comporta como una cola si las inserciones las hacemos al final y las extracciones las hacemos por el frente de la lista. También se las llama listas FIFO (First In First Out - primero en entrar primero en salir)
Confeccionaremos un programa que permita administrar una lista tipo cola. Desarrollaremos las funciones de insertar, extraer, vacia, imprimir y liberar.
Programa: programa164.c
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct nodo {
int info;
struct nodo *sig;
};
struct nodo *raiz=NULL;
struct nodo *fondo=NULL;
void insertar(int x)
{
struct nodo *nuevo;
nuevo=malloc(sizeof(struct nodo));
nuevo->info=x;
nuevo->sig=NULL;
if (vacia())
{
raiz = nuevo;
fondo = nuevo;
}
else
{
fondo->sig = nuevo;
fondo = nuevo;
}
}
int extraer()
{
if (!vacia())
{
int informacion = raiz->info;
struct nodo *bor = raiz;
if (raiz == fondo)
{
raiz = NULL;
fondo = NULL;
}
else
{
raiz = raiz->sig;
}
free(bor);
return informacion;
}
else
return -1;
}
void imprimir()
{
struct nodo *reco = raiz;
printf("Listado de todos los elementos de la cola.\n");
while (reco != NULL)
{
printf("%i - ", reco->info);
reco = reco->sig;
}
printf("\n");
}
void liberar()
{
struct nodo *reco = raiz;
struct nodo *bor;
while (reco != NULL)
{
bor = reco;
reco = reco->sig;
free(bor);
}
}
void main()
{
insertar(5);
insertar(10);
insertar(50);
imprimir();
printf("Extraemos uno de la cola: %i\n", extraer());
imprimir();
liberar();
getch();
return 0;
}
La declaración del nodo es igual a la Pila. Luego definimos dos punteros externos llamados raiz y fondo:
struct nodo {
int info;
struct nodo *sig;
};
struct nodo *raiz=NULL;
struct nodo *fondo=NULL;
raíz apunta al principio de la lista y fondo al final de la lista. Utilizar dos punteros tiene como ventaja que cada vez que tengamos que insertar un nodo al final de la lista no tengamos que recorrerla. Por supuesto que es perfectamente válido implementar una cola con un único puntero externo a la lista.
El método vacía retorna 1 si la lista no tiene nodos y 0 en caso contrario:
int vacia()
{
if (raiz == NULL)
return 1;
else
return 0;
}
En la inserción luego de crear el nodo tenemos dos posibilidades: que la cola esté vacía, en cuyo caso los dos punteros externos a la lista deben apuntar al nodo creado, o que haya nodos en la lista.
void insertar(int x)
{
struct nodo *nuevo;
nuevo=malloc(sizeof(struct nodo));
nuevo->info=x;
nuevo->sig=NULL;
if (vacia())
{
raiz = nuevo;
fondo = nuevo;
}
else
{
fondo->sig = nuevo;
fondo = nuevo;
}
}
Recordemos que definimos un puntero llamado nuevo, luego creamos el nodo con la función malloc y cargamos los dos atributos, el de información con lo que llega en el parámetro y el puntero con NULL ya que se insertará al final de la lista, es decir no hay otro después de este.
Si la lista está vacía:
En caso de no estar vacía:
Debemos enlazar el puntero sig del último nodo con el nodo recién creado:
fondo->sig=nuevo;
Y por último el puntero externo fondo debe apuntar al nodo apuntado por nuevo:
fondo=nuevo;
Con esto ya tenemos correctamente enlazados los nodos en la lista tipo cola. Recordar que el puntero nuevo desaparece cuando se sale del método insertar, pero el nodo creado no se pierde porque queda enlazado en la lista.
El funcionamiento del método extraer es similar al de la pila:
int extraer()
{
if (!vacia())
{
int informacion = raiz->info;
struct nodo *bor = raiz;
if (raiz == fondo)
{
raiz = NULL;
fondo = NULL;
}
else
{
raiz = raiz->sig;
}
free(bor);
return informacion;
}
else
return -1;
}
Si la lista no está vacía guardamos en una variable local la información del primer nodo (el operador lógico ! invierte el valor devuelto por la función vacía, si retorna un 1 luego el operador ! lo convierte a cero y viceversa y retorna un 1):
int informacion = raiz->info;
Definimos un puntero y lo inicializamos con el primero de la lista:
struct nodo *bor = raiz;
Para saber si hay un solo nodo verificamos si los dos punteros raiz y fondo apuntan a la misma dirección de memoria:
if (raiz == fondo)
{
Luego hacemos:
raiz = NULL;
fondo = NULL;
En caso de haber 2 o más nodos debemos avanzar el puntero raiz al siguiente nodo:
raiz = raiz->sig;
Ya tenemos la lista correctamente enlazada (raiz apunta al primer nodo y fondo continúa apuntando al último nodo)
Finalmente eliminamos el nodo y retornamos la información:
free(bor);
return informacion;
Si la lista tipo cola está vacía retornamos un -1 (que representa que la cola está vacía, no debemos insertar este valor -1 en la lista)
La función liberar es necesaria llamarla cuando no necesite nuestro programa trabajar más con la lista y tiene por objetivo liberar la ram de todos los nodos actuales que tiene la lista tipo cola:
void liberar()
{
struct nodo *reco = raiz;
struct nodo *bor;
while (reco != NULL)
{
bor = reco;
reco = reco->sig;
free(bor);
}
}
En la función main llamamos a las distintas funciones que hemos codificado en un orden lógico:
void main()
{
insertar(5);
insertar(10);
insertar(50);
imprimir();
printf("Extraemos uno de la cola: %i\n", extraer());
imprimir();
liberar();
getch();
return 0;
}