Estructura de datos – Queue (Cola)

Pila StackEn 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

Estructura de datos - Cola (Queue)
Fig.1: Muestra como un elemento es agregado a la cola(Izquierda) y como queda la cola luego de que el nuevo elemento entra en la cola(Derecha).

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

Estructura de datos cola - Retirar
Fig.2: Muestra como un elemento es retirado de la cola(Izquierda) y como queda la cola después de retirar el elemento(Derecha)

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.

 

ColaPrioridadIn
Fig.3: Muestra como un elemento entra en la Cola(Izquierda) y basado en su prioridad(0 es la prioridad máxima) es colocado en la cola(Derecha).

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

ColaPrioridadOut
Fig.4: En la siguiente imagen podemos apreciar como el elementos con prioridad mas alta es sacado de la cola primero(Izquierda) y como queda la Cola una vez que el elemento es retirado.

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.

Cola Queue
Fig.5: En esta figuro se aprecia que el nuevo elemento que intenta entrar a la cola es rechazado debido a que la Cola ya se encuentra llena en su totalidad.

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.

 

Artículos sugeridos

Si te gusto este Post te sugiero que veas estos dos Post en los cuales las Colas juegan un papel muy importante:
Java Message Service (JMS)
JMS en las integraciones

Otras estructuras de datos:
Pilas (stack)
Árboles (tree)

 

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.

Artículos relacionados

Pila (Stack) En días pasados hablamos acerca de las Colas o Queue las cuales siguen la filosofía FIFO (First In - First Out) o Primero en entrar - Primero en salir...
Estructuras de datos – Listas ligadas Sin duda una de las partes mas emocionantes cuando programamos es la parte de la algoritmia donde tenemos que usar la mente para resolver problemas qu...
Estructura de datos – Árboles Los Árboles son las estructuras de datos mas utilizadas, pero también una de las mas complejas, Los Árboles se caracterizan por almacenar sus nodos e...

Oscar Blancarte

Ideológico, Innovador y emprendedor, Padre, Tecnólogo y Autor, amante de la ciencia y la tecnología en todos sus colores y sabores. Arquitecto de software & Full Stack Developer con experiencia en la industria del desarrollo de software y la consultoría. Amante de la programación y el Ajedrez.

4 comentarios en “Estructura de datos – Queue (Cola)

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *