Wie verwalte ich eine vollständige kreisförmige Ereigniswarteschlange in C++?

Einführung

Circular Queue ist eine Verbesserung der linearen Warteschlange, die eingeführt wurde, um das Problem der Speicherverschwendung in linearen Warteschlangen zu lösen. Zirkuläre Warteschlangen nutzen das FIFO-Prinzip, um Elemente daraus einzufügen und daraus zu löschen. In diesem Tutorial besprechen wir den Betrieb einer zirkulären Warteschlange und deren Verwaltung.

Was ist eine kreisförmige Warteschlange?

Circular Queue ist eine andere Art von Warteschlange in der Datenstruktur, bei der das Front-End und das Back-End miteinander verbunden sind. Er wird auch als Ringpuffer bezeichnet. Sie funktioniert ähnlich wie eine lineare Warteschlange. Warum müssen wir also eine neue Warteschlange in die Datenstruktur einführen?

Wenn Sie eine lineare Warteschlange verwenden und die Warteschlange ihr maximales Limit erreicht, ist möglicherweise etwas Speicherplatz vor dem Endzeiger vorhanden. Dies führt zu Speicherverlust und ein guter Algorithmus sollte in der Lage sein, die Ressourcen voll auszunutzen.

Um das Problem der Speicherverschwendung zu lösen, haben Entwickler das Konzept der zirkulären Warteschlange eingeführt, das eine zirkuläre Verbindung zum Backend und Frontend herstellen und weitere Elemente einfügen kann.

Grundfunktionen der kreisförmigen Warteschlange

• Post - Gibt den Postwert der Warteschlange zurück.

• Front - Gibt den vorderen Wert der Warteschlange zurück.

• deQueue – Diese integrierte Methode wird verwendet, um Elemente aus der Warteschlange zu entfernen und gleichzeitig zu prüfen, ob die Warteschlange leer ist.

• enQueue − Diese Methode wird verwendet, um neue Elemente einzufügen und gleichzeitig die Warteschlangengröße zu überprüfen.

In einer zirkulären Warteschlange werden Elemente aus dem Backend hinzugefügt und aus dem Frontend entfernt. deQueue und enQueue sind von der Warteschlangengröße unabhängige Funktionen und werden mithilfe des Modulo-Operators implementiert. Ihre Zeitkomplexität beträgt O(1).

Zirkuläre Warteschlange verwalten

Wir verwalten zirkuläre Warteschlangen mithilfe von enQueue- und deQueue-Operationen. Anfänglich ist der vordere Wert der Ringwarteschlange 0, der hintere Wert -1 und alle Elemente in der Ringwarteschlange sind NULL.

Beispiel

C++-Code, der Arrays verwendet, um eine kreisförmige Warteschlange zu implementieren

#include <bits/stdc++.h>
using namespace std;
 
class Queue {
   //Initializing front and rear of the queue
   int rear, front;
   int sz;
   int* arr;
 
   public:
   Queue(int s) {
      front = rear = -1;
      sz = s;
      arr = new int[s];
   }
   
   void enQueue(int v);
   int deQueue();
   void displayQueue();
};
 
//Circular queue function
void Queue::enQueue(int v) {
   if ((front == 0 && rear == sz - 1)
      || (rear == (front - 1) % (sz - 1))) {
         printf("\nNo Space Queue is Full");
         return;
      }
   
      //Inserting the front element
      else if (front == -1) {
         front = rear = 0;
         arr[rear] = v;
      }
   
      else if (rear == sz - 1 && front != 0) {
         rear = 0;
         arr[rear] = v;
      }
   
      else {
         rear++;
         arr[rear] = v;
      }
}
 
//Function for deleting queue elements
int Queue::deQueue() {
   if (front == -1) {
      printf("\nQueue needs data it is empty");
      return INT_MIN;
   }
   
   int ele = arr[front];
   arr[front] = -1;
   if (front == rear) {
      front = -1;
      rear = -1;
   }
   else if (front == sz - 1)
      front = 0;
   else
      front++;
   return ele;
}
 
//Printing Circular queue elements
void Queue::displayQueue() {
   if (front == -1) {
      printf("\nQueue Empty");
      return;
   }
   printf("\nCircular Queue elements are: \n");
   if (rear >= front) {
      for (int i = front; i <= rear; i++)
      printf("%d ", arr[i]);
   } else {
      for (int i = front; i < sz; i++)
      printf("%d ", arr[i]);
   
      for (int i = 0; i <= rear; i++)
      printf("%d ", arr[i]);
   }
}
 
int main() {
   Queue q(5);
   //Pushing data in circular queue
   q.enQueue(10);
   q.enQueue(20);
   q.enQueue(3);
   q.enQueue(5);
   //Printing circular queue elements
   q.displayQueue();
   
   //Deleting front elements of circular queue
   printf("\nDeleted element = %d\n", q.deQueue());
   printf("\nDeleted element = %d", q.deQueue());
   q.displayQueue();
   q.enQueue(13);
   q.enQueue(27);
   q.enQueue(50);
   q.displayQueue();
   q.enQueue(22);
   
   return 0;
}

Ausgabe

Circular Queue elements are: 
10 20 3 5 
Deleted element = 10

Deleted element = 20
Circular Queue elements are: 
3 5 
Circular Queue elements are: 
3 5 13 27 50 
No Space Queue is Full

Fazit

Zirkuläre Warteschlangen werden bei der Speicherverwaltung und CPU-Planung verwendet. Es verwendet die Funktion displayQueue(), um Warteschlangenelemente anzuzeigen.

Wir sind am Ende dieses Tutorials angelangt. Ich hoffe, dieses Tutorial hat Ihnen geholfen zu verstehen, wie man eine kreisförmige Warteschlange implementiert.

Das obige ist der detaillierte Inhalt vonWie verwalte ich eine vollständige kreisförmige Ereigniswarteschlange in C++?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!