4.2.2.4 Implementación con POO

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;