CUA CIRCULAR DE DS - TUTORIAL DS

Per què es va introduir el concepte de cua circular?

Hi havia una limitació en la implementació de la matriu

Com podem veure a la imatge de dalt, la part posterior es troba a l'última posició de la cua i la part davantera apunta a algun lloc en lloc del 0^thposició. A la matriu anterior, només hi ha dos elements i altres tres posicions estan buides. La part posterior es troba a l'última posició de la Cua; si intentem inserir l'element, mostrarà que no hi ha espais buits a la cua. Hi ha una solució per evitar aquest malbaratament d'espai de memòria desplaçant els dos elements de l'esquerra i ajustant la part davantera i posterior en conseqüència. No és un enfocament pràcticament bo perquè canviar tots els elements consumirà molt de temps. L'enfocament eficient per evitar el malbaratament de la memòria és utilitzar l'estructura de dades de la cua circular.

Què és una cua circular?

Una cua circular és similar a una cua lineal, ja que també es basa en el principi FIFO (First In First Out), excepte que l'última posició està connectada a la primera posició d'una cua circular que forma un cercle. També es coneix com a Buffer d'anell .

Operacions a la cua circular

Les següents són les operacions que es poden realitzar en una cua circular:

Davant:S'utilitza per obtenir l'element frontal de la cua.posterior:S'utilitza per obtenir l'element posterior de la cua.enQueue(valor):Aquesta funció s'utilitza per inserir el valor nou a la cua. El nou element s'insereix sempre des de la part posterior.deQueue():Aquesta funció elimina un element de la cua. L'eliminació d'una cua sempre es fa des de la portada.

Aplicacions de la cua circular

La cua circular es pot utilitzar en els escenaris següents:

Gestió de la memòria:La cua circular proporciona gestió de memòria. Com ja hem vist que a la cua lineal, la memòria no es gestiona de manera molt eficient. Però en el cas d'una cua circular, la memòria es gestiona de manera eficient col·locant els elements en una ubicació que no s'utilitza.Programació de la CPU:El sistema operatiu també utilitza la cua circular per inserir els processos i després executar-los.Sistema de trànsit:En un sistema de control de trànsit per ordinador, el semàfor és un dels millors exemples de la cua circular. Cada semàfor s'encén un per un després de cada interval de temps. Com si la llum vermella s'encengui durant un minut, la llum groga durant un minut i després la llum verda. Després de la llum verda, la llum vermella s'encendrà.

Operació de cua

Els passos del funcionament de la cua es detallen a continuació:

Primer, comprovarem si la cua està plena o no.
Inicialment, la part davantera i posterior s'estableixen a -1. Quan inserim el primer element en una cua, la part davantera i posterior es posen a 0.
Quan inserim un nou element, la part posterior s'incrementa, és a dir, posterior=darrera+1 .

Escenaris per inserir un element

Hi ha dos escenaris en què la cua no està plena:

mod (mida màxima)

Hi ha dos casos en què l'element no es pot inserir:

Quan davant ==0 && posterior = max-1 , que significa que la part davantera es troba a la primera posició de la cua i la part posterior es troba a l'última posició de la cua.
davanter== darrere + 1;

Algorisme per inserir un element en una cua circular

Pas 1: IF (DARRERA+1)%MAX = DAVANT
Escriu 'DESBORRAMENT'
Passeu al pas 4
[Fi de SI]

Pas 2: SI FRONT = -1 i POSTERIOR = -1
CONFIGURAR FRONT = DARRERE = 0
ALTRES SI POSTERIOR = MAX - 1 i FRONT ! = 0
SET POSTERIOR = 0
ALTRES
SET POSTERIOR = (DARRERA + 1) % MÀX
[FI DE SI]

Pas 3: SET QUEUE[REAR] = VAL

Pas 4: SORTIR

Operació de retirada de la cua

Els passos de l'operació de descua es donen a continuació:

Primer, comprovem si la cua està buida o no. Si la cua està buida, no podem realitzar l'operació de descua.
Quan s'elimina l'element, el valor de front es redueix en 1.
Si només queda un element que s'ha de suprimir, la part davantera i posterior es restabliran a -1.

Algorisme per eliminar un element de la cua circular

aes vs des

Pas 1: SI FRONT = -1
Escriu 'SUBFLOW'
Passeu al pas 4
[FI de SI]

Pas 2: SET VAL = QUEUE[FRONT]

Pas 3: SI FRONT = POSTERIOR
SET DAVANT = POSTERIOR = -1
ALTRES
SI FRONT = MAX -1
SET FRONT = 0
ALTRES
SET FRONT = FRONT + 1
[FI de SI]
[FI DE SI]

Pas 4: SORTIR

Entendrem l'operació d'engegada i eliminació de cua mitjançant la representació esquemàtica.

Implementació de la cua circular mitjançant 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)>

Sortida:

TechCodeview

Cua circular