Circulaire buffer of Circulaire wachtrij is de geavanceerde versie van de normale wachtrij waarbij de laatste index en staartindex in een cirkelvormige structuur zijn verbonden. Circulaire buffer in C++ volgt twee methoden: enqueue() en dequeue(). Op basis van deze methoden voeren we de circulaire buffer- of circulaire wachtrijbewerking uit.
- De methode enqueue() controleert of de buffer gevuld is. Controleer anders of de eindindex de laatste is. Als dit het geval is, stelt u de staartwaarde in op 0. Als dit niet het geval is, verhoogt u de staartwaarde met de waarde bij die index.
- De functie dequeue() haalt de waarde uit de voorste index in de circulaire wachtrij. Als de wachtrij leeg is, wordt een bericht weergegeven dat de lege wachtrij leeg is. Anders wordt de laatste waarde opgehaald en uit de wachtrij verwijderd.
Programma om een circulaire buffer in C++ te implementeren
Door de genoemde twee methoden te volgen, implementeren we de circulaire buffer in C++. Laten we eens kijken naar alle stappen voor de implementatie van de circulaire wachtrij in C++.
#include
namespace std; gebruiken;
MyQueue structureren
{
int hoofd , staart ;
int Qgrootte;
int * NieuwArr;
MijnWachtrij ( int.nr ) {
hoofd = staart = -1 ;
Qmaat = maat;
NewArr = nieuwe int [ S ] ;
}
ongeldig enQueue ( int val ) ;
int deQueue ( ) ;
ongeldig showQueue ( ) ;
} ;
Beginnend met de code maken we eerst de ‘MyQueue’-structuur om de head- en tail-variabelen te initialiseren. De kopvariabele vertegenwoordigt de voorste indices en de staart vertegenwoordigt de achterste indices van een array. Daarna wordt de grootte van de cirkelvormige wachtrij, aangegeven door de variabele “Qsize”, gedefinieerd.
Vervolgens definiëren we de dynamisch toegewezen array van “NewArr” die de waarden van de circulaire wachtrij opslaat. Vervolgens roepen we MyQueue() aan, wat een constructor is, en geven we de parameter “sz” door voor de cirkelvormige wachtrijgrootte. Binnen de MyQueue()-constructor wijzen we de waarde “-1” toe aan de kop- en staartaanwijzers. Deze negatieve waarde geeft aan dat de wachtrij nu leeg is. Verderop wijzen we de “sz”-waarde toe die de grootte van de cirkelvormige wachtrij vertegenwoordigt. De circulaire wachtrij “NewArr” wordt ingesteld met een nieuw sleutelwoord om de array met gehele getallen binnen de opgegeven “sz”-grootte te creëren.
Vervolgens definiëren we de functies enQueue() en dequeue(). De enqueue() voegt de waarden vanaf de staart in de gedefinieerde cirkelvormige wachtrij in. De elementen in de kop van de cirkelvormige wachtrij worden echter geëlimineerd door de functie dequeue(). De lidfunctie showQueue() geeft de waarden van de circulaire wachtrij weer.
Stap 1: Maak een functie om de elementen in een circulaire buffer in te voegen
In de eerdere stap hebben we een klasse ingesteld waarin de privéleden worden geïnitialiseerd en de privélidfuncties worden ingesteld om de circulaire wachtrij te implementeren. Nu stellen we de functie in om de circulaire wachtrij te maken en voegen we de waarden in de circulaire wachtrij in met behulp van het algoritme.
void MyQueue::enQueue ( int val ){
als ( ( hoofd == 0 && staart == Qmaat - 1 ) || ( staart == ( hoofd - 1 ) % ( Qmaat - 1 ) ) )
{
uit << ' \N Wachtrij is gevuld' ;
opbrengst ;
}
anders als ( hoofd == - 1 )
{
hoofd = staart = 0 ;
NieuwArr [ staart ] = waarde;
}
anders als ( staart == Qmaat - 1 && hoofd ! = 0 )
{
staart = 0 ;
NieuwArr [ staart ] = waarde;
}
anders {
staart ++;
NieuwArr [ staart ] = waarde;
}
}
Hier roepen we de functie “enqueue()” uit de klasse “MyQueue” aan om het element in de circulaire wachtrij in te voegen als de wachtrij leeg is of onderstroom is. De functie “enqueue()” wordt doorgegeven met de parameter “val” en voegt de waarde in vanaf de staart van de cirkelvormige wachtrij. We stellen de “if-else” voorwaarde in om hiervoor de waarden in de circulaire wachtrij in te voegen. De eerste “if”-instructie, namelijk “if ((head == 0 && tail == Qsize – 1) || (tail == (head – 1) % (Qsize – 1)))” controleert twee voorwaarden of de head bevindt zich op de beginpositie en de staart bevindt zich op de eindpositie van de cirkelvormige wachtrij. Vervolgens wordt gecontroleerd of de staart zich in één positie aan de achterkant van het hoofd bevindt. Als aan een van deze voorwaarden is voldaan, is de wachtrij niet leeg en genereert de prompt het bericht.
Vervolgens hebben we de ‘else-if’-voorwaarde die identificeert of de wachtrij leeg is. Als dit het geval is, wordt de waarde in de wachtrij ingevoegd. Omdat de kop gelijk wordt gehouden aan -1, geeft dit aan dat de wachtrij leeg is en dat de waarde in de cirkelvormige wachtrij moet worden ingevoegd. Hiervoor stellen we de kop en de staart gelijk aan 0. Vervolgens voegen we de waarde van de staartpositie in de cirkelvormige wachtrij 'NewArr' in.
Dan hebben we onze derde ‘else-if’-voorwaarde die controleert of de staart zich op de laatste positie van de wachtrij bevindt en de kop niet de startpositie van de wachtrij is. Deze voorwaarde geldt wanneer de staart het einde bereikt en er nog ruimte is in de startpositie. Hiervoor moeten we de kop op 0 zetten en het element wordt toegevoegd vanuit de staartpositie. Als ten slotte niet aan alle gegeven voorwaarden is voldaan, is de wachtrij niet leeg of vol. In dit geval verhogen we de staart met 1 en wordt de waarde toegevoegd vanaf de nieuwe staartpositie.
Stap 2: Maak een functie om de elementen uit de circulaire buffer te verwijderen
We hebben de vorige code ingesteld om de elementen in de circulaire wachtrij te maken en in te voegen met behulp van de functie enqueue(). Nu definiëren we de implementatie van het verwijderen van de elementen uit de circulaire buffer als deze overloopt.
int MijnQueue::deQueue ( ){
als ( hoofd == - 1 )
{
uit << ' \N Wachtrij is gratis' ;
opbrengst INT_MIN;
}
int MijnGegevens = Nieuwe Arr [ hoofd ] ;
NieuwArr [ hoofd ] = -1 ;
als ( hoofd == staart )
{
hoofd = -1 ;
staart = -1 ;
}
anders als ( hoofd == Qmaat - 1 )
hoofd = 0 ;
anders
hoofd ++;
opbrengst Mijn data;
}
In de gegeven code roepen we de functie dequeue() aan vanuit de klasse “Myqueue” om het element uit de head-index te verwijderen. We hebben dus de “if”-instructie die controleert of de wachtrij leeg is. De kop is ingesteld met de waarde “-1” die de lege wachtrij vertegenwoordigt. Het bericht wordt gegenereerd dat de wachtrij leeg is en retourneert vervolgens de INT_MIN, wat de constante minimumwaarde is voor een int. De “if”-instructie bepaalt of de wachtrij onbezet is. Hiervoor definiëren we de variabele “MyData” en stellen we de waarde van het element bovenaan de wachtrij in. Vervolgens zetten we de kop op de positie -1, wat aangeeft dat deze waarde uit de wachtrij is verwijderd. Hierna controleren we of kop en staart gelijk zijn of niet. Als beide gelijk zijn, wijzen we aan beide de waarde “-1” toe, die de lege cirkelvormige wachtrij vertegenwoordigt. Ten slotte controleren we of de dequeue() functioneert als de head zich op de laatste index van de wachtrij bevindt. Hiervoor stellen we de waarde “0” in, die rondloopt aan het begin van de array. Als geen van de gegeven voorwaarden waar is, wordt de waarde van de kop verhoogd en wordt het uit de wachtrij verwijderde element geretourneerd.
Stap 3: Maak een functie om de elementen van de circulaire buffer weer te geven
In deze sectie roepen we de functie showQueue() aan om de elementen van de circulaire wachtrij “NewArr” weer te geven.
void MyQueue::showQueue ( ){
als ( hoofd == - 1 )
{
uit << ' \N Wachtrij is gratis' ;
opbrengst ;
}
uit << ' \N Circulaire wachtrij-elementen: ' ;
als ( staart > = hoofd )
{
voor ( int ik = hoofd ; i < = staart ; ik++ )
uit << NieuwArr [ i ] << ' ' ;
}
anders
{
voor ( int ik = hoofd ; i < Qmaat; ik++ )
uit << NieuwArr [ i ] << ' ' ;
voor ( int ik = 0 ; i < = staart ; ik++ )
uit << NieuwArr [ i ] << ' ' ;
}
}
De lege status van de wachtrij wordt eerst geverifieerd. Er wordt een indicatie weergegeven dat de circulaire wachtrij vrij is als de wachtrij vrij is. Anders toont de functie de elementen van de circulaire wachtrij. Hiervoor definiëren we de “if”-instructie waarbij we de staart hebben die groter is dan of gelijk is aan de kop. Deze voorwaarde is ingesteld om het geval af te handelen wanneer de circulaire wachtrij niet is voltooid.
Voor dit geval gebruiken we de “for”-lus om van kop tot staart te itereren en de waarden van de cirkelvormige wachtrij af te drukken. In het volgende geval wordt de cirkelvormige wachtrij voltooid. Hiervoor controleren we met behulp van de “if”-voorwaarde waarbij de staart kleiner is dan de kop. Vervolgens moeten we twee lussen gebruiken, waarbij de eerste zich herhaalt van de kop tot het einde van de wachtrij en de tweede vanaf het begin van de staart.
Stap 4: Maak de Main()-functie van het Circular Queue-programma
Ten slotte creëren we de functie main() van het programma, waarbij we vijf gehele getallen in de cirkelvormige wachtrij invoegen en de gehele getallen van de wachtrij weergeven. Daarna tonen we de verwijderde gehele getallen uit de circulaire wachtrij door de functie dequeue() aan te roepen. Nadat we een aantal elementen uit de wachtrij hebben gehaald, vullen we de wachtrij opnieuw door de nieuwe elementen in te voegen met behulp van de functie enqueue().
int. hoofd ( ){
MyQueue dat ( 5 ) ;
// Elementen invoegen in Circulaire wachtrij
que.enQueue ( elf ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( vijftien ) ;
// Display-elementen aanwezig in Circulaire wachtrij
que.showQueue ( ) ;
// Elementen verwijderen uit Circular Queue
uit << ' \N Verwijderd element = ' << que.deQueue ( ) ;
uit << ' \N Verwijderd element = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
opbrengst 0 ;
}
Uitgang:
De resultaten van de implementatie van de circulaire wachtrij worden weergegeven op het C++-promptscherm.
Conclusie
Concluderend wordt het onderwerp circulaire buffer in dit artikel uitgebreid toegelicht. We hebben eerst de circulaire buffer gemaakt, vervolgens uitgelegd hoe u deze uit de circulaire wachtrij kunt verwijderen en vervolgens de elementen van de circulaire in C++ weergegeven.