Kruhová vyrovnávací paměť nebo Kruhová fronta je pokročilá verze normální fronty, kde jsou poslední index a koncový index spojeny do kruhové struktury. Kruhová vyrovnávací paměť v C++ používá dvě metody: enqueue() a dequeue(). Na základě těchto metod provádíme operace kruhové vyrovnávací paměti nebo kruhové fronty.
- Metoda enqueue() kontroluje, zda je vyrovnávací paměť plná. V opačném případě ověřte, že koncový index je poslední. Pokud ano, nastavte hodnotu ocasu na 0. Pokud ne, zvyšte hodnotu ocasu o hodnotu na daném indexu.
- Funkce dequeue() přebírá hodnotu z předního indexu v kruhové frontě. Pokud je fronta prázdná, zobrazí se zpráva s prázdnou frontou. V opačném případě získá poslední hodnotu a odstraní ji z fronty.
Program pro implementaci kruhové vyrovnávací paměti v C++
Podle zmíněných dvou metod implementujeme kruhový buffer v C++. Podívejme se na všechny kroky pro implementaci kruhové fronty v C++.
#include
pomocí jmenného prostoru std;
struct MyQueue
{
int hlava , ocas ;
int Qsize;
int * NewArr;
MyQueue ( int no ) {
hlava = ocas = -1 ;
Qsize = velikost;
NewArr = nový int [ s ] ;
}
void enQueue ( int val ) ;
int deQueue ( ) ;
void showQueue ( ) ;
} ;
Počínaje kódem nejprve vytvoříme strukturu „MyQueue“ pro inicializaci proměnných head a tail. Proměnná head představuje přední indexy a koncová část představuje zadní zadní indexy pole. Poté je definována velikost kruhové fronty, označená proměnnou „Qsize“.
Poté definujeme dynamicky alokované pole „NewArr“, které ukládá hodnoty kruhové fronty. Dále zavoláme MyQueue(), což je konstruktor, a předáme parametr „sz“ pro velikost kruhové fronty. Uvnitř konstruktoru MyQueue() přiřadíme ukazatelům hlavy a paty hodnotu „-1“. Tato záporná hodnota znamená, že fronta je nyní prázdná. Vpřed přiřadíme hodnotu „sz“, která představuje velikost kruhové fronty. Kruhová fronta „NewArr“ je nastavena pomocí nového klíčového slova pro vytvoření pole celých čísel v rámci zadané velikosti „sz“.
Poté definujeme funkce enQueue() a dequeue(). Enqueue() vloží hodnoty do definované kruhové fronty z konce. Prvky v hlavě kruhové fronty jsou však eliminovány funkcí dequeue(). Členská funkce showQueue() zobrazuje hodnoty cyklické fronty.
Krok 1: Vytvořte funkci pro vložení prvků do kruhové vyrovnávací paměti
V předchozím kroku jsme nastavili třídu, kde jsou inicializováni soukromí členové a funkce soukromých členů jsou nastaveny tak, aby implementovaly cyklickou frontu. Nyní nastavíme funkci na vytvoření kruhové fronty a vložíme hodnoty do kruhové fronty pomocí algoritmu.
void MyQueue::enQueue ( int val ){
-li ( ( hlava == 0 && ocas == Velikost Q - 1 ) || ( ocas == ( hlava - 1 ) % ( Qsize - 1 ) ) )
{
cout << ' \n Fronta je plná' ;
vrátit se ;
}
jiný -li ( hlava == - 1 )
{
hlava = ocas = 0 ;
NewArr [ ocas ] = val;
}
jiný -li ( ocas == Velikost Q - 1 && hlava ! = 0 )
{
ocas = 0 ;
NewArr [ ocas ] = val;
}
jiný {
ocas ++;
NewArr [ ocas ] = val;
}
}
Zde zavoláme funkci „enqueue()“ z třídy „MyQueue“, abychom vložili prvek do kruhové fronty, pokud je fronta prázdná nebo podtečená. Funkce „enqueue()“ se předá s parametrem „val“ a vloží hodnotu z konce kruhové fronty. Za tímto účelem jsme nastavili podmínku „if-else“, abychom vložili hodnoty do kruhové fronty. První příkaz „if“, který je „if ((hlava == 0 && ocas == velikost Q – 1) || (ocas == (hlava – 1) % (velikost Q – 1)))“ kontroluje dvě podmínky, zda hlava je na počáteční pozici a ocas je na koncové pozici kruhové fronty. Poté zkontroluje, zda je ocas v jedné poloze v zadní části hlavy. Pokud je některá z těchto podmínek splněna, fronta není prázdná a výzva vygeneruje zprávu.
Dále máme podmínku „else-if“, která identifikuje, zda je fronta prázdná. Pokud ano, hodnota se vloží do fronty. Protože je hlavička udržována na hodnotě -1, znamená to, že fronta je prázdná a hodnotu je třeba vložit do kruhové fronty. Za tímto účelem nastavíme hlavu a patu na 0. Poté vložíme hodnotu z pozice ocasu do kruhové fronty „NewArr“.
Pak máme třetí podmínku „jinak-li“, která kontroluje, zda je ocas na poslední pozici fronty a hlava není výchozí pozicí fronty. Tato podmínka platí, když ocas dosáhne konce a výchozí pozice má stále prostor. K tomu musíme nastavit hlavu na 0 a prvek se přidá z polohy ocasu. A konečně, pokud nejsou splněny všechny dané podmínky, fronta není ani prázdná, ani plná. V tomto případě zvýšíme ocas o 1 a hodnota se přičte z nové polohy ocasu.
Krok 2: Vytvořte funkci pro odstranění prvků z kruhové vyrovnávací paměti
Předchozí kód jsme nastavili tak, aby vytvářel a vkládal prvky do kruhové fronty pomocí funkce enqueue(). Nyní definujeme implementaci odstranění prvků z kruhové vyrovnávací paměti, pokud přeteče.
int MyQueue::deQueue ( ){
-li ( hlava == - 1 )
{
cout << ' \n Fronta je zdarma' ;
vrátit se INT_MIN;
}
int MyData = NewArr [ hlava ] ;
NewArr [ hlava ] = -1 ;
-li ( hlava == ocas )
{
hlava = -1 ;
ocas = -1 ;
}
jiný -li ( hlava == Velikost Q - 1 )
hlava = 0 ;
jiný
hlava ++;
vrátit se MojeData;
}
V daném kódu zavoláme funkci dequeue() ze třídy „Myqueue“, abychom odstranili prvek z indexu hlavy. Máme tedy příkaz „if“, který kontroluje, zda je fronta prázdná. Hlava je nastavena na hodnotu „-1“, která představuje prázdnou frontu. Vygeneruje se zpráva, že fronta je prázdná, a poté vrátí INT_MIN, což je konstantní minimální hodnota pro int. Příkaz „if“ určuje, zda je fronta neobsazena. Za tímto účelem definujeme proměnnou „MyData“ a nastavíme hodnotu prvku na začátek fronty. Potom nastavíme hlavu na pozici -1, což znamená, že tato hodnota je odstraněna z fronty. Poté zkontrolujeme, zda jsou hlava a ocas stejné nebo ne. Pokud jsou obě stejné, přiřadíme oběma hodnotu „-1“, která představuje prázdnou kruhovou frontu. Nakonec zkontrolujeme, zda funkce dequeue() funguje, pokud je hlava na posledním indexu fronty. Za tímto účelem jsme jej nastavili na hodnotu „0“, která se bude opakovat na začátku pole. Pokud není splněna žádná z daných podmínek, hodnota hlavy se zvýší a vrátí se vyřazený prvek.
Krok 3: Vytvořte funkci pro zobrazení prvků kruhové vyrovnávací paměti
V této části zavoláme funkci showQueue() k zobrazení prvků kruhové fronty „NewArr“.
void MyQueue::showQueue ( ){
-li ( hlava == - 1 )
{
cout << ' \n Fronta je zdarma' ;
vrátit se ;
}
cout << ' \n Prvky kruhové fronty: ' ;
-li ( ocas > = hlava )
{
pro ( int i = hlava ; i < = ocas ; i++ )
cout << NewArr [ i ] << '' ;
}
jiný
{
pro ( int i = hlava ; i < Qsize; i++ )
cout << NewArr [ i ] << '' ;
pro ( int i = 0 ; i < = ocas ; i++ )
cout << NewArr [ i ] << '' ;
}
}
Nejprve se ověří prázdný stav fronty. Pokud je fronta volná, zobrazí se indikace, že kruhová fronta je volná. V opačném případě funkce zobrazí prvky kruhové fronty. Za tímto účelem definujeme příkaz „if“, kde máme ocas, který je větší nebo roven hlavě. Tato podmínka je nastavena tak, aby zvládla případ, kdy není cyklická fronta dokončena.
V tomto případě použijeme smyčku „for“ k iteraci od hlavy k patě a vytiskneme hodnoty kruhové fronty. Dalším případem je dokončení kruhové fronty. Za tímto účelem kontrolujeme pomocí podmínky „if“, kdy je ocas menší než hlava. Pak musíme použít dvě smyčky, kde první iteruje od hlavy ke konci fronty a druhá od začátku konce.
Krok 4: Vytvořte funkci Main() programu Circular Queue
Nakonec vytvoříme funkci main() programu, kde vložíme pět celých čísel do kruhové fronty a zobrazíme celá čísla fronty. Poté zobrazíme smazaná celá čísla z kruhové fronty voláním funkce dequeue(). Po vyřazení několika prvků frontu znovu naplníme vložením nových prvků pomocí funkce enqueue().
int main ( ){
MyQueue to ( 5 ) ;
// Vkládání prvků v Kruhová fronta
que.enQueue ( jedenáct ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( patnáct ) ;
// Přítomny zobrazovací prvky v Kruhová fronta
que.showQueue ( ) ;
// Odstranění prvků z kruhové fronty
cout << ' \n Smazaný prvek = ' << que.deQueue ( ) ;
cout << ' \n Smazaný prvek = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
vrátit se 0 ;
}
Výstup:
Výsledky implementace kruhové fronty jsou zobrazeny na obrazovce příkazového řádku C++.
Závěr
Na závěr je v tomto článku podrobně vysvětleno téma kruhové vyrovnávací paměti. Nejprve jsme vytvořili kruhovou vyrovnávací paměť, pak jsme vysvětlili, jak odstranit z kruhové fronty, a poté jsme prvky kruhové zobrazili v C++.