La cola se puede describir como una estructura de datos lineal no primitiva que sigue el orden FIFO en el que los elementos de datos se insertan desde un extremo (parte posterior) y se eliminan desde el otro extremo (extremo frontal). Las otras variaciones de la cola son la cola circular, la cola de doble finalización y la cola de prioridad.
Gráfica comparativa
| Bases para la comparación | Cola lineal | Cola circular |
|---|---|---|
| BASIC | Organiza los elementos de datos e instrucciones en orden secuencial uno tras otro. | Organiza los datos en el patrón circular donde el último elemento está conectado al primer elemento. |
| Orden de ejecución de tareas | Las tareas se ejecutan en el orden en que se colocaron antes (FIFO). | El orden de ejecución de una tarea puede cambiar. |
| Inserción y eliminación | El nuevo elemento se agrega desde la parte trasera y se quita desde la parte delantera. | La inserción y eliminación se puede hacer en cualquier posición. |
| Actuación | Ineficiente | Funciona mejor que la cola lineal. |
Definición de la cola lineal
Una cola lineal es racionalmente una lista de primero en entrar, primero en salir . Se llama así lineal porque se asemeja a una línea recta donde los elementos se colocan uno tras otro. Contiene una colección homogénea de los elementos en los que los nuevos elementos se agregan en un extremo y se eliminan de otro extremo. El concepto de la cola se puede entender mediante el ejemplo de una cola de la audiencia que espera fuera del mostrador de boletos para obtener el boleto de teatro. En esta cola, la persona se une al final de la cola para tomar el boleto y el boleto se emite en la parte delantera de la cola.
Hay varias operaciones realizadas en la cola.
- En primer lugar, la cola se inicializa a cero (es decir, está vacía).
- Determine si la cola está vacía o no.
- Determine si la cola está llena o no.
- Inserción del nuevo elemento desde la parte trasera (Encolar).
- Borrado del elemento desde el extremo frontal (Dequeue).
La cola se puede implementar de dos maneras.
- Estáticamente (utilizando matrices)
- Dinámicamente (utilizando punteros)
La limitación de la cola lineal es que crea un escenario en el que no se puede agregar ningún elemento nuevo a la cola, incluso si la cola contiene los espacios vacíos. Esta situación anterior se ilustra en la figura a continuación. Aquí, la parte trasera apunta al último índice, mientras que todas las casillas aún están vacías, no se puede agregar ningún elemento nuevo.
Definición de la cola circular
Una cola circular es una variante de la cola lineal que supera la limitación de la cola lineal. En la cola circular, el nuevo elemento se agrega a la primera posición de la cola si el último está ocupado y hay espacio disponible. Cuando se trata de una cola lineal, la inserción se puede realizar solo desde la parte trasera y la eliminación desde la parte delantera. En una cola completa después de realizar una serie de eliminaciones sucesivas en la cola, surge una situación en la que ya no se puede agregar ningún elemento nuevo, incluso si el espacio disponible porque la condición de desbordamiento (Rear = max - 1) aún existe.
La cola circular conecta los dos extremos a través de un puntero donde el primer elemento viene después del último elemento. También realiza un seguimiento de la parte delantera y trasera mediante la implementación de una lógica adicional para que pueda rastrear los elementos que se insertarán y eliminarán. Con esto, la cola circular no genera la condición de desbordamiento hasta que la cola esté llena en real.
Algunas condiciones seguidas por la cola circular:
- Frente debe apuntar al primer elemento.
- La cola estará vacía si Front = Rear.
- Cuando se agrega un nuevo elemento, la cola se incrementa en el valor uno (Posterior = Posterior + 1).
- Cuando se elimina un elemento de la cola, el frente se incrementa en uno (Frente = Frente + 1).
Diferencias clave entre la cola lineal y la circular
- La cola lineal es una lista ordenada en la que los elementos de datos se organizan en orden secuencial. Por el contrario, la cola circular almacena los datos de forma circular.
- La cola lineal sigue el orden FIFO para ejecutar la tarea (el elemento agregado en la primera posición se eliminará en la primera posición). A la inversa, en la cola circular, el orden de las operaciones realizadas en un elemento puede cambiar.
- La inserción y eliminación de los elementos se fija en la cola lineal, es decir, la adición desde la parte posterior y la eliminación desde la parte frontal. Por otro lado, la cola circular es capaz de insertar y eliminar el elemento desde cualquier punto hasta que esté desocupado.
- La cola lineal desperdicia el espacio de la memoria, mientras que la cola circular hace que el espacio sea eficiente.
Implementación de la cola lineal.
El algoritmo dado a continuación ilustra la adición de elementos en una cola:
La cola necesita tres variables de datos, incluida una matriz para almacenar la cola y otra para almacenar la posición inicial delantera y trasera que es -1.
inserte (elemento, cola, n, parte trasera) {si (parte trasera == n) luego imprima "cola de desbordamiento"; else {trasero = trasero + 1; queue [rear] = item; }} El algoritmo dado a continuación ilustra la eliminación de elementos en una cola:
delete_circular (artículo, cola, parte trasera, parte delantera) {if (parte trasera == parte delantera) luego imprima "cola de flujo insuficiente"; else {front = front + 1; item = queue [front]; }} Implementación de la cola circular.
Un algoritmo para interpretar la adición del elemento en la cola circular:
insert_circular (artículo, cola, trasero, delantero) {trasero = (trasero + 1) mod n; if (front == rear) luego imprima "la cola está llena"; else {queue [rear] = item; }} El algoritmo explica la eliminación del elemento en la cola circular:
delete_circular (item, queue, rear, front) {if (front == rear) luego print ("la cola está vacía"); else {front = front + 1; item = queue [front]; }} Conclusión
La cola lineal es ineficiente en ciertos casos donde se requiere que los elementos se desplacen a los espacios vacantes para realizar la operación de inserción. Esa es la razón por la que tiende a desperdiciar el espacio de almacenamiento mientras que la cola circular hace un uso adecuado del espacio de almacenamiento, ya que los elementos se agregan en cualquier posición si existe un espacio vacío.
