Estructura de datos – Queue (Cola)

En esta entrada quiero platicarles de las Colas (Queue) un tipo de estructura de datos muy utilizada. ¿Pero que es exactamente una colas?, Cuando digo la palabra cola lo mas seguro es que lo primero que se les venga a la mente es una Cola o Fila como cuando vamos al cine y la taquilla esta muy llena o cuando vamos a un evento donde se presentara alguien famoso. Si en tu mente paso un escenario a sí te diré que vas por buen camino.

Una Cola o Queue es una estructura de datos que sigue la Filosofía FIFO del ingles First In – First Out que en español seria “Primero en entrar primero en salir”. Esto quiere decir que el elemento que entre primero a la Cola sera el primero que salga y el último que entre sera el último en salir.

Un escenario común es cuando vamos al banco, Llegamos y lo primero que haces es tomar un turno, inmediatamente nos damos cuenta que ya había 10 personas primero que tú por lo que automáticamente deduces que ellos serán atendidos primero que tú. Si nos damos cuenta en este escenario el primer cliente que llego y solicito un turno sera el que sea atendido primero y tú que llegaste al último seras atendido hasta el final.

Agregar elementos a una cola

Si apreciamos en la figura anterior cuando un nuevo elemento entra en la cola se posiciona siempre al final de la cola a si mismo este sera el ultimo en salir.

Extraer un elementos a una cola

Como podemos apreciar en la Imagen anterior cuando un elemento es retirado de la cola siempre se retira el primero elemento por lo que el primero en entrar sera el primero en salir y después de esto los demas elementos de la cola se recorren.

Colas de prioridad

Este es una variante de la Cola convencional y trabaja muy parecido a la anterior sin embargo esta tiene un característica que la hace única y es que cuando un nuevo elemento entra en la cola no siempre se coloca al final.

Antes de explicar el funcionamiento me gustaría retomar el Escenario del Banco. Comentamos que el cliente que llegaba primero era el primero en ser atendido sin embargo que pasa cuando llega un cliente el cual es un cliente VIP el cual tiene la tarjeta Platino la cual es la mejor tarjeta que maneja el banco y entre sus beneficios es que es colocado hasta delante de la fila (Siempre y cuando no haya otro cliente con la misma tarjeta, ya que sera colocado detrás de este pero adelante de los demas.), Entonces cuando esta persona llega tenemos que garantizar que se atendido primero que el resto de los clientes que no son VIP.

Para resolver este tipo de problemas tenemos las Colas de Prioridad las cuales tiene un mecanismo para determinar la prioridad de cada elemento de la cola, cuando un elemento entra en la cola lo primero que hace es ver que prioridad tiene y luego lo inserta en la posición que le corresponde.

Como podemos apreciar en la imagen anterior un elemento con prioridad 1 es colocado en la cola y es puesto casi hasta a delante, sin embargo al tener prioridad 1 no pudo llegar hasta el principio ya que existía un elemento con mas prioridad(Prioridad 0) en la Cola.

Si nos damos cuenta de esta manera podemos priorizar la forma en que los elementos son colocados en la Cola.

Extraer elementos de una Cola(Queue) de Prioridad

Si prestamos atención la operación de retirar elementos de la Cola es exactamente igual que las colas normales.

Otra de las cosas importantes cuando trabajamos con Colas(Queue) sean de prioridad o no es que existen implementaciones con capacidad ilimitada o dinámica y Colas con capacidad limitada. Esto quiere decir que existen Colas a las cuales les podemos agregar cuantos elementos queramos a la cola, Sin embargo existen otras implementaciones las cuales solo permite un número limitado de elementos por lo que si un nuevo elemento quiere entrar en la cola sera rechazado hasta que por lo menos un elemento salga.

NOTA: En una Cola no es permitido sacar ningún elemento que no sea el primero en la Cola ya que de lo contrario se perdería el sentido de utilizar una cola.

Con esto me despido,  No olvides suscribirte a mi Blog para que seas notificado cuando suba nuevo material, También te pido que si te gusto lo compartas ya que esto me ayudara a crear mas y mejor material.