TechCodeview

Waarom werd het concept van de circulaire wachtrij geïntroduceerd?

Er was één beperking bij de array-implementatie van

Zoals we in de bovenstaande afbeelding kunnen zien, bevindt de achterkant zich op de laatste positie van de wachtrij en wijst de voorkant ergens heen in plaats van naar de 0^epositie. In de bovenstaande array zijn er slechts twee elementen en zijn de andere drie posities leeg. De achterkant bevindt zich op de laatste positie van de wachtrij; als we proberen het element in te voegen, zal het laten zien dat er geen lege spaties in de wachtrij zijn. Er is één oplossing om een ​​dergelijke verspilling van geheugenruimte te voorkomen door beide elementen aan de linkerkant te verschuiven en de voor- en achterkant dienovereenkomstig aan te passen. Het is praktisch gezien geen goede aanpak, omdat het verschuiven van alle elementen veel tijd zal kosten. De efficiënte aanpak om verspilling van geheugen te voorkomen is het gebruik van de datastructuur van de circulaire wachtrij.

data structuur

verbindingen in Java

Stap 1: INDIEN VOOR = -1
Schrijf 'ONDERSTROOM'
Ga naar stap 4
[EIND van ALS]

Stap 2: SET VAL = WACHTRIJ[VOOR]

javascript if-instructie

Stap 3: INDIEN VOOR = ACHTER
SET VOOR = ACHTER = -1
ANDERS
ALS VOOR = MAX -1
VOORZET = 0
ANDERS
SET VOOR = VOOR + 1
[EIND van ALS]
[EIND VAN ALS]

Stap 4: UITGANG

Laten we de bewerking van het in de wachtrij plaatsen en uit de wachtrij halen begrijpen via de schematische weergave.

Implementatie van een circulaire wachtrij met behulp van 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)>

Uitgang: