Kruhová vyrovnávacia pamäť alebo Kruhový front je pokročilá verzia normálneho frontu, kde sú posledný index a koncový index spojené do kruhovej štruktúry. Kruhová vyrovnávacia pamäť v C++ používa dve metódy: enqueue() a dequeue(). Na základe týchto metód vykonávame operáciu kruhovej vyrovnávacej pamäte alebo kruhovej fronty.
- Metóda enqueue() kontroluje, či je vyrovnávacia pamäť naplnená. V opačnom prípade skontrolujte, či je koncový index posledný. Ak áno, nastavte koncovú hodnotu na 0. Ak nie, zvýšte koncovú hodnotu o hodnotu pri tomto indexe.
- Funkcia dequeue() preberá hodnotu z predného indexu v kruhovom fronte. Ak je front prázdny, správa zobrazí tento prázdny front. V opačnom prípade získa poslednú hodnotu a vymaže ju z frontu.
Program na implementáciu kruhovej vyrovnávacej pamäte v C++
Podľa uvedených dvoch metód implementujeme kruhovú vyrovnávaciu pamäť v C++. Pozrime sa na všetky kroky pre implementáciu kruhového frontu v C++.
#include
pomocou menného priestoru std;
struct MyQueue
{
int hlavu , chvost ;
int Qsize;
int * NewArr;
MyQueue ( int č ) {
hlavu = chvost = -1 ;
Qsize = veľkosť;
NewArr = nový int [ s ] ;
}
void enQueue ( int val ) ;
int deQueue ( ) ;
void showQueue ( ) ;
} ;
Počnúc kódom najprv vytvoríme štruktúru „MyQueue“ na inicializáciu premenných hlavy a chvosta. Premenná hlava predstavuje predné indexy a chvost predstavuje zadné zadné indexy poľa. Potom je definovaná veľkosť kruhového frontu, označená premennou „Qsize“.
Potom definujeme dynamicky pridelené pole „NewArr“, ktoré ukladá hodnoty kruhového frontu. Ďalej zavoláme funkciu MyQueue(), ktorá je konštruktorom, a odošleme parameter „sz“ pre veľkosť kruhovej fronty. Vo vnútri konštruktora MyQueue() priraďujeme hodnotu „-1“ ukazovateľom hlavy a chvosta. Táto záporná hodnota znamená, že front je teraz prázdny. Vpred priradíme hodnotu „sz“, ktorá predstavuje veľkosť kruhového radu. Kruhový rad „NewArr“ je nastavený s novým kľúčovým slovom na vytvorenie poľa celých čísel v rámci špecifikovanej veľkosti „sz“.
Potom definujeme funkcie enQueue() a dequeue(). Enqueue() vloží hodnoty do definovaného kruhového frontu z konca. Prvky v hlave kruhového frontu sú však eliminované funkciou dequeue(). Členská funkcia showQueue() zobrazuje hodnoty kruhového frontu.
Krok 1: Vytvorte funkciu na vloženie prvkov do kruhovej vyrovnávacej pamäte
V predchádzajúcom kroku sme nastavili triedu, v ktorej sú inicializovaní súkromní členovia a funkcie súkromných členov sú nastavené na implementáciu kruhového frontu. Teraz nastavíme funkciu na vytvorenie kruhového radu a pomocou algoritmu vložíme hodnoty do kruhového radu.
void MyQueue::enQueue ( int val ){
ak ( ( hlavu == 0 && chvost == Veľkosť Q - 1 ) || ( chvost == ( hlavu - 1 ) % ( Veľkosť Q - 1 ) ) )
{
cout << ' \n Front je naplnený' ;
vrátiť ;
}
inak ak ( hlavu == - 1 )
{
hlavu = chvost = 0 ;
NewArr [ chvost ] = val;
}
inak ak ( chvost == Veľkosť Q - 1 && hlavu ! = 0 )
{
chvost = 0 ;
NewArr [ chvost ] = val;
}
inak {
chvost ++;
NewArr [ chvost ] = val;
}
}
Tu voláme funkciu „enqueue()“ z triedy „MyQueue“, aby sme vložili prvok do kruhového frontu, ak je front prázdny alebo nedostatočný. Funkcia „enqueue()“ sa odovzdá s parametrom „val“ a vloží sa hodnota z konca kruhového frontu. Nastavili sme podmienku „if-else“ na vloženie hodnôt do kruhového frontu. Prvý výraz „if“, ktorým je „ak ((hlava == 0 && chvost == Veľkosť Q – 1) || (chvost == (hlava – 1) % (Veľkosť Q – 1)))“ kontroluje dve podmienky, či hlava je na začiatku pozície a chvost je na konci pozície kruhového radu. Potom skontroluje, či je chvost v jednej polohe v zadnej časti hlavy. Ak je splnená niektorá z týchto podmienok, front nie je prázdny a výzva vygeneruje správu.
Ďalej máme podmienku „else-if“, ktorá identifikuje, či je front prázdny. Ak áno, hodnota sa vloží do frontu. Keďže hlavička sa rovná -1, znamená to, že front je prázdny a hodnotu je potrebné vložiť do kruhového radu. Na tento účel nastavíme hlavu a chvost na 0. Potom vložíme hodnotu z polohy chvosta do kruhového radu „NewArr“.
Potom máme našu tretiu podmienku „else-if“, ktorá kontroluje, či je chvost na poslednej pozícii frontu a či hlava nie je počiatočnou pozíciou frontu. Táto podmienka platí, keď chvost dosiahne koniec a východisková pozícia má ešte priestor. Na to musíme nastaviť hlavu na 0 a prvok sa pridáva z polohy chvosta. Nakoniec, ak nie sú splnené všetky dané podmienky, rad nie je prázdny ani plný. V tomto prípade zvýšime chvost o 1 a hodnota sa pripočíta z novej polohy chvosta.
Krok 2: Vytvorte funkciu na odstránenie prvkov z kruhovej vyrovnávacej pamäte
Predchádzajúci kód nastavíme na vytváranie a vkladanie prvkov do kruhového frontu pomocou funkcie enqueue(). Teraz definujeme implementáciu odstránenia prvkov z kruhovej vyrovnávacej pamäte, ak pretečie.
int MyQueue::deQueue ( ){
ak ( hlavu == - 1 )
{
cout << ' \n Front je voľný' ;
vrátiť INT_MIN;
}
int MyData = NewArr [ hlavu ] ;
NewArr [ hlavu ] = -1 ;
ak ( hlavu == chvost )
{
hlavu = -1 ;
chvost = -1 ;
}
inak ak ( hlavu == Veľkosť Q - 1 )
hlavu = 0 ;
inak
hlavu ++;
vrátiť MyData;
}
V danom kóde zavoláme funkciu dequeue() z triedy „Myqueue“, aby sme odstránili prvok z indexu hlavy. Máme teda príkaz „if“, ktorý kontroluje, či je front prázdny. Hlava je nastavená na hodnotu „-1“, ktorá predstavuje prázdny front. Vygeneruje sa správa, že front je prázdny a potom vráti INT_MIN, čo je konštantná minimálna hodnota pre int. Príkaz „if“ určuje, či je front neobsadený. Na tento účel definujeme premennú „MyData“ a nastavíme hodnotu prvku na začiatku fronty. Potom nastavíme hlavu na pozíciu -1, čo znamená, že táto hodnota je odstránená z frontu. Potom skontrolujeme, či sú hlava a chvost rovnaké alebo nie. Ak sú obe rovnaké, obom priradíme hodnotu „-1“, ktorá predstavuje prázdny kruhový rad. Nakoniec skontrolujeme, či funkcia dequeue() funguje, ak je hlava na poslednom indexe frontu. Na tento účel sme ho nastavili na hodnotu „0“, ktorá sa zacyklí na začiatku poľa. Ak nie je splnená žiadna z daných podmienok, hodnota hlavy sa zvýši a vráti sa vyradený prvok.
Krok 3: Vytvorte funkciu na zobrazenie prvkov kruhovej vyrovnávacej pamäte
V tejto časti zavoláme funkciu showQueue() na zobrazenie prvkov kruhového frontu „NewArr“.
void MyQueue::showQueue ( ){
ak ( hlavu == - 1 )
{
cout << ' \n Front je voľný' ;
vrátiť ;
}
cout << ' \n Prvky kruhového frontu: ' ;
ak ( chvost > = hlavu )
{
pre ( int i = hlavu ; i < = chvost ; i++ )
cout << NewArr [ i ] << '' ;
}
inak
{
pre ( int i = hlavu ; i < veľkosť Q; i++ )
cout << NewArr [ i ] << '' ;
pre ( int i = 0 ; i < = chvost ; i++ )
cout << NewArr [ i ] << '' ;
}
}
Najprv sa overí prázdny stav frontu. Ak je rad voľný, zobrazí sa indikácia, že kruhový rad je voľný. V opačnom prípade funkcia zobrazí prvky kruhového frontu. Na tento účel definujeme výraz „ak“, kde máme chvost väčší alebo rovný hlave. Táto podmienka je nastavená na zvládnutie prípadu, keď kruhový rad nie je dokončený.
V tomto prípade používame cyklus „for“ na iteráciu od hlavy po koniec a tlač hodnôt kruhového frontu. Ďalším prípadom je, keď je kruhový rad dokončený. Na to kontrolujeme pomocou podmienky „ak“, kde je chvost menší ako hlava. Potom musíme použiť dve slučky, kde prvá iteruje od hlavy po koniec frontu a druhá od začiatku konca.
Krok 4: Vytvorte funkciu Main() programu Circular Queue
Nakoniec vytvoríme funkciu main() programu, kde vložíme päť celých čísel do kruhového frontu a zobrazíme celé čísla z frontu. Potom zobrazíme vymazané celé čísla z kruhového frontu zavolaním funkcie dequeue(). Po vyradení niekoľkých prvkov front opäť naplníme vložením nových prvkov pomocou funkcie enqueue().
int main ( ){
MyQueue to ( 5 ) ;
// Vkladanie prvkov v Kruhový rad
que.enQueue ( jedenásť ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( pätnásť ) ;
// Prítomné zobrazovacie prvky v Kruhový rad
que.showQueue ( ) ;
// Odstraňovanie prvkov z kruhového frontu
cout << ' \n Odstránený prvok = ' << que.deQueue ( ) ;
cout << ' \n Odstránený prvok = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
vrátiť 0 ;
}
Výkon:
Výsledky implementácie kruhového frontu sú zobrazené na obrazovke s výzvou C++.
Záver
Na záver je v tomto článku podrobne vysvetlená téma kruhovej vyrovnávacej pamäte. Najprv sme vytvorili kruhovú vyrovnávaciu pamäť, potom sme vysvetlili, ako odstrániť z kruhovej fronty, a potom sme prvky kruhovej pamäte zobrazili v C++.