Circular buffer arba Circular queue yra išplėstinė įprastos eilės versija, kurioje paskutinis indeksas ir uodegos indeksas yra sujungti į apskritą struktūrą. Apvalus buferis C++ veikia dviem būdais: enqueue () ir dequeue (). Remdamiesi šiais metodais atliekame apskrito buferio arba žiedinės eilės operaciją.
- enqueue() metodas patikrina, ar buferis užpildytas. Kitu atveju patikrinkite, ar pabaigos indeksas yra paskutinis. Jei taip, nustatykite uodegos reikšmę į 0. Jei ne, padidinkite uodegos reikšmę to indekso reikšme.
- Funkcija dequeue() paima reikšmę iš priekinio indekso žiedinėje eilėje. Jei eilė tuščia, bus rodomas pranešimas, kad tuščia eilė. Priešingu atveju jis gauna paskutinę reikšmę ir ištrina ją iš eilės.
Programa, skirta įdiegti cirkuliacinį buferį C++
Vadovaudamiesi dviem minėtais metodais, mes įdiegiame apskritą buferį C++. Apsvarstykime visus žiedinės eilės diegimo veiksmus C++.
#include
naudojant vardų sritį std;
sukurti MyQueue
{
tarpt galva , uodega ;
int Qsize;
tarpt * NewArr;
„MyQueue“. ( int Nr ) {
galva = uodega = -1 ;
Qsize = dydis;
NewArr = naujas tarpt [ s ] ;
}
tuščia eilė ( int val ) ;
int deQueue ( ) ;
tuščias šou eilė ( ) ;
} ;
Pradėdami nuo kodo, pirmiausia sukuriame „MyQueue“ struktūrą, kad inicijuotume galvos ir uodegos kintamuosius. Galvos kintamasis žymi priekinius indeksus, o uodega – masyvo užpakalinius indeksus. Po to apibrėžiamas apskritos eilės dydis, žymimas kintamuoju „Qsize“.
Tada apibrėžiame dinamiškai paskirstytą „NewArr“ masyvą, kuriame saugomos žiedinės eilės reikšmės. Tada iškviečiame MyQueue (), kuris yra konstruktorius, ir perduodame apskritimo eilės dydžio parametrą „sz“. „MyQueue()“ konstruktoriuje galvos ir uodegos rodyklėms priskiriame „-1“ reikšmę. Ši neigiama reikšmė rodo, kad eilė dabar tuščia. Eidami į priekį, priskiriame „sz“ reikšmę, kuri parodo apskritos eilės dydį. „NewArr“ apskritimo eilė nustatoma naudojant naują raktinį žodį, kad būtų sukurtas nurodyto „sz“ dydžio sveikųjų skaičių masyvas.
Tada apibrėžiame enQueue() ir dequeue() funkcijas. enqueue () įterpia reikšmes į apibrėžtą apskritą eilę iš uodegos. Tačiau žiedinės eilės antraštėje esantys elementai pašalinami naudojant dequeue() funkciją. Funkcija showQueue() nario rodo apskritos eilės reikšmes.
1 veiksmas: sukurkite elementų įterpimo į apskritą buferį funkciją
Ankstesniame žingsnyje nustatėme klasę, kurioje inicijuojami privatūs nariai, o privataus nario funkcijos nustatomos taip, kad būtų įdiegta apskrita eilė. Dabar nustatome funkciją sukurti apskritą eilę ir įterpti reikšmes į apskritą eilę naudodami algoritmą.
negalioja MyQueue::enQueue ( int val ){
jeigu ( ( galva == 0 && uodega == Qsize - 1 ) || ( uodega == ( galva - 1 ) % ( Qsize - 1 ) ) )
{
cout << “ \n Eilė užpildyta' ;
grąžinti ;
}
Kitas jeigu ( galva == - 1 )
{
galva = uodega = 0 ;
NaujasArr [ uodega ] = val;
}
Kitas jeigu ( uodega == Qsize - 1 && galva ! = 0 )
{
uodega = 0 ;
NaujasArr [ uodega ] = val;
}
Kitas {
uodega ++;
NaujasArr [ uodega ] = val;
}
}
Čia mes iškviečiame funkciją „enqueue()“ iš „MyQueue“ klasės, kad įterptume elementą į apskritą eilę, jei eilė tuščia arba perpildyta. Funkcija „enqueue()“ perduodama su parametru „val“ ir įterpiama reikšmė iš apskritos eilės galo. Mes nustatome sąlygą „jei-else“, kad įterptume reikšmes į apskritą eilę. Pirmasis „if“ teiginys, kuris yra „if ((galva == 0 && tail == Qsize – 1) || (uodega == (galva – 1) % (Qsize – 1)))“ patikrina dvi sąlygas, ar galva yra pradinėje padėtyje, o uodega yra apskritos eilės pabaigoje. Tada patikrinama, ar uodega yra vienoje padėtyje galvos gale. Jei įvykdoma kuri nors iš šių sąlygų, eilė nėra tuščia ir raginimas generuoja pranešimą.
Toliau turime sąlygą „else-if“, kuri nustato, ar eilė tuščia. Jei taip, reikšmė įterpiama į eilę. Kadangi antraštė yra lygi -1, tai rodo, kad eilė tuščia ir reikšmę reikia įterpti į apskritą eilę. Tam mes nustatome galvutę ir uodegą lygioms 0. Tada į „NewArr“ žiedinę eilę įterpiame reikšmę iš uodegos padėties.
Tada turime trečią sąlygą „else-if“, kuri patikrina, ar uodega yra paskutinėje eilės padėtyje, o galva nėra pradinė eilės padėtis. Ši sąlyga taikoma, kai uodega pasiekia galą ir pradinėje padėtyje dar yra vietos. Tam turime nustatyti galvą ties 0, o elementas pridedamas iš uodegos padėties. Galiausiai, jei netenkinamos visos nurodytos sąlygos, eilė nėra nei tuščia, nei pilna. Šiuo atveju uodegą padidiname 1, o vertė pridedama iš naujos uodegos padėties.
2 veiksmas: sukurkite funkciją, kad pašalintumėte elementus iš apskrito buferio
Mes nustatėme ankstesnį kodą, kad sukurtumėte ir įterptumėte elementus į apskritą eilę naudodami funkciją enqueue (). Dabar apibrėžiame elementų pašalinimo iš apskrito buferio įgyvendinimą, jei jis persipildo.
int MyQueue::deQueue ( ){
jeigu ( galva == - 1 )
{
cout << “ \n Eilė laisva' ;
grąžinti INT_MIN;
}
int MyData = NaujasArr [ galva ] ;
NaujasArr [ galva ] = -1 ;
jeigu ( galva == uodega )
{
galva = -1 ;
uodega = -1 ;
}
Kitas jeigu ( galva == Qsize - 1 )
galva = 0 ;
Kitas
galva ++;
grąžinti MyData;
}
Pateiktame kode mes iškviečiame funkciją dequeue () iš „Myqueue“ klasės, kad pašalintume elementą iš pagrindinio indekso. Taigi, turime sakinį „if“, kuris patikrina, ar eilė tuščia. Antraštė nustatoma su „-1“ reikšme, kuri reiškia tuščią eilę. Sugeneruojamas pranešimas, kad eilė tuščia, tada grąžinama INT_MIN, kuri yra pastovi minimali int reikšmė. Teiginys „if“ nustato, ar eilė neužimta. Tam mes apibrėžiame „MyData“ kintamąjį ir nustatome elemento vertę eilės pradžioje. Tada nustatome galvutę į padėtį -1, kuri rodo, kad ši reikšmė pašalinta iš eilės. Po to patikriname, ar galva ir uodega yra vienodos, ar ne. Jei abu yra vienodi, abiem priskiriame „-1“ reikšmę, kuri reiškia tuščią apskritą eilę. Galiausiai patikriname, ar dequeue () veikia, jei antraštė yra paskutiniame eilės indekse. Tam nustatome reikšmę „0“, kuri sukasi masyvo pradžioje. Jei nė viena iš nurodytų sąlygų nėra teisinga, galvutės reikšmė padidinama ir grąžinamas elementas, kurio eilė buvo išbraukta.
3 veiksmas: sukurkite funkciją, rodančią apskrito buferio elementus
Šiame skyriuje mes vadiname funkciją showQueue(), kad būtų rodomi „NewArr“ žiedinės eilės elementai.
negalioja MyQueue::showQueue ( ){
jeigu ( galva == - 1 )
{
cout << “ \n Eilė laisva' ;
grąžinti ;
}
cout << “ \n Žiedinės eilės elementai: ' ;
jeigu ( uodega > = galva )
{
dėl ( int i = galva ; i < = uodega ; i++ )
cout << NaujasArr [ i ] << ' ' ;
}
Kitas
{
dėl ( int i = galva ; i < Qsize; i++ )
cout << NaujasArr [ i ] << ' ' ;
dėl ( int i = 0 ; i < = uodega ; i++ )
cout << NaujasArr [ i ] << ' ' ;
}
}
Pirmiausia patikrinama tuščios eilės būsena. Jei eilė laisva, rodomas nurodymas, kad apskrita eilė yra laisva. Priešingu atveju funkcija parodys apskritos eilės elementus. Tam mes apibrėžiame teiginį „jei“, kai mūsų uodega yra didesnė arba lygi galvai. Ši sąlyga nustatyta taip, kad būtų tvarkomas atvejis, kai žiedinė eilė neužbaigta.
Šiuo atveju naudojame kilpą „for“, kad kartotume nuo galvos iki galo ir atspausdintume apskritos eilės reikšmes. Kitas atvejis yra tada, kai apskrita eilė yra baigta. Norėdami tai padaryti, patikriname naudodamiesi sąlyga „jei“, kai uodega yra mažesnė už galvą. Tada turime naudoti dvi kilpas, kur pirmoji kartojasi nuo eilės pradžios iki pabaigos, o antroji – nuo uodegos pradžios.
4 veiksmas: sukurkite žiedinės eilės programos pagrindinę () funkciją
Galiausiai sukuriame programos main() funkciją, kurioje į apskritą eilę įterpiame penkis sveikuosius skaičius ir parodome sveikuosius eilės skaičius. Po to mes parodome ištrintus sveikuosius skaičius iš apskritos eilės, iškviesdami funkciją dequeue(). Ištraukę keletą elementų, eilę vėl užpildome įterpdami naujus elementus naudodami funkciją enqueue().
tarp pagrindinis ( ){
MyQueue that ( 5 ) ;
// Elementų įterpimas in Žiedinė eilė
que.enEilė ( vienuolika ) ;
que.enEilė ( 12 ) ;
que.enEilė ( 13 ) ;
que.enEilė ( 14 ) ;
que.enEilė ( penkiolika ) ;
// Pateikiami ekrano elementai in Žiedinė eilė
que.showQueue ( ) ;
// Elementai ištrinami iš žiedinės eilės
cout << “ \n Ištrintas elementas = ' << que.deQueue ( ) ;
cout << “ \n Ištrintas elementas = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enEilė ( 16 ) ;
que.enEilė ( 17 ) ;
que.enEilė ( 18 ) ;
que.showQueue ( ) ;
grąžinti 0 ;
}
Išvestis:
Apvalios eilės įgyvendinimo rezultatai rodomi C++ raginimo ekrane.
Išvada
Apibendrinant, šiame straipsnyje išsamiai paaiškinta apskrito buferio tema. Pirmiausia sukūrėme apskrito buferį, tada paaiškinome, kaip ištrinti iš apskritos eilės, o tada parodėme apskritimo elementus C++.