colas


Colas
En éste capitulo hablaremos de una estructura muy utilizada e importante en el área de la programación, nos referimos a las estructuras de datos tipo Colas.
Por ejemplo cuando mandamos a impresión un documento, éste actúa en forma de cola, es decir; primera en entrar, primera en salir, o por sus siglas en inglés (First in, first out), ya que el primer documento que llega a la "Cola deImpresión", es el primer documento que es impreso.
Pero las colas, no sólo son usadas por las impresoras, sino también en la vida cotidiana tienen otras muchas aplicaciones, por ejemplo el celular, cuando recibimos un mensaje de texto, éste es almacenado en un "lugar" (dentro del chip) que se comporta como cola; otro ejemplo son las colas de tareas en la pc, las colas de prioridades, etc.
Claro,estos ejemplos son muy complejos y exigen que tengamos conocimientos de sistemas operativos (uso y creación), por tanto y para resguardar nuestra salud mental, no vamos a entrar en tanto detalle respecto a las aplicaciones complejas de las colas, sin embargo trataremos algunas abstracciones que nos ayudarán a comprender el funcionamiento de ésta estructura.
Concepto de Cola
Una cola, es unaestructura en la cual se almacenan elementos (en orden de llegada), es decir que, se ingresan los elementos por la parte final de la estructura y se eliminan (o se sirven) por la parte del frente.

Como puede observarse, ésta estructura cuenta con dos apuntadores, uno que apunta al último elemento y otro que apunta hacia el primer elemento (o el elemento del frente).
Se debe tener en cuenta que,una cola, almacena los datos en ella, manteniendo cierto orden, ya que sus elementos se añaden por el final de la cola y se extraen o se eliminan por la parte de frente.
El lector dispensará el por que la insistencia de ello, pero cuando uno inicia este estudio, al momento de programar, se confunde fácilmente, por que las sentencias de las funciones son muy parecidas a la de una pila, y en algunasocasiones me pasaba que empezaba programando una cola, pero terminaba funcionando como pila.
Las operaciones con las colas son:
-insert (q, x) Inserta el elemento x en la parte posterior de la cola q
-remove(q) Suprime el elemento delantero de la cola q
-empty(q) Retorna True o false, si la cola tiene elementos o no.
Las colas pueden implementarse, al igual que las pilas, mediante dosformas:
Arrays
Memoria Dinámica
Tipo Cola Implementado como Arreglo

La figura de arriba, muestra la forma de implementar una cola, como arreglo, en la que cada casilla, representa una estructura compuesta por el tipo de dato a guardar (o bien otra estructura).
Las variables q.rear y q.front, se van modificando cada vez que añadimos o eliminamos datos de nuestra cola.
Para determinar lacantidad de elementos en cualquier momento es:
Cant=q.rear-q.front+1
Ahora vemos un ejemplo del funcionamiento de las colas, implementadas como arreglos:
Supongamos que en una cola vamos a almacenar elementos de tipo carácter.
Insert(&q, ‘A’);

q.rear=0, q.front=0
insert (&q, ‘B’)

q.rear=1
q.front=0
insert (&q, ‘C’);

q.rear=2
q.front=0
remove(&q);

q.rear=2
q.front=1
remove(&q);q.rear=2
q.front=2
insert(&q, ‘D’);
 
 
C
D
 
0 1 2 3 4
q.rear=3
q.front=2
insert(&q, ‘E’);

q.rear=4
q.front=2
Como se puede ver, al manejar una cola en forma de arreglo lineal, resulta complicado y poco eficiente, por que al eliminar elementos quedan nodosvacíos y cuando se llega al último elemento de la cola, aparecerá un mensaje de error, (o al menos debería aparecer), que indique que ya no hay más espacios, sin embargo, eso sería una total mentira, ya que tenemos elementos sin utilizar; una solución para ello podría ser que cada vez que se eliminen un elemento mover todos los datos hacia la izquierda, pero, te imaginas la cantidad de código...