Colas en lenguaje c

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 sehacen 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. Enfunció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 LISTAS3. 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 fincada 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á unmanejo 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-> (n) ->siguiente->elemento>, tal que c->siguiente->siguiente-> (n) ->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 **)...