Circular buffer eller Circular queue är den avancerade versionen av den normala kön där det sista indexet och tail index är sammankopplade i en cirkulär struktur. Cirkulär buffert i C++ följer två metoder: enqueue() och dequeue(). Vi utför den cirkulära bufferten eller den cirkulära köoperationen baserat på dessa metoder.
- Metoden enqueue() kontrollerar om bufferten är fylld. Annars kontrollerar du att slutindexet är det sista. Om så är fallet, ställ in svansvärdet till 0. Om inte, öka svansvärdet med värdet vid det indexet.
- Funktionen dequeue() tar värdet från det främre indexet i den cirkulära kön. Om kön är tom kommer ett meddelande att visa den tomma kön. Annars får den det sista värdet och tar bort det från kön.
Program för att implementera en cirkulär buffert i C++
Efter de två nämnda metoderna implementerar vi den cirkulära bufferten i C++. Låt oss överväga alla steg för den cirkulära köimplementeringen i C++.
#include
använder namnutrymme std;
strukturera MyQueue
{
int huvud , svans ;
int Qsize;
int * NewArr;
MyQueue ( int nr ) {
huvud = svans = -1 ;
Qsize = storlek;
NewArr = ny int [ s ] ;
}
ogiltig kö ( int val ) ;
int deQueue ( ) ;
ogiltig showQueue ( ) ;
} ;
Med början med koden skapar vi först 'MyQueue'-strukturen för att initiera huvud- och svansvariablerna. Huvudvariabeln representerar de främre indexen och svansen representerar en arrays bakre bakindex. Därefter definieras den cirkulära köns storlek, betecknad med variabeln 'Qsize'.
Sedan definierar vi den dynamiskt allokerade arrayen av 'NewArr' som lagrar värdena för den cirkulära kön. Därefter anropar vi MyQueue() som är en konstruktor och skickar parametern 'sz' för den cirkulära köstorleken. Inuti MyQueue()-konstruktorn tilldelar vi '-1'-värdet till huvud- och svanspekarna. Detta negativa värde indikerar att kön är tom nu. När vi går vidare tilldelar vi värdet 'sz' som representerar storleken på den cirkulära kön. Den cirkulära 'NewArr'-kön ställs in med ett nytt nyckelord för att skapa arrayen av heltal inom den angivna 'sz'-storleken.
Sedan definierar vi funktionerna enQueue() och dequeue(). Enqueue() infogar värdena i den definierade cirkulära kön från svansen. Emellertid elimineras elementen i den cirkulära köns huvud av funktionen dequeue(). Medlemsfunktionen showQueue() visar värdena för den cirkulära kön.
Steg 1: Skapa en funktion för att infoga elementen i en cirkulär buffert
I det tidigare steget satte vi en klass där de privata medlemmarna initieras och de privata medlemsfunktionerna ställs in för att implementera den cirkulära kön. Nu ställer vi in funktionen för att skapa den cirkulära kön och infoga värdena i den cirkulära kön med hjälp av algoritmen.
ogiltig MyQueue::enQueue ( int val ){
om ( ( huvud == 0 && svans == Qsize - 1 ) || ( svans == ( huvud - 1 ) % ( Qsize - 1 ) ) )
{
cout << ' \n Kön är fylld' ;
lämna tillbaka ;
}
annan om ( huvud == - 1 )
{
huvud = svans = 0 ;
NewArr [ svans ] = val;
}
annan om ( svans == Qsize - 1 && huvud ! = 0 )
{
svans = 0 ;
NewArr [ svans ] = val;
}
annan {
svans ++;
NewArr [ svans ] = val;
}
}
Här anropar vi funktionen 'enqueue()' från klassen 'MyQueue' för att infoga elementet i den cirkulära kön om kön är tom eller underflytande. Funktionen 'enqueue()' skickas med parametern 'val' och infogar värdet från den cirkulära köns svans. Vi ställer in villkoret 'om-else' för att infoga värdena i den cirkulära kön för detta. Den första 'if'-satsen som är 'if ((huvud == 0 && svans == Qsize – 1) || (tail == (huvud – 1) % (Qsize – 1)))' kontrollerar två villkor om huvudet är i startpositionen och svansen är i slutpositionen av den cirkulära kön. Sedan kontrollerar den om svansen är i en position på baksidan av huvudpositionen. Om något av dessa villkor är uppfyllt är kön inte tom och uppmaningen genererar meddelandet.
Därefter har vi villkoret 'annat om' som identifierar om kön är tom. Om så är fallet, infogas värdet i kön. Eftersom huvudet hålls lika med -1, visar det att kön är tom och att värdet måste infogas i den cirkulära kön. För detta sätter vi huvudet och svansen lika med 0. Sedan infogar vi värdet från svanspositionen i den cirkulära kön 'NewArr'.
Sedan har vi vårt tredje 'annat-om'-villkor som kontrollerar om svansen är i den sista positionen i kön och huvudet inte är startpositionen för kön. Detta villkor gäller när svansen når slutet och startpositionen fortfarande har plats. För detta måste vi ställa in huvudet på 0, och elementet läggs till från svanspositionen. Slutligen, om alla givna villkor inte är uppfyllda, är kön varken tom eller full. I det här fallet ökar vi svansen med 1 och värdet läggs till från den nya svanspositionen.
Steg 2: Skapa en funktion för att ta bort elementen från den cirkulära bufferten
Vi ställer in föregående kod för att skapa och infoga elementen i den cirkulära kön med funktionen enqueue(). Nu definierar vi implementeringen av att ta bort elementen från den cirkulära bufferten om den rinner över.
int MyQueue::deQueue ( ){
om ( huvud == - 1 )
{
cout << ' \n Kön är ledig' ;
lämna tillbaka INT_MIN;
}
int MyData = NewArr [ huvud ] ;
NewArr [ huvud ] = -1 ;
om ( huvud == svans )
{
huvud = -1 ;
svans = -1 ;
}
annan om ( huvud == Qsize - 1 )
huvud = 0 ;
annan
huvud ++;
lämna tillbaka Min data;
}
I den givna koden anropar vi funktionen dequeue() från klassen 'Myqueue' för att ta bort elementet från huvudindexet. Så vi har 'if'-satsen som kontrollerar om kön är tom. Huvudet är satt med värdet '-1' som representerar den tomma kön. Meddelandet genereras att kön är tom och returnerar sedan INT_MIN som är det konstanta minimivärdet för en int. 'if'-satsen avgör om kön är ledig. För detta definierar vi variabeln 'MyData' och ställer in elementets värde i köns huvud. Sedan sätter vi huvudet på -1-positionen vilket indikerar att detta värde har tagits bort från kön. Efter detta kontrollerar vi om huvudet och svansen är lika eller inte. Om båda är lika, tilldelar vi värdet '-1' till båda, vilket representerar den tomma cirkulära kön. Slutligen kontrollerar vi om dequeue() fungerar om huvudet är vid det sista indexet i kön. För detta ställer vi in det med värdet '0' som går runt i början av arrayen. Om inget av de givna villkoren är sanna, ökas värdet på huvudet och det urköade elementet returneras.
Steg 3: Skapa en funktion för att visa elementen i den cirkulära bufferten
I det här avsnittet anropar vi funktionen showQueue() för att visa elementen i den cirkulära kön 'NewArr'.
void MyQueue::showQueue ( ){
om ( huvud == - 1 )
{
cout << ' \n Kön är ledig' ;
lämna tillbaka ;
}
cout << ' \n Cirkulära köelement: ' ;
om ( svans > = huvud )
{
för ( int i = huvud ; i < = svans ; i++ )
cout << NewArr [ i ] << ' ' ;
}
annan
{
för ( int i = huvud ; i < Qsize; i++ )
cout << NewArr [ i ] << ' ' ;
för ( int i = 0 ; i < = svans ; i++ )
cout << NewArr [ i ] << ' ' ;
}
}
Köns tomma status verifieras först. En indikation på att den cirkulära kön är ledig visas om kön är ledig. Annars kommer funktionen att visa elementen i den cirkulära kön. För detta definierar vi 'om'-satsen där vi har svansen som är större än eller lika med huvudet. Detta villkor är inställt för att hantera ärendet när den cirkulära kön inte är klar.
I det här fallet använder vi 'för'-loopen för att iterera från huvud till svans och skriva ut värdena för den cirkulära kön. Nästa fall är där den cirkulära kön är klar. För detta kontrollerar vi med 'om'-tillståndet där svansen är mindre än huvudet. Sedan måste vi använda två loopar där den första itererar från huvudet till slutet av kön och den andra itererar från början av svansen.
Steg 4: Skapa Main()-funktionen för programmet Circular Queue
Slutligen skapar vi programmets main() funktion där vi infogar fem heltal i den cirkulära kön och visar köns heltal. Efter det visar vi de borttagna heltal från den cirkulära kön genom att anropa funktionen dequeue(). Efter att ha tagit bort några element, fyller vi kön igen genom att infoga de nya elementen med hjälp av enqueue()-funktionen.
int main ( ){
MyQueue det ( 5 ) ;
// Infoga element i Cirkulär kö
que.enQueue ( elva ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( femton ) ;
// Visa element närvarande i Cirkulär kö
que.showQueue ( ) ;
// Ta bort element från Circular Queue
cout << ' \n Borttaget element = ' << que.deQueue ( ) ;
cout << ' \n Borttaget element = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
lämna tillbaka 0 ;
}
Produktion:
Resultaten av den cirkulära köimplementeringen visas på C++-promptskärmen.
Slutsats
Sammanfattningsvis förklaras det cirkulära buffertämnet djupt i den här artikeln. Vi skapade den cirkulära bufferten först, förklarade sedan hur man tar bort från den cirkulära kön och visade sedan elementen i cirkuläret i C++.