COLA CIRCULAR DS - TUTORIAL DS

¿Por qué se introdujo el concepto de cola circular?

Había una limitación en la implementación de la matriz de

Como podemos ver en la imagen de arriba, la parte trasera está en la última posición de la cola y el frente apunta a algún lugar en lugar de 0.^thposición. En la matriz anterior, sólo hay dos elementos y otras tres posiciones están vacías. La retaguardia está en la última posición de la cola; Si intentamos insertar el elemento, mostrará que no hay espacios vacíos en la cola. Existe una solución para evitar ese desperdicio de espacio en la memoria desplazando ambos elementos a la izquierda y ajustando la parte delantera y trasera en consecuencia. No es un enfoque prácticamente bueno porque cambiar todos los elementos consumirá mucho tiempo. El enfoque eficaz para evitar el desperdicio de memoria es utilizar la estructura de datos de cola circular.

¿Qué es una cola circular?

Una cola circular es similar a una cola lineal, ya que también se basa en el principio FIFO (primero en entrar, primero en salir), excepto que la última posición está conectada a la primera posición en una cola circular que forma un círculo. También se le conoce como Búfer de anillo .

Operaciones en cola circular

Las siguientes son las operaciones que se pueden realizar en una cola circular:

Frente:Se utiliza para obtener el elemento frontal de la cola.Trasero:Se utiliza para obtener el elemento trasero de la cola.enCola(valor):Esta función se utiliza para insertar el nuevo valor en la cola. El nuevo elemento siempre se inserta por la parte trasera.deCola():Esta función elimina un elemento de la cola. La eliminación de una cola siempre se realiza desde el principio.

Aplicaciones de la cola circular

La cola circular se puede utilizar en los siguientes escenarios:

Gestión de la memoria:La cola circular proporciona gestión de memoria. Como ya hemos visto, en la cola lineal, la memoria no se gestiona de manera muy eficiente. Pero en el caso de una cola circular, la memoria se gestiona de manera eficiente colocando los elementos en una ubicación que no se utiliza.Programación de CPU:El sistema operativo también utiliza la cola circular para insertar los procesos y luego ejecutarlos.Sistema de trafico:En un sistema de tráfico controlado por computadora, el semáforo es uno de los mejores ejemplos de cola circular. Cada luz del semáforo se ENCIENDE una por una después de cada intervalo de tiempo. Como si la luz roja se ENCIENDA durante un minuto, luego la luz amarilla durante un minuto y luego la luz verde. Después de la luz verde, la luz roja se ENCIENDE.

Operación de puesta en cola

Los pasos de la operación de puesta en cola se detallan a continuación:

Primero, comprobaremos si la cola está llena o no.
Inicialmente, la parte delantera y trasera están configuradas en -1. Cuando insertamos el primer elemento en una cola, tanto la parte delantera como la trasera se establecen en 0.
Cuando insertamos un nuevo elemento, la parte trasera se incrementa, es decir, trasero=trasero+1 .

Escenarios para insertar un elemento

Hay dos escenarios en los que la cola no está llena:

mod(tamaño máximo)

Hay dos casos en los que el elemento no se puede insertar:

Cuando frente ==0 && trasero = max-1 , lo que significa que el frente está en la primera posición de la cola y la parte trasera está en la última posición de la cola.
delantero== trasero + 1;

Algoritmo para insertar un elemento en una cola circular

Paso 1: SI (TRASERO+1)%MAX = DELANTERO
Escribe 'DESBORDAMIENTO'
Ir al paso 4
[Fin DE SI]

Paso 2: SI DELANTERO = -1 y TRASERO = -1
AJUSTAR DELANTERO = TRASERO = 0
¡OTRO SI TRASERO = MAX - 1 y DELANTERO! = 0
ESTABLECER TRASERO = 0
DEMÁS
AJUSTAR TRASERO = (TRASERO + 1) % MAX
[FIN DE SI]

Paso 3: ESTABLECER COLA[TRASERO] = VAL

Etapa 4: SALIDA

Operación de salida de cola

Los pasos de la operación de eliminación de la cola se detallan a continuación:

Primero, verificamos si la cola está vacía o no. Si la cola está vacía, no podemos realizar la operación de sacar de la cola.
Cuando se elimina el elemento, el valor de front disminuye en 1.
Si solo queda un elemento que desea eliminar, entonces la parte delantera y trasera se restablecen a -1.

Algoritmo para eliminar un elemento de la cola circular

escribe json en el archivo python

Paso 1: SI DELANTE = -1
Escribe 'FLUJO SUPERIOR'
Ir al paso 4
[FIN de SI]

