Sdsd

Tema 4 Colas

1.- Definición

Una cola es una estructura lineal en la que sólo se pueden insertar nodos en uno de los extremos de la cola 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 FirstOut), el primero en entrar es el primero en salir.
El ejemplo 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.
3.- Representación grafica
COLA[ n ]
| | | | | |

Penúltimo(frente)ultimo (final)
4.- Estado de una Cola
Generalmente una pila tiene dos estados a considerar:
Cola vacia cuando penultimo = final
Cola llena cuando penultimo =1 y ultimo = n
5.- Declaracion de una pila estática.
Se puede definir y declarar una cola utilizando un vector o array unidimensional, pero esta vez con dos indices, ya que necesitamos realizar las operaciones por ambos extremosPILA[ 5 ]
| | | | | |

Penúltimo (frente) ultimo (final)

6.- Operaciones básicas con colas

Las colas tienen un conjunto de operaciones muy limitado, sólo permiten las operaciones de meter, insertar, adicionar ("push") y sacar, imprimir, mostrar, eliminar ("pop":)
6.1.- Inserción
Consiste en añadir unelemento por un extremo denominado final, cualquier elemento de la cola siempre se inserta por un extremo y se saca por el otro extremo.

6.2.- Algoritmo para insertar un elemento a la cola
Primeramente se debe crear un vector que será la cola, se debe definir el tipo de datos que almacenara esta cola, que puede ser enteros, de caracter , reales y otros
void insertar (int dato)
{ if(ultimo>MAX)
{ printf ("COLA LLENA\n");
return; }
cola[ultimo]=dato;
ultimo++; }
Programa ejemplo de implementación de una cola que almacena numeros

6.3.- Eliminación en una cola
Consiste en sacar un elemento de la cola, la salida o impresión de los elementos de la cola siempre se realiza por el otro extremo denominado penultimo, ya que el primero en entrar es el primero ensalir.
Algoritmo de eliminacion
/*int quitar( )
{ if(ultimo ==penultimo)
{ printf("PILA VACIA\n");
return 0;
}
penultimo++;
return (cola[penultimo-1]);
}

7.- Declaraciones e implementación dinámica

El nodo típico para construir colas es :
struct nodo {
int dato;
struct nodo *siguiente;
};
Para implementar dinamicamente, tambien se utiliza unaestructura y punteros.
[pic]
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 dondeinsertemos 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.

3.- Operaciones básicas con colas

Se aplican tres operaciones primitivas auna cola. La operación inserción (añadir), remove (eliminar) y empty (comprobacion de cola).
▪ Añadir: Inserta un elemento al final de la cola.
Eliminar: Lee y elimina un elemento del principio de la cola.
Comprobacion de la cola: si esta llena y esta vacia

Añadir un elemento

1. Hacemos que nodo->siguiente apunte a NULL.
2. Si ultimo no es NULL, hacemos que...