Es una estructra de tipo FIFO (First In First Out), es decir: primero en entrar, primero en salir.
Las colas se utilizan en sistemas informáticos,transportes, operaciones de investigación (entre otros),dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases en forma de listas enlazadas.
Operaciones básicas con colas:
Las operaciones con colas son muy sencillas, prácticamente no hay casos especiales, salvo que la cola esté vacía, nos encontramos ante una estructura con muy pocas operaciones disponibles. Las colas sólo permiten añadir y leer elementos:
Añadir: Inserta un elemento al final de la cola.
Leer: Lee y elimina un elemento del principio de la cola.
Añadir un elemento en general
Para generalizar el caso anterior, sólo necesitamos añadir una operación:
Hacemos que nodo->siguiente apunte a NULL.
Si ultimo no es NULL, hacemos que ultimo->siguiente apunte a nodo.
Y actualizamos ultimo, haciendo que apunte a nodo.
Si primero es NULL, significa que la cola estaba vacía, así que haremos que primero apunte también a nodo.
Añadir un elemento en cola no vacía
partiremos de un nodo a insertar, con un puntero que apunte a él, y de una cola, en este caso, al no estar vacía, los punteros primero y ultimo no serán nulos:
El proceso sigue siendo muy sencillo:
- Hacemos que nodo->siguiente apunte a NULL.
- Después que ultimo->siguiente apunte a nodo.
- Y actualizamos ultimo, haciendo que apunte a nodo.
Leer un elemento, implica eliminarlo
existen dos casos, que la cola tenga un solo elemento o que tenga más de uno.
1. Hacemos que nodo apunte al primer elemento de la pila, es decir a primero.
2. Asignamos a primero la dirección del segundo nodo de la pila: primero->siguiente.
3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de lectura en colas implican también borrar.
4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.
5. Si primero es NULL, hacemos que ultimo también apunte a NULL, ya que la lectura ha dejado la cola vacía.
Leer un elemento en una cola con más de un elemento:
Usaremos un puntero a un nodo auxiliar:
1. Hacemos que nodo apunte al primer elemento de la cola, es decir a primero.
2. Asignamos a primero la dirección del segundo nodo de la pila: primero->siguiente.
3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de lectura en colas implican también borrar.
4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.
Leer un elemento en un solo elemento
También necesitamos un puntero a un nodo auxiliar:
1. Hacemos que nodo apunte al primer elemento de la pila, es decir a primero.
2. Asignamos NULL a primero, que es la dirección del segundo nodo teórico de la cola: primero->siguiente.
3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de lectura en colas implican también borrar.
4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.
5. Hacemos que ultimo apunte a NULL, ya que la lectura ha dejado la cola vacía.
Video Colas
