Der Ringpuffer oder die Ringwarteschlange ist die erweiterte Version der normalen Warteschlange, bei der der letzte Index und der Endindex in einer Ringstruktur verbunden sind. Der Ringpuffer in C++ folgt zwei Methoden: enqueue() und dequeue(). Basierend auf diesen Methoden führen wir die Ringpuffer- oder Ringwarteschlangenoperation durch.
- Die Methode enqueue() prüft, ob der Puffer gefüllt ist. Überprüfen Sie andernfalls, ob der Endindex der letzte ist. Wenn ja, setzen Sie den Endwert auf 0. Wenn nicht, erhöhen Sie den Endwert um den Wert an diesem Index.
- Die Funktion dequeue() übernimmt den Wert vom vorderen Index in der zirkulären Warteschlange. Wenn die Warteschlange leer ist, wird eine Meldung angezeigt, dass die Warteschlange leer ist. Andernfalls wird der letzte Wert abgerufen und aus der Warteschlange gelöscht.
Programm zur Implementierung eines Ringpuffers in C++
Nach den beiden genannten Methoden implementieren wir den Ringpuffer in C++. Betrachten wir alle Schritte für die Implementierung der zirkulären Warteschlange in C++.
#include
Verwenden des Namensraums std;
struct MyQueue
{
int Kopf , Schwanz ;
int Qsize;
int * NewArr;
Meine Warteschlange ( int Nr ) {
Kopf = Schwanz = -1 ;
Qsize = Größe;
NewArr = new int [ S ] ;
}
void enQueue ( int val ) ;
int deQueue ( ) ;
void showQueue ( ) ;
} ;
Beginnend mit dem Code erstellen wir zunächst die Struktur „MyQueue“, um die Head- und Tail-Variablen zu initialisieren. Die Variable head repräsentiert die vorderen Indizes und die Variable tail repräsentiert die hinteren Indizes eines Arrays. Danach wird die Größe der zirkulären Warteschlange, angegeben durch die Variable „Qsize“, definiert.
Anschließend definieren wir das dynamisch zugewiesene Array „NewArr“, das die Werte der zirkulären Warteschlange speichert. Als nächstes rufen wir MyQueue() auf, einen Konstruktor, und übergeben den Parameter „sz“ für die Größe der kreisförmigen Warteschlange. Im MyQueue()-Konstruktor weisen wir den Head- und Tail-Zeigern den Wert „-1“ zu. Dieser negative Wert zeigt an, dass die Warteschlange jetzt leer ist. Im weiteren Verlauf weisen wir den „sz“-Wert zu, der die Größe der kreisförmigen Warteschlange darstellt. Die zirkuläre Warteschlange „NewArr“ wird mit einem neuen Schlüsselwort festgelegt, um das Array von Ganzzahlen innerhalb der angegebenen „sz“-Größe zu erstellen.
Anschließend definieren wir die Funktionen enQueue() und dequeue(). Die enqueue() fügt die Werte vom Ende in die definierte kreisförmige Warteschlange ein. Die Elemente im Kopf der kreisförmigen Warteschlange werden jedoch durch die Funktion dequeue() entfernt. Die Memberfunktion showQueue() zeigt die Werte der zirkulären Warteschlange an.
Schritt 1: Erstellen Sie eine Funktion zum Einfügen der Elemente in einen kreisförmigen Puffer
Im vorherigen Schritt legen wir eine Klasse fest, in der die privaten Mitglieder initialisiert werden und die privaten Mitgliedsfunktionen so eingestellt werden, dass sie die zirkuläre Warteschlange implementieren. Jetzt legen wir die Funktion fest, um die zirkuläre Warteschlange zu erstellen und die Werte mithilfe des Algorithmus in die zirkuläre Warteschlange einzufügen.
void MyQueue::enQueue ( int val ){
Wenn ( ( Kopf == 0 && Schwanz == Qsize - 1 ) || ( Schwanz == ( Kopf - 1 ) % ( QGröße - 1 ) ) )
{
cout << ' \N Warteschlange ist gefüllt“ ;
zurückkehren ;
}
anders Wenn ( Kopf == - 1 )
{
Kopf = Schwanz = 0 ;
NeuArr [ Schwanz ] = Wert;
}
anders Wenn ( Schwanz == Qsize - 1 && Kopf ! = 0 )
{
Schwanz = 0 ;
NeuArr [ Schwanz ] = Wert;
}
anders {
Schwanz ++;
NeuArr [ Schwanz ] = Wert;
}
}
Hier rufen wir die Funktion „enqueue()“ aus der Klasse „MyQueue“ auf, um das Element in die kreisförmige Warteschlange einzufügen, wenn die Warteschlange leer ist oder einen Unterlauf aufweist. Die Funktion „enqueue()“ wird mit dem Parameter „val“ übergeben und fügt den Wert vom Ende der zirkulären Warteschlange ein. Dazu setzen wir die „if-else“-Bedingung, um die Werte in die Ringwarteschlange einzufügen. Die erste „if“-Anweisung, die „if ((head == 0 && tail == Qsize – 1) || (tail == (head – 1) % (Qsize – 1)))“ lautet, prüft zwei Bedingungen, ob der Kopf befindet sich an der Anfangsposition und das Ende befindet sich an der Endposition der kreisförmigen Warteschlange. Anschließend wird geprüft, ob sich der Schwanz in einer Position am Hinterkopf befindet. Wenn eine dieser Bedingungen erfüllt ist, ist die Warteschlange nicht leer und die Eingabeaufforderung generiert die Nachricht.
Als nächstes haben wir die „else-if“-Bedingung, die angibt, ob die Warteschlange leer ist. Wenn ja, wird der Wert in die Warteschlange eingefügt. Da der Kopf auf -1 gehalten wird, zeigt dies an, dass die Warteschlange leer ist und der Wert in die Ringwarteschlange eingefügt werden muss. Dazu setzen wir den Kopf und den Schwanz auf 0. Anschließend fügen wir den Wert von der Schwanzposition in die kreisförmige Warteschlange „NewArr“ ein.
Dann haben wir unsere dritte „sonst-wenn“-Bedingung, die prüft, ob sich der Schwanz an der letzten Position der Warteschlange befindet und der Kopf nicht die Startposition der Warteschlange ist. Diese Bedingung gilt, wenn der Schwanz das Ende erreicht und in der Startposition noch Platz ist. Dazu müssen wir den Kopf auf 0 setzen und das Element wird von der Schwanzposition aus hinzugefügt. Wenn schließlich nicht alle angegebenen Bedingungen erfüllt sind, ist die Warteschlange weder leer noch voll. In diesem Fall erhöhen wir den Schwanz um 1 und der Wert wird ab der neuen Schwanzposition hinzugefügt.
Schritt 2: Erstellen Sie eine Funktion zum Löschen der Elemente aus dem kreisförmigen Puffer
Wir legen den vorherigen Code fest, um die Elemente mit der Funktion enqueue() zu erstellen und in die kreisförmige Warteschlange einzufügen. Jetzt definieren wir die Implementierung zum Entfernen der Elemente aus dem Ringpuffer, wenn dieser überläuft.
int MyQueue::deQueue ( ){
Wenn ( Kopf == - 1 )
{
cout << ' \N Warteschlange ist frei“ ;
zurückkehren INT_MIN;
}
int MyData = NewArr [ Kopf ] ;
NeuArr [ Kopf ] = -1 ;
Wenn ( Kopf == Schwanz )
{
Kopf = -1 ;
Schwanz = -1 ;
}
anders Wenn ( Kopf == Qsize - 1 )
Kopf = 0 ;
anders
Kopf ++;
zurückkehren Meine Daten;
}
Im angegebenen Code rufen wir die Funktion dequeue() aus der Klasse „Myqueue“ auf, um das Element aus dem Kopfindex zu entfernen. Wir haben also die „if“-Anweisung, die prüft, ob die Warteschlange leer ist. Der Kopf wird auf den Wert „-1“ gesetzt, der die leere Warteschlange darstellt. Es wird die Meldung generiert, dass die Warteschlange leer ist, und dann wird INT_MIN zurückgegeben, was der konstante Mindestwert für einen int ist. Die „if“-Anweisung bestimmt, ob die Warteschlange nicht belegt ist. Dazu definieren wir die Variable „MyData“ und setzen den Wert des Elements an der Spitze der Warteschlange. Dann setzen wir den Kopf auf die Position -1, was anzeigt, dass dieser Wert aus der Warteschlange entfernt wird. Danach prüfen wir, ob Kopf und Schwanz gleich sind oder nicht. Wenn beide gleich sind, weisen wir beiden den Wert „-1“ zu, was die leere kreisförmige Warteschlange darstellt. Zuletzt prüfen wir, ob dequeue() funktioniert, wenn sich der Kopf am letzten Index der Warteschlange befindet. Dazu setzen wir den Wert „0“, der sich am Anfang des Arrays wiederholt. Wenn keine der angegebenen Bedingungen zutrifft, wird der Wert des Kopfes erhöht und das aus der Warteschlange entfernte Element zurückgegeben.
Schritt 3: Erstellen Sie eine Funktion zum Anzeigen der Elemente des kreisförmigen Puffers
In diesem Abschnitt rufen wir die Funktion showQueue() auf, um die Elemente der kreisförmigen Warteschlange „NewArr“ anzuzeigen.
void MyQueue::showQueue ( ){
Wenn ( Kopf == - 1 )
{
cout << ' \N Warteschlange ist frei“ ;
zurückkehren ;
}
cout << ' \N Elemente der kreisförmigen Warteschlange: „ ;
Wenn ( Schwanz > = Kopf )
{
für ( int i = Kopf ; ich < = Schwanz ; i++ )
cout << NeuArr [ ich ] << ' ' ;
}
anders
{
für ( int i = Kopf ; ich < Qsize; i++ )
cout << NeuArr [ ich ] << ' ' ;
für ( int i = 0 ; ich < = Schwanz ; i++ )
cout << NeuArr [ ich ] << ' ' ;
}
}
Zunächst wird der Leerstatus der Warteschlange überprüft. Wenn die Warteschlange frei ist, wird ein Hinweis darauf angezeigt, dass die Ringwarteschlange frei ist. Andernfalls zeigt die Funktion die Elemente der zirkulären Warteschlange an. Dazu definieren wir die „if“-Anweisung, bei der der Schwanz größer oder gleich dem Kopf ist. Diese Bedingung wird festgelegt, um den Fall zu behandeln, dass die Ringwarteschlange nicht abgeschlossen ist.
In diesem Fall verwenden wir die „for“-Schleife, um von Kopf bis Ende zu iterieren und die Werte der kreisförmigen Warteschlange auszugeben. Im nächsten Fall ist die zirkuläre Warteschlange abgeschlossen. Hierzu prüfen wir anhand der „Wenn“-Bedingung, dass der Schwanz kleiner als der Kopf ist. Dann müssen wir zwei Schleifen verwenden, wobei die erste vom Kopf bis zum Ende der Warteschlange und die zweite vom Anfang des Endes iteriert.
Schritt 4: Erstellen Sie die Main()-Funktion des Circular Queue-Programms
Zuletzt erstellen wir die Funktion main() des Programms, in der wir fünf Ganzzahlen in die kreisförmige Warteschlange einfügen und die Ganzzahlen der Warteschlange anzeigen. Danach zeigen wir die gelöschten Ganzzahlen aus der zirkulären Warteschlange an, indem wir die Funktion dequeue() aufrufen. Nachdem wir einige Elemente aus der Warteschlange entfernt haben, füllen wir die Warteschlange erneut, indem wir die neuen Elemente mithilfe der Funktion enqueue() einfügen.
int main ( ){
MyQueue das ( 5 ) ;
// Elemente einfügen In Runde Warteschlange
que.enQueue ( elf ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( fünfzehn ) ;
// Anzeigeelemente vorhanden In Runde Warteschlange
que.showQueue ( ) ;
// Elemente aus der Circular Queue löschen
cout << ' \N Gelöschtes Element = ' << que.deQueue ( ) ;
cout << ' \N Gelöschtes Element = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
zurückkehren 0 ;
}
Ausgabe:
Die Ergebnisse der Implementierung der zirkulären Warteschlange werden auf dem C++-Eingabeaufforderungsbildschirm angezeigt.
Abschluss
Abschließend wird das Thema Kreispuffer in diesem Artikel ausführlich erläutert. Wir haben zuerst den Ringpuffer erstellt, dann erklärt, wie man aus der Ringwarteschlange löscht, und dann die Elemente des Ringpuffers in C++ angezeigt.