Paso 2: ESTABLECER VAL = COLA[FRONTAL]

Paso 3: SI DELANTERO = TRASERO
AJUSTAR DELANTERO = TRASERO = -1
DEMÁS
SI DELANTERO = MAX -1
CONFIGURAR DELANTE = 0
DEMÁS
CONFIGURAR DELANTE = DELANTERO + 1
[FIN de SI]
[FIN DE SI]

Etapa 4: SALIDA

Comprendamos la operación de poner y quitar la cola a través de la representación esquemática.

Implementación de cola circular usando Array.

 #include # define max 6 int queue[max]; // array declaration int front=-1; int rear=-1; // function to insert an element in a circular queue void enqueue(int element) { if(front==-1 &amp;&amp; rear==-1) // condition to check queue is empty { front=0; rear=0; queue[rear]=element; } else if((rear+1)%max==front) // condition to check queue is full { printf(&apos;Queue is overflow..&apos;); } else { rear=(rear+1)%max; // rear is incremented queue[rear]=element; // assigning a value to the queue at the rear position. } } // function to delete the element from the queue int dequeue() { if((front==-1) &amp;&amp; (rear==-1)) // condition to check queue is empty { printf(&apos;
Queue is underflow..&apos;); } else if(front==rear) { printf(&apos;
The dequeued element is %d&apos;, queue[front]); front=-1; rear=-1; } else { printf(&apos;
The dequeued element is %d&apos;, queue[front]); front=(front+1)%max; } } // function to display the elements of a queue void display() { int i=front; if(front==-1 &amp;&amp; rear==-1) { printf(&apos;
 Queue is empty..&apos;); } else { printf(&apos;
Elements in a Queue are :&apos;); while(i<=rear) { printf('%d,', queue[i]); i="(i+1)%max;" } int main() choice="1,x;" variables declaration while(choice<4 && choice!="0)" while loop printf('
 press 1: insert an element'); printf('
press 2: delete 3: display the printf('
enter your choice'); scanf('%d', &choice); switch(choice) case printf('enter element which is to be inserted'); &x); enqueue(x); break; dequeue(); display(); }} return 0; < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/14/circular-queue-10.webp" alt="Circular Queue"> <h3>Implementation of circular queue using linked list</h3> <p>As we know that linked list is a linear data structure that stores two parts, i.e., data part and the address part where address part contains the address of the next node. Here, linked list is used to implement the circular queue; therefore, the linked list follows the properties of the Queue. When we are implementing the circular queue using linked list then both the <strong> <em>enqueue and dequeue</em> </strong> operations take <strong> <em>O(1)</em> </strong> time.</p> <pre> #include // Declaration of struct type node struct node { int data; struct node *next; }; struct node *front=-1; struct node *rear=-1; // function to insert the element in the Queue void enqueue(int x) { struct node *newnode; // declaration of pointer of struct node type. newnode=(struct node *)malloc(sizeof(struct node)); // allocating the memory to the newnode newnode-&gt;data=x; newnode-&gt;next=0; if(rear==-1) // checking whether the Queue is empty or not. { front=rear=newnode; rear-&gt;next=front; } else { rear-&gt;next=newnode; rear=newnode; rear-&gt;next=front; } } // function to delete the element from the queue void dequeue() { struct node *temp; // declaration of pointer of node type temp=front; if((front==-1)&amp;&amp;(rear==-1)) // checking whether the queue is empty or not { printf(&apos;
Queue is empty&apos;); } else if(front==rear) // checking whether the single element is left in the queue { front=rear=-1; free(temp); } else { front=front-&gt;next; rear-&gt;next=front; free(temp); } } // function to get the front of the queue int peek() { if((front==-1) &amp;&amp;(rear==-1)) { printf(&apos;
Queue is empty&apos;); } else { printf(&apos;
The front element is %d&apos;, front-&gt;data); } } // function to display all the elements of the queue void display() { struct node *temp; temp=front; printf(&apos;
 The elements in a Queue are : &apos;); if((front==-1) &amp;&amp; (rear==-1)) { printf(&apos;Queue is empty&apos;); } else { while(temp-&gt;next!=front) { printf(&apos;%d,&apos;, temp-&gt;data); temp=temp-&gt;next; } printf(&apos;%d&apos;, temp-&gt;data); } } void main() { enqueue(34); enqueue(10); enqueue(23); display(); dequeue(); peek(); } </pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/14/circular-queue-11.webp" alt="Circular Queue"> <hr></=rear)>

Producción:

TechCodeview

Cola circular