Diferentes tipos de colas y sus aplicaciones

Una cola es una estructura lineal que sigue un orden particular en el que se realizan las operaciones. El orden es Primero en entrar, primero en salir (FIFO). Un buen ejemplo de una cola es cualquier cola de consumidores de un recurso donde se atiende primero al consumidor que llegó primero. En este artículo, se analizan los diferentes tipos de colas. 

Tipos de colas:

Hay cinco tipos diferentes de colas que se utilizan en diferentes escenarios. Están:

1. Cola restringida de entrada (esta es una cola simple)
2. Cola restringida de salida (esta también es una cola simple)
3. cola circular
4. Cola de doble terminación (Deque)
5. cola de prioridad
   • Cola de prioridad ascendente
   • Cola de prioridad descendente

1. Cola circular : la cola circular es una estructura de datos lineal en la que las operaciones se realizan según el principio FIFO (primero en entrar, primero en salir) y la última posición se conecta de nuevo a la primera posición para formar un círculo. También se le llama ‘Ring Buffer’ . Esta cola se utiliza principalmente en los siguientes casos:

1. Gestión de memoria: las ubicaciones de memoria no utilizadas en el caso de colas ordinarias se pueden utilizar en colas circulares.
2. Sistema de tráfico: en un sistema de tráfico controlado por computadora, se utilizan colas circulares para encender los semáforos uno por uno repetidamente según el tiempo establecido.
3. Programación de CPU: los sistemas operativos a menudo mantienen una cola de procesos que están listos para ejecutarse o que están esperando que ocurra un evento en particular.

2. Cola restringida de entrada: en este tipo de cola, la entrada se puede tomar de un solo lado (posterior) y la eliminación de elementos se puede realizar desde ambos lados (frontal y posterior). Este tipo de cola no sigue FIFO (primero en entrar, primero en salir). Esta cola se utiliza en casos en los que el consumo de datos debe estar en orden FIFO, pero si es necesario eliminar los datos insertados recientemente por algún motivo y uno de esos casos puede ser datos irrelevantes, problemas de rendimiento, etc. 

3. Cola restringida de salida: en este tipo de Cola, la entrada se puede tomar de ambos lados (posterior y frontal) y la eliminación del elemento se puede realizar de un solo lado (frontal). Esta cola se utiliza en el caso de que las entradas tengan algún orden de prioridad para ejecutarse y la entrada se puede colocar incluso en primer lugar para que se ejecute primero. 

4. Cola de doble extremo : la cola de doble extremo también es una estructura de datos de cola en la que las operaciones de inserción y eliminación se realizan en ambos extremos (frontal y posterior). Eso significa que podemos insertar tanto en la posición delantera como trasera y podemos eliminar tanto en la posición delantera como trasera. Dado que Deque admite operaciones de pila y cola, se puede usar como ambas. La estructura de datos de Deque admite rotaciones en el sentido de las agujas del reloj y en el sentido contrario a las agujas del reloj en tiempo O(1), lo que puede ser útil en determinadas aplicaciones. Además, los problemas en los que es necesario eliminar o agregar elementos en ambos extremos se pueden resolver de manera eficiente con Deque.

5. Cola de prioridad : una cola de prioridad es un tipo especial de cola en la que cada elemento está asociado con una prioridad y se sirve de acuerdo con su prioridad. Hay dos tipos de colas de prioridad. Están:

1. Cola de prioridad ascendente: el elemento se puede insertar arbitrariamente, pero solo se puede eliminar el elemento más pequeño. Por ejemplo, suponga que hay una array que tiene los elementos 4, 2, 8 en el mismo orden. Entonces, al insertar los elementos, la inserción será en la misma secuencia pero al eliminar, el orden será 2, 4, 8.
2. Cola de prioridad descendente: el elemento se puede insertar arbitrariamente, pero solo el elemento más grande se puede eliminar primero de la cola dada. Por ejemplo, suponga que hay una array que tiene los elementos 4, 2, 8 en el mismo orden. Entonces, al insertar los elementos, la inserción será en la misma secuencia pero al eliminar, el orden será 8, 4, 2.

Aplicaciones de una cola:

La cola se usa cuando las cosas no tienen que procesarse de inmediato, pero deben procesarse en el orden Primero en entrar, primero en salir, como la Búsqueda en anchura . Esta propiedad de Queue también la hace útil en los siguientes tipos de escenarios.

1. Cuando un recurso se comparte entre múltiples consumidores. Los ejemplos incluyen la programación de la CPU , la programación del disco .
2. Cuando los datos se transfieren de forma asincrónica (los datos no se reciben necesariamente a la misma velocidad que se envían) entre dos procesos. Los ejemplos incluyen IO Buffers, pipes , file IO, etc.