Ringipuhver või ümmargune järjekord on tavalise järjekorra täiustatud versioon, kus viimane indeks ja sabaindeks on ühendatud ringikujulises struktuuris. C++ tsirkulaarne puhver järgib kahte meetodit: enqueue() ja dequeue(). Nende meetodite alusel teostame ringpuhvri või ringjärjekorra toimingu.
- Meetod enqueue() kontrollib, kas puhver on täidetud. Muul juhul veenduge, et lõpuindeks on viimane. Kui jah, siis määrake sabaväärtuseks 0. Kui ei, suurendage saba väärtust selle indeksi väärtuse võrra.
- Funktsioon dequeue() võtab väärtuse ringjärjekorra eesmisest indeksist. Kui järjekord on tühi, kuvatakse teade, et tühi järjekord. Vastasel juhul saab see viimase väärtuse ja kustutab selle järjekorrast.
Programm ümmarguse puhvri juurutamiseks C++ keeles
Järgides nimetatud kahte meetodit, rakendame ringikujulise puhvri C++ keeles. Vaatleme kõiki samme ringikujulise järjekorra rakendamiseks C++-s.
#include
kasutades nimeruumi std;
struktureerida MyQueue
{
int pea , saba ;
int Qsize;
int * UusArr;
MyQueue ( int nr ) {
pea = saba = -1 ;
Qsize = suurus;
UusArr = uus int [ s ] ;
}
tühine järjekord ( int val ) ;
int deQueue ( ) ;
tühi showQueue ( ) ;
} ;
Alustades koodiga, loome esmalt pea- ja sabamuutujate lähtestamiseks struktuuri 'MyQueue'. Pea muutuja tähistab eesmisi indekseid ja saba esindab massiivi tagumist tagumist indeksit. Pärast seda määratakse ringikujulise järjekorra suurus, mida tähistatakse muutujaga 'Qsize'.
Seejärel määratleme dünaamiliselt eraldatud massiivi 'NewArr', mis salvestab ringikujulise järjekorra väärtused. Järgmisena kutsume välja MyQueue(), mis on konstruktor, ja edastame ringikujulise järjekorra suuruse parameetri 'sz'. Konstruktoris MyQueue() omistame pea- ja sabaosutitele väärtuse '-1'. See negatiivne väärtus näitab, et järjekord on praegu tühi. Edasi liikudes määrame väärtuse 'sz', mis tähistab ringikujulise järjekorra suurust. 'NewArr' ringikujuline järjekord seatakse uue märksõnaga, et luua täisarvude massiiv määratud 'sz' suuruses.
Seejärel määratleme funktsioonid enQueue() ja dequeue(). Enqueue() lisab väärtused määratletud ringikujulisse järjekorda sabast. Kuid funktsioon dequeue() elimineerib ringikujulise järjekorra peas olevad elemendid. Liikmefunktsioon showQueue() kuvab ringikujulise järjekorra väärtused.
1. samm: looge funktsioon elementide sisestamiseks ringikujulisse puhvrisse
Varasemas etapis määrasime klassi, kus privaatliikmed lähtestatakse ja privaatliikme funktsioonid seatakse ringikujulise järjekorra rakendamiseks. Nüüd seadsime funktsiooni ringikujulise järjekorra loomiseks ja väärtused sisestame algoritmi abil ringikujulise järjekorra sisse.
tühine MyQueue::enQueue ( int val ){
kui ( ( pea == 0 && saba == Qsize - 1 ) || ( saba == ( pea - 1 ) % ( Qsize - 1 ) ) )
{
cout << ' \n Järjekord on täis' ;
tagasi ;
}
muidu kui ( pea == - 1 )
{
pea = saba = 0 ;
UusArr [ saba ] = val;
}
muidu kui ( saba == Qsize - 1 && pea ! = 0 )
{
saba = 0 ;
UusArr [ saba ] = val;
}
muidu {
saba ++;
UusArr [ saba ] = val;
}
}
Siin kutsume funktsiooni 'enqueue()' klassist 'MyQueue', et lisada element ringikujulisse järjekorda, kui järjekord on tühi või allavoolu. Funktsioon 'enqueue()' edastatakse parameetriga 'val' ja väärtus sisestatakse ringikujulise järjekorra sabast. Seadsime tingimuse 'if-else', et lisada väärtused selle jaoks ringikujulisse järjekorda. Esimene 'if' lause, mis on 'if ((pea == 0 && saba == Qsize – 1) || (tail == (pea - 1) % (Qsize - 1)))' kontrollib kahte tingimust, kas pea on ringikujulise järjekorra alguspositsioonis ja saba on lõppasendis. Seejärel kontrollib see, kas saba on pea tagumises asendis ühes asendis. Kui mõni neist tingimustest on täidetud, ei ole järjekord tühi ja viip genereerib teate.
Järgmisena on meil tingimus „muu-kui”, mis tuvastab, kas järjekord on tühi. Kui jah, lisatakse väärtus järjekorda. Kuna pea väärtus on võrdne -1-ga, näitab see, et järjekord on tühi ja väärtus tuleb sisestada ringikujulisse järjekorda. Selleks määrame pea ja saba võrdseks 0-ga. Seejärel sisestame sabapositsiooni väärtuse 'NewArr' ringikujulisse järjekorda.
Seejärel on meil kolmas 'muu-kui' tingimus, mis kontrollib, kas saba on järjekorra viimasel positsioonil ja pea pole järjekorra alguspositsioon. See tingimus kehtib siis, kui saba jõuab lõpuni ja algusasendis on veel ruumi. Selleks peame määrama pea 0-le ja element lisatakse sabaasendist. Lõpuks, kui kõik antud tingimused ei ole täidetud, pole järjekord tühi ega täis. Sel juhul suurendame saba 1 võrra ja väärtus lisatakse uuest sabaasendist.
2. samm: looge funktsioon elementide kustutamiseks ringpuhvrist
Eelmise koodi seadsime elemendid ringikujulisesse järjekorda looma ja sisestama funktsiooni enqueue() abil. Nüüd määratleme elementide eemaldamise ümmargusest puhvrist, kui see ületab.
int MyQueue::deQueue ( ){
kui ( pea == - 1 )
{
cout << ' \n Järjekord on vaba' ;
tagasi INT_MIN;
}
int MyData = UusArr [ pea ] ;
UusArr [ pea ] = -1 ;
kui ( pea == saba )
{
pea = -1 ;
saba = -1 ;
}
muidu kui ( pea == Qsize - 1 )
pea = 0 ;
muidu
pea ++;
tagasi MyData;
}
Antud koodis kutsume elemendi peaindeksist eemaldamiseks välja funktsiooni dequeue() klassist “Myqueue”. Seega on meil „if”-lause, mis kontrollib, kas järjekord on tühi. Pea on seatud väärtusega '-1', mis tähistab tühja järjekorda. Genereeritakse teade, et järjekord on tühi, ja seejärel tagastatakse INT_MIN, mis on int konstantne minimaalne väärtus. „if”-lause määrab, kas järjekord on hõivamata. Selleks defineerime muutuja 'MyData' ja määrame elemendi väärtuse järjekorra päis. Seejärel määrame pea positsioonile -1, mis näitab, et see väärtus on järjekorrast eemaldatud. Pärast seda kontrollime, kas pea ja saba on võrdsed või mitte. Kui mõlemad on võrdsed, omistame mõlemale väärtuse '-1', mis tähistab tühja ringikujulist järjekorda. Lõpuks kontrollime, kas dequeue() toimib, kui pea on järjekorra viimases indeksis. Selleks määrame selle väärtusega '0', mis liigub massiivi alguses ringi. Kui ükski antud tingimustest ei ole tõene, suurendatakse pea väärtust ja tagastatakse järjekorrast eemaldatud element.
3. samm: looge funktsioon ringikujulise puhvri elementide kuvamiseks
Selles jaotises kutsume funktsiooni showQueue(), et kuvada 'NewArr' ringikujulise järjekorra elemendid.
tühine MyQueue::showQueue ( ){
kui ( pea == - 1 )
{
cout << ' \n Järjekord on vaba' ;
tagasi ;
}
cout << ' \n Ringikujulise järjekorra elemendid: ' ;
kui ( saba > = pea )
{
jaoks ( int i = pea ; i < = saba ; i++ )
cout << UusArr [ i ] << ' ' ;
}
muidu
{
jaoks ( int i = pea ; i < Qsize; i++ )
cout << UusArr [ i ] << ' ' ;
jaoks ( int i = 0 ; i < = saba ; i++ )
cout << UusArr [ i ] << ' ' ;
}
}
Esmalt kontrollitakse järjekorra tühi olekut. Kui järjekord on vaba, kuvatakse märge selle kohta, et ringjärjekord on vaba. Vastasel juhul näitab funktsioon ringikujulise järjekorra elemente. Selleks defineerime „kui”-lause, kus meie saba on peast suurem või sellega võrdne. See tingimus on seatud käsitlema juhu, kui ringjärjekord pole lõpetatud.
Sel juhul kasutame tsüklit 'for', et itereerida pealaest sabani ja printida ringikujulise järjekorra väärtused. Järgmine juhtum on see, kui ringikujuline järjekord on täidetud. Selleks kontrollime tingimust 'kui', kus saba on peast väiksem. Seejärel peame kasutama kahte tsüklit, kus esimene itereerub järjekorra algusest lõpuni ja teine itereerub saba algusest.
4. samm: looge ringikujulise järjekorra programmi funktsioon Main().
Viimasena loome programmi main() funktsiooni, kus sisestame ringikujulisse järjekorda viis täisarvu ja kuvame järjekorra täisarvud. Pärast seda näitame ringjärjekorrast kustutatud täisarve, kutsudes välja funktsiooni dequeue(). Pärast mõne elemendi järjekorrast eemaldamist täidame järjekorra uuesti, lisades uued elemendid funktsiooni enqueue() abil.
int main ( ){
MyQueue see ( 5 ) ;
// Elementide sisestamine sisse Ringi järjekord
que.enQueue ( üksteist ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( viisteist ) ;
// Kuvaelemendid olemas sisse Ringi järjekord
que.showQueue ( ) ;
// Elementide kustutamine ringjärjekorrast
cout << ' \n Kustutatud element = ' << que.deQueue ( ) ;
cout << ' \n Kustutatud element = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
tagasi 0 ;
}
Väljund:
Ringikujulise järjekorra rakendamise tulemused kuvatakse C++ viipakuval.
Järeldus
Kokkuvõtteks võib öelda, et selles artiklis on ümmarguse puhvri teemat põhjalikult selgitatud. Esmalt lõime ringikujulise puhvri, seejärel selgitasime, kuidas ringikujulisest järjekorrast kustutada, ja seejärel kuvasime ringikujulise elemendid C++ keeles.