logo

TechCodeview

Runde Warteschlange

Warum wurde das Konzept der zirkulären Warteschlange eingeführt?

Es gab eine Einschränkung bei der Array-Implementierung von

Wie wir im obigen Bild sehen können, befindet sich die Rückseite an der letzten Position der Warteschlange und die Vorderseite zeigt irgendwohin und nicht auf die 0ThPosition. Im obigen Array gibt es nur zwei Elemente und die anderen drei Positionen sind leer. Der hintere Teil befindet sich an der letzten Position der Warteschlange. Wenn wir versuchen, das Element einzufügen, wird angezeigt, dass in der Warteschlange keine Leerzeichen vorhanden sind. Eine Lösung, um eine solche Verschwendung von Speicherplatz zu vermeiden, besteht darin, beide Elemente nach links zu verschieben und die Vorder- und Rückseite entsprechend anzupassen. Dies ist kein praktisch sinnvoller Ansatz, da das Verschieben aller Elemente viel Zeit in Anspruch nimmt. Der effiziente Ansatz zur Vermeidung von Speicherverschwendung ist die Verwendung der zirkulären Warteschlangendatenstruktur.

Was ist eine kreisförmige Warteschlange?

Eine kreisförmige Warteschlange ähnelt einer linearen Warteschlange, da sie ebenfalls auf dem FIFO-Prinzip (First In First Out) basiert, mit der Ausnahme, dass die letzte Position mit der ersten Position in einer kreisförmigen Warteschlange verbunden ist, die einen Kreis bildet. Es ist auch als bekannt Ringpuffer .

Operationen in der kreisförmigen Warteschlange

Im Folgenden sind die Vorgänge aufgeführt, die für eine kreisförmige Warteschlange ausgeführt werden können:

    Vorderseite:Es wird verwendet, um das vordere Element aus der Warteschlange abzurufen.Hinteren:Es wird verwendet, um das hintere Element aus der Warteschlange abzurufen.enQueue(Wert):Mit dieser Funktion wird der neue Wert in die Warteschlange eingefügt. Das neue Element wird immer von hinten eingefügt.deQueue():Diese Funktion löscht ein Element aus der Warteschlange. Das Löschen in einer Queue erfolgt immer vom Frontend aus.

Anwendungen der kreisförmigen Warteschlange

Die zirkuläre Warteschlange kann in den folgenden Szenarien verwendet werden:

    Speicherverwaltung:Die zirkuläre Warteschlange sorgt für die Speicherverwaltung. Wie wir bereits gesehen haben, wird der Speicher in linearen Warteschlangen nicht sehr effizient verwaltet. Im Falle einer zirkulären Warteschlange wird der Speicher jedoch effizient verwaltet, indem die Elemente an einem ungenutzten Ort platziert werden.CPU-Planung:Das Betriebssystem nutzt die zirkuläre Warteschlange auch, um die Prozesse einzufügen und dann auszuführen.Verkehrssystem:In einem computergesteuerten Verkehrssystem ist die Ampel eines der besten Beispiele für die kreisförmige Warteschlange. Jede Ampel einer Ampel schaltet sich nach jedem Zeitintervall einzeln ein. Als ob das rote Licht eine Minute lang angeht, dann das gelbe Licht eine Minute lang und dann das grüne Licht. Nach grünem Licht geht das rote Licht an.

Enqueue-Vorgang

Die Schritte des Enqueue-Vorgangs sind unten aufgeführt:

  • Zuerst prüfen wir, ob die Warteschlange voll ist oder nicht.
  • Zunächst sind vorne und hinten auf -1 eingestellt. Wenn wir das erste Element in eine Warteschlange einfügen, werden vorne und hinten beide auf 0 gesetzt.
  • Wenn wir ein neues Element einfügen, wird die Rückseite inkrementiert, d. h. hinten=hinten+1 .

Szenarien zum Einfügen eines Elements

Es gibt zwei Szenarien, in denen die Warteschlange nicht voll ist:

    Wenn hinten != max - 1, dann wird die Rückseite auf erhöht mod(maximale Größe) und der neue Wert wird am hinteren Ende der Warteschlange eingefügt.Wenn vorne != 0 und hinten = max - 1, bedeutet dies, dass die Warteschlange nicht voll ist. Setzen Sie dann den Wert von hinten auf 0 und fügen Sie dort das neue Element ein.

Es gibt zwei Fälle, in denen das Element nicht eingefügt werden kann:

  • Wann vorne ==0 && hinten = max-1 , was bedeutet, dass sich vorne an der ersten Position der Warteschlange und hinten an der letzten Position der Warteschlange befindet.
  • vorne== hinten + 1;

Algorithmus zum Einfügen eines Elements in eine kreisförmige Warteschlange

Schritt 1: WENN (HINTEN+1)%MAX = VORNE
Schreiben Sie „ÜBERLAUF“
Gehen Sie zu Schritt 4
[Ende von WENN]

Schritt 2: WENN VORNE = -1 und HINTEN = -1
SET VORNE = HINTEN = 0
ELSE IF REAR = MAX - 1 und FRONT ! = 0
SET HINTEN = 0
ANDERS
SET HINTEN = (HINTEN + 1) % MAX
[ENDE VON WENN]

Schritt 3: SET QUEUE[REAR] = VAL

Schritt 4: AUSFAHRT

Vorgang aus der Warteschlange entfernen

Die Schritte zum Entfernen aus der Warteschlange sind unten aufgeführt:

  • Zuerst prüfen wir, ob die Warteschlange leer ist oder nicht. Wenn die Warteschlange leer ist, können wir den Vorgang zum Entfernen aus der Warteschlange nicht durchführen.
  • Wenn das Element gelöscht wird, wird der Wert von front um 1 verringert.
  • Wenn nur noch ein Element übrig ist, das gelöscht werden soll, werden Vorder- und Rückseite auf -1 zurückgesetzt.

Algorithmus zum Löschen eines Elements aus der zirkulären Warteschlange

Schritt 1: WENN FRONT = -1
Schreiben Sie „UNDERFLOW“
Gehen Sie zu Schritt 4
[ENDE von IF]

Schritt 2: SET VAL = QUEUE[FRONT]

Schritt 3: WENN VORNE = HINTEN
SET VORNE = HINTEN = -1
ANDERS
WENN VORNE = MAX -1
VORNE SETZEN = 0
ANDERS
SET FRONT = FRONT + 1
[ENDE von IF]
[ENDE VON WENN]

Schritt 4: AUSFAHRT

Lassen Sie uns den Vorgang zum Ein- und Ausreihen in die Warteschlange anhand der schematischen Darstellung verstehen.

Runde Warteschlange
Runde Warteschlange
Runde Warteschlange
Runde Warteschlange
Runde Warteschlange
Runde Warteschlange
Runde Warteschlange
Runde Warteschlange

Implementierung einer zirkulären Warteschlange mithilfe von 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)>

Ausgabe:

Runde Warteschlange