c circular queue data structure
In diesem Lernprogramm zur Datenstruktur von C ++ Circular Queue wird erläutert, was Circular Queue ist, was die grundlegenden Vorgänge zusammen mit Implementierung und Anwendungen sind:
Eine kreisförmige Warteschlange ist eine Erweiterung der zuvor diskutierten Basiswarteschlange. Es ist auch als 'Ringpuffer' bekannt.
Was ist Circular Queue in C ++?
Eine kreisförmige Warteschlange ist eine lineare Datenstruktur, in der Datenelemente gespeichert werden. Es führt Operationen aus, indem es dem FIFO-Ansatz (First In, First Out) folgt, und die letzte Position in der Warteschlange wird wieder mit der ersten Position verbunden, um einen Kreis zu bilden.
=> Suchen Sie hier nach der gesamten C ++ - Schulungsserie
Was du lernen wirst:
Zirkuläre Warteschlange In C ++
Das folgende Diagramm zeigt eine kreisförmige Warteschlange.
Das obige Bild zeigt eine kreisförmige Datenstruktur der Größe 10. Die ersten sechs Elemente befinden sich bereits in der Warteschlange und wir sehen, dass die erste und die letzte Position verbunden sind. Aufgrund dieser Anordnung wird kein Platz verschwendet, wie dies in einer linearen Warteschlange der Fall ist.
PHP Interview Frage und Antwort für Erfahrung
In einer linearen Warteschlange, nachdem die Warteschlange voll ist, löschen wir die Elemente von einem anderen Ende, und der Status der Warteschlange wird weiterhin als voll angezeigt, und wir können keine weiteren Elemente einfügen.
In der kreisförmigen Warteschlange können wir, wenn die Warteschlange voll ist und wenn wir Elemente von vorne entfernen, da die letzten und ersten Positionen verbunden sind, die Elemente hinten einfügen, die durch Löschen des Elements geräumt wurden.
Im nächsten Abschnitt lernen wir die grundlegenden Operationen der kreisförmigen Warteschlange kennen.
Grundoperationen
Einige der grundlegenden Operationen der zirkulären Warteschlange sind wie folgt:
Vorderseite: Gibt die vordere Position in der kreisförmigen Warteschlange zurück.
Rückseite: Gibt die hintere Position in der kreisförmigen Warteschlange zurück.
Enqueue: Enqueue (Wert) wird verwendet, um ein Element in die kreisförmige Warteschlange einzufügen. Das Element wird immer am hinteren Ende der Warteschlange eingefügt.
Wir folgen der folgenden Abfolge von Schritten, um ein neues Element in die kreisförmige Warteschlange einzufügen.
# 1) Überprüfen Sie, ob die kreisförmige Warteschlange voll ist: test ((hinten == GRÖSSE-1 && vorne == 0) || (hinten == vorne-1)), wobei 'GRÖSSE' die Größe der kreisförmigen Warteschlange ist.
#zwei) Wenn die kreisförmige Warteschlange voll ist, wird die Meldung 'Warteschlange ist voll' angezeigt. Wenn die Warteschlange nicht voll ist, prüfen Sie, ob (hinten == GRÖSSE - 1 && vorne! = 0). Wenn dies zutrifft, setzen Sie hinten = 0 und fügen Sie das Element ein.
Warteschlange: Die Dequeue-Funktion wird verwendet, um ein Element aus der Warteschlange zu löschen. In der kreisförmigen Warteschlange wird das Element immer aus dem Frontend gelöscht. Nachstehend ist die Reihenfolge für die Dequeue-Operation in einer kreisförmigen Warteschlange angegeben.
Schritte:
# 1) Überprüfen Sie, ob die kreisförmige Warteschlange leer ist: Überprüfen Sie, ob (front == - 1).
wie man einem Array hinzufügt
#zwei) Wenn es leer ist, wird die Meldung 'Warteschlange ist leer' angezeigt. Wenn die Warteschlange nicht leer ist, führen Sie Schritt 3 aus.
#3) Überprüfen Sie ob (vorne == hinten). Wenn es wahr ist, setze front = hinten = -1, sonst überprüfe ob (vorne == Größe-1), wenn es wahr ist, setze front = 0 und gib das Element zurück.
Illustration
In diesem Abschnitt werden wir das Hinzufügen / Entfernen von Elementen in der kreisförmigen Warteschlange detailliert veranschaulichen.
Betrachten Sie die folgende kreisförmige Warteschlange mit 5 Elementen wie unten gezeigt:
Als nächstes fügen wir Element 1 in die Warteschlange ein.
Als nächstes fügen wir einen Artikel mit dem Wert 3 ein.
Wenn wir die Elemente einfügen, um eine Warteschlange voll zu machen, sieht die Darstellung wie folgt aus.
Jetzt löschen wir die beiden Elemente, d. H. Punkt 1 und Punkt 3, wie unten gezeigt aus der Warteschlange.
Als nächstes fügen wir das Element 11 in die kreisförmige Warteschlange ein oder stellen sie in die Warteschlange, wie unten dargestellt.
Fügen wir erneut Element 13 in die kreisförmige Warteschlange ein. Die Warteschlange sieht wie unten gezeigt aus.
Wir sehen, dass wir in der kreisförmigen Warteschlange Elemente in einen Kreis verschieben oder einfügen. Daher können wir den gesamten Speicherplatz der Warteschlange belegen, bis sie voll ist.
Implementierung
Implementieren wir die zirkuläre Warteschlange mit C ++.
#include using namespace std; class Queue { public: // Initialize front and rear int rear, front; // Circular Queue int size; int *circular_queue; Queue(int sz) { front = rear = -1; size = sz; circular_queue = new int(sz); } void enQueue(int elem); int deQueue(); void displayQueue(); }; /* Function to create Circular queue */ void Queue::enQueue(int elem) { if ((front == 0 && rear == size-1) || (rear == (front-1)%(size-1))) { cout<<'
Queue is Full'; return; } else if (front == -1) { /* Insert First Element */ front = rear = 0; circular_queue(rear) = elem; } else if (rear == size-1 && front != 0) { rear = 0; circular_queue(rear) = elem; } else { rear++; circular_queue(rear) = elem; } } // Function to delete element from Circular Queue int Queue::deQueue() { if (front == -1) { cout<<'
Queue is Empty'; return -1; } int data = circular_queue(front); circular_queue(front) = -1; if (front == rear) { front = -1; rear = -1; } else if (front == size-1) front = 0; else front++; return data; } //display elements of Circular Queue void Queue::displayQueue() { if (front == -1) { cout<<'
Queue is Empty'<= front) { for (int i = front; i <= rear; i++) cout< Oben ist die Ausgabe von zirkulären Warteschlangenoperationen dargestellt. Zuerst fügen wir die Elemente hinzu und entfernen oder entfernen dann zwei Elemente. Als nächstes fügen wir drei weitere Elemente in die kreisförmige Warteschlange ein oder stellen sie in die Warteschlange. Wir sehen, dass im Gegensatz zur linearen Warteschlange die Elemente am Ende der Warteschlange hinzugefügt werden.
Implementierung einer verknüpften Liste
Lassen Sie uns jetzt die Implementierung einer zirkulären Warteschlange für verknüpfte Listen diskutieren. Im Folgenden wird die Implementierung der verknüpften Liste der zirkulären Warteschlange in C ++ angegeben. Beachten Sie, dass wir struct verwenden, um jeden Knoten darzustellen. Die Operationen sind die gleichen wie zuvor beschrieben, außer dass wir sie in diesem Fall in Bezug auf die verknüpften Listenknoten ausführen müssen.
Die Ausgabe zeigt die kreisförmige Warteschlange nach der Warteschlangenoperation, der Warteschlange und auch nach der zweiten Warteschlangenoperation.
#include using namespace std; struct Node { int data; struct Node* link; }; struct PQueue { struct Node *front, *rear; }; /* this functions performs enqueue operation for circular queue */ void enQueue(PQueue *pq,int elem) { struct Node *temp = new Node; temp->data = elem; if (pq->front == NULL) pq->front = temp; else pq->rear->link = temp; pq->rear = temp; pq->rear->link = pq->front; } // This function performs dequeue operation for Circular Queue int deQueue(PQueue *pq) { if (pq->front == NULL) { cout<<'Queue is empty!!'; return -1; } int elem; // item to be dequeued // item is the last node to be deleted if (pq->front == pq->rear) { elem = pq->front->data; free(pq->front); pq->front = NULL; pq->rear = NULL; } else //more than one nodes { struct Node *temp = pq->front; elem = temp->data; pq->front = pq->front->link; pq->rear->link= pq->front; free(temp); } return elem ; } //display elements of Circular Queue void displayQueue(struct PQueue *pq) { struct Node *temp = pq->front; while (temp->link != pq->front) { cout<data<<' '; temp = temp->link; } cout<data; } //main program int main() { // Create a circular queue and initialize front and rear PQueue *pq = new PQueue; pq->front = pq->rear = NULL; // Insert/enqueue elements in Circular Queue enQueue(pq, 1); enQueue(pq, 3); enQueue(pq, 5); cout<<'
Circular Queue elements after enqueue operation: '; // Display elements in Circular Queue displayQueue(pq); // Delete/dequeue elements from Circular Queue cout<<'
Dequeued Item: '< Ausgabe:

Die nächste Implementierung ist ein Java-Programm zur Demonstration der zirkulären Warteschlange mithilfe der verknüpften Liste.
import java.util.* ; class Main { // Node structure static class Node { int data; Node link; } static class CQueue { Node front, rear; } // Enqueue operation for circular queue static void enQueue(CQueue cq, int value) { Node temp = new Node(); temp .data = value; if (cq .front == null) cq .front = temp; else cq .rear .link = temp; cq .rear = temp; cq .rear .link = cq .front; } // Dequeue operation for Circular Queue static int deQueue(CQueue cq) { if (cq .front == null) { System.out.printf ('Queue is empty!!'); return Integer.MIN_VALUE; } int value; // Value to be dequeued // the last node to be deleted if (cq.front == cq.rear) { value = cq.front.data; cq.front = null; cq.rear = null; } else { // There are more than one nodes Node temp = cq.front; value = temp.data; cq.front = cq.front.link; cq.rear.link= cq.front; } return value ; } // display the elements of Circular Queue static void displayQueue( CQueue cq) { Node temp = cq.front; while (temp.link != cq.front) { System.out.printf('%d ', temp.data); temp = temp.link; } System.out.printf('%d', temp.data); } /* main program */ public static void main(String args()) { // Create a queue and initialize front and rear CQueue cq = new CQueue(); cq.front = cq.rear = null; // Insert/enqueue elements in Circular Queue enQueue(cq, 2); enQueue(cq, 4); enQueue(cq, 6); System.out.print('
Circular Queue elements after Enqueue Operation:'); // Display elements in Circular Queue displayQueue(cq); // Delete/dequeue elements from Circular Queue System.out.printf('
Dequeued Item = %d', deQueue(cq)); System.out.printf('
Dequeued Item = %d', deQueue(cq)); System.out.print('
Circular Queue elements after Dequeue Operation:'); displayQueue(cq); enQueue(cq, 8); enQueue(cq, 10); System.out.print('
Circular Queue elements after second Enqueue Operation:'); displayQueue(cq); } }
Ausgabe:

Die Ausgabe des obigen Programms ähnelt der des vorherigen Programms.
Anwendungen
Lassen Sie uns einige der Anwendungen der zirkulären Warteschlange diskutieren.
- CPU-Planung: Betriebssystemprozesse, bei denen ein Ereignis auftreten muss oder andere Prozesse zur Ausführung abgeschlossen werden müssen, werden häufig in einer kreisförmigen Warteschlange verwaltet, sodass sie nacheinander ausgeführt werden, wenn alle Bedingungen erfüllt sind oder wenn alle Ereignisse auftreten.
- Speicherverwaltung: Die Verwendung gewöhnlicher Warteschlangen verschwendet Speicherplatz, wie bereits in unserer obigen Diskussion erwähnt. Die Verwendung einer kreisförmigen Warteschlange für die Speicherverwaltung ist für eine optimale Speichernutzung von Vorteil.
- Computergesteuertes Verkehrssignalsystem: Computergestützte Verkehrssignale werden häufig zu einer kreisförmigen Warteschlange hinzugefügt, damit sie sich nach Ablauf des angegebenen Zeitintervalls wiederholen.
Fazit
Kreisförmige Warteschlangen beheben den Hauptnachteil einer normalen Warteschlange, bei der keine Elemente eingefügt werden können, wenn sich der hintere Zeiger am Ende der Warteschlange befindet, selbst wenn die Elemente gelöscht werden und der Speicherplatz geleert wird. In einer kreisförmigen Warteschlange sind Elemente kreisförmig angeordnet, so dass überhaupt kein Platz verschwendet wird.
Wir haben auch die Hauptoperationen der kreisförmigen Warteschlange gesehen. Kreisförmige Warteschlangen sind hauptsächlich für Planungszwecke und Anwendungen wie Verkehrssignalsysteme nützlich, bei denen die Signale abwechselnd leuchten.
Wie erstelle ich ein Array von Strings in Java?
In unserem nächsten Tutorial lernen wir die doppelseitigen Warteschlangen kennen, die einfach als 'deque' bezeichnet werden.
=> Besuchen Sie hier, um C ++ von Grund auf neu zu lernen
Literatur-Empfehlungen
- Warteschlangendatenstruktur in C ++ mit Illustration
- Datenstruktur der Prioritätswarteschlange in C ++ mit Abbildung
- Datenstruktur für zirkuläre verknüpfte Listen in C ++ mit Abbildung
- Data Mart Tutorial - Typen, Beispiele und Implementierung von Data Mart
- Stapeldatenstruktur in C ++ mit Illustration
- Data Mining-Beispiele: Häufigste Anwendungen von Data Mining 2021
- Datenstruktur des Binärbaums in C ++
- Prioritätswarteschlange In STL