Hvorfor ble konseptet med sirkulær kø introdusert?

Det var én begrensning i array-implementeringen av

Som vi kan se i bildet ovenfor, er baksiden i den siste posisjonen i køen og fronten peker et sted i stedet for 0^thposisjon. I arrayen ovenfor er det bare to elementer og tre andre posisjoner er tomme. Den bakre er i den siste posisjonen i køen; hvis vi prøver å sette inn elementet, vil det vise at det ikke er noen tomme mellomrom i køen. Det er én løsning for å unngå slik sløsing med minneplass ved å flytte begge elementene til venstre og justere for- og bakenden tilsvarende. Det er ikke en praktisk god tilnærming fordi å skifte alle elementene vil ta mye tid. Den effektive tilnærmingen for å unngå sløsing med minnet er å bruke den sirkulære kødatastrukturen.

Hva er en sirkulær kø?

En sirkulær kø ligner på en lineær kø da den også er basert på FIFO-prinsippet (First In First Out) bortsett fra at den siste posisjonen er koblet til den første posisjonen i en sirkulær kø som danner en sirkel. Det er også kjent som en Ringbuffer .

listenode

ls kommandoer linux

Trinn 4: EXIT

Drift av kø

Trinnene for fjerning av kø er gitt nedenfor:

• Først sjekker vi om køen er tom eller ikke. Hvis køen er tom, kan vi ikke utføre dekøoperasjonen.
• Når elementet slettes, reduseres verdien av front med 1.
• Hvis det kun er ett element igjen som skal slettes, tilbakestilles front og bak til -1.

Algoritme for å slette et element fra den sirkulære køen

Trinn 1: HVIS FRONT = -1
Skriv 'UNDERFLØY'
Gå til trinn 4
[END of IF]

Steg 2: SET VALUE = KØ[FRONT]

Trinn 3: HVIS FRONT = BAK
SET FRONT = BAK = -1
ELLERS
HVIS FRONT = MAKS -1
SET FRONT = 0
ELLERS
SET FRONT = FRONT + 1
[END of IF]
[SLUT PÅ HVIS]

Trinn 4: EXIT

La oss forstå enqueue og dequeue-operasjonen gjennom den skjematiske representasjonen.

Implementering av sirkulær kø ved bruk av 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 && 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('Queue is overflow..'); } 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) && (rear==-1)) // condition to check queue is empty { printf('
Queue is underflow..'); } else if(front==rear) { printf('
The dequeued element is %d', queue[front]); front=-1; rear=-1; } else { printf('
The dequeued element is %d', queue[front]); front=(front+1)%max; } } // function to display the elements of a queue void display() { int i=front; if(front==-1 && rear==-1) { printf('
 Queue is empty..'); } else { printf('
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)>

Produksjon: