Krožni medpomnilnik ali krožna čakalna vrsta je napredna različica običajne čakalne vrste, kjer sta zadnji indeks in repni indeks povezana v krožno strukturo. Krožni medpomnilnik v C++ sledi dvema metodama: enqueue() in dequeue(). Na podlagi teh metod izvajamo operacijo krožnega medpomnilnika ali krožne čakalne vrste.
- Metoda enqueue() preveri, ali je vmesni pomnilnik napolnjen. V nasprotnem primeru preverite, ali je končni indeks zadnji. Če je tako, nastavite vrednost repa na 0. Če ni, povečajte vrednost repa za vrednost pri tem indeksu.
- Funkcija dequeue() vzame vrednost iz sprednjega indeksa v krožni čakalni vrsti. Če je čakalna vrsta prazna, bo to prazno čakalno vrsto prikazalo sporočilo. V nasprotnem primeru dobi zadnjo vrednost in jo izbriše iz čakalne vrste.
Program za implementacijo krožnega medpomnilnika v C++
Po omenjenih dveh metodah implementiramo krožni medpomnilnik v C++. Oglejmo si vse korake za implementacijo krožne čakalne vrste v C++.
#include
uporaba imenskega prostora std;
struct MyQueue
{
int glavo , rep ;
int Qsize;
int * NewArr;
MyQueue ( int št ) {
glavo = rep = -1 ;
Qsize = velikost;
NewArr = novo int [ s ] ;
}
void enQueue ( int val ) ;
int deQueue ( ) ;
void showQueue ( ) ;
} ;
Začenši s kodo, najprej ustvarimo strukturo »MyQueue« za inicializacijo spremenljivk head in tail. Spremenljivka glava predstavlja sprednje indekse, rep pa zadnje zadnje indekse niza. Po tem se določi velikost krožne čakalne vrste, ki jo označuje spremenljivka 'Qsize'.
Nato definiramo dinamično dodeljeno matriko »NewArr«, ki shranjuje vrednosti krožne čakalne vrste. Nato pokličemo MyQueue(), ki je konstruktor, in posredujemo parameter »sz« za velikost krožne čakalne vrste. Znotraj konstruktorja MyQueue() dodelimo vrednost »-1« kazalcema glave in repa. Ta negativna vrednost pomeni, da je čakalna vrsta zdaj prazna. Če gremo naprej, dodelimo vrednost 'sz', ki predstavlja velikost krožne čakalne vrste. Krožna čakalna vrsta »NewArr« je nastavljena z novo ključno besedo za ustvarjanje niza celih števil v podani velikosti »sz«.
Nato definiramo funkciji enQueue() in dequeue(). Enqueue() vstavi vrednosti v definirano krožno čakalno vrsto iz repa. Vendar pa elemente v glavi krožne čakalne vrste odstrani funkcija dequeue(). Članska funkcija showQueue() prikaže vrednosti krožne čakalne vrste.
1. korak: Ustvarite funkcijo za vstavljanje elementov v krožni medpomnilnik
V prejšnjem koraku smo nastavili razred, kjer so zasebni člani inicializirani in so funkcije zasebnega člana nastavljene za izvajanje krožne čakalne vrste. Zdaj smo nastavili funkcijo za ustvarjanje krožne čakalne vrste in z algoritmom vstavili vrednosti znotraj krožne čakalne vrste.
void MyQueue::enQueue ( int val ){
če ( ( glavo == 0 && rep == Qsize - 1 ) || ( rep == ( glavo - 1 ) % ( Qsize - 1 ) ) )
{
cout << ' \n Čakalna vrsta je zapolnjena' ;
vrnitev ;
}
drugače če ( glavo == - 1 )
{
glavo = rep = 0 ;
NewArr [ rep ] = val;
}
drugače če ( rep == Qsize - 1 && glavo ! = 0 )
{
rep = 0 ;
NewArr [ rep ] = val;
}
drugače {
rep ++;
NewArr [ rep ] = val;
}
}
Tukaj pokličemo funkcijo »enqueue()« iz razreda »MyQueue«, da vstavimo element v krožno čakalno vrsto, če je čakalna vrsta prazna ali premajhna. Funkcija »enqueue()« se posreduje s parametrom »val« in vstavi vrednost iz repa krožne čakalne vrste. Nastavili smo pogoj »if-else«, da za to vstavimo vrednosti v krožno čakalno vrsto. Prvi stavek »if«, ki je »if ((head == 0 && tail == Qsize – 1) || (tail == (head – 1) % (Qsize – 1)))« preveri dva pogoja, ali je glava je na začetnem položaju, rep pa na končnem položaju krožne čakalne vrste. Nato preveri, ali je rep v enem položaju na zadnjem delu glave. Če je kateri od teh pogojev izpolnjen, čakalna vrsta ni prazna in poziv ustvari sporočilo.
Nato imamo pogoj »drugo če«, ki identificira, ali je čakalna vrsta prazna. Če je tako, se vrednost vstavi v čakalno vrsto. Ker je višina enaka -1, to kaže, da je čakalna vrsta prazna in da je treba vrednost vstaviti v krožno čakalno vrsto. Za to nastavimo glavo in rep na 0. Nato vstavimo vrednost iz pozicije repa v krožno čakalno vrsto »NewArr«.
Nato imamo tretji pogoj »drugače, če«, ki preveri, ali je rep na zadnjem položaju v čakalni vrsti in glava ni začetni položaj v čakalni vrsti. Ta pogoj velja, ko rep doseže konec in ima začetni položaj še vedno prostor. Za to moramo glavo nastaviti na 0, element pa dodamo iz pozicije repa. Nazadnje, če vsi dani pogoji niso izpolnjeni, čakalna vrsta ni niti prazna niti polna. V tem primeru povečamo rep za 1 in vrednost se doda z novega položaja repa.
2. korak: Ustvarite funkcijo za brisanje elementov iz krožnega medpomnilnika
Prejšnjo kodo smo nastavili za ustvarjanje in vstavljanje elementov v krožno čakalno vrsto s funkcijo enqueue(). Zdaj definiramo izvedbo odstranitve elementov iz krožnega vmesnega pomnilnika, če se ta prepolni.
int MyQueue::deQueue ( ){
če ( glavo == - 1 )
{
cout << ' \n Čakalna vrsta je brezplačna' ;
vrnitev INT_MIN;
}
int MyData = NewArr [ glavo ] ;
NewArr [ glavo ] = -1 ;
če ( glavo == rep )
{
glavo = -1 ;
rep = -1 ;
}
drugače če ( glavo == Qsize - 1 )
glavo = 0 ;
drugače
glavo ++;
vrnitev MyData;
}
V dani kodi pokličemo funkcijo dequeue() iz razreda »Myqueue«, da odstranimo element iz indeksa glave. Torej, imamo stavek 'if', ki preveri, ali je čakalna vrsta prazna. Glava je nastavljena z vrednostjo »-1«, ki predstavlja prazno čakalno vrsto. Ustvari se sporočilo, da je čakalna vrsta prazna, nato pa se vrne INT_MIN, ki je konstantna najmanjša vrednost za int. Izjava »if« določa, ali je čakalna vrsta nezasedena. Za to definiramo spremenljivko 'MyData' in nastavimo vrednost elementa na čelu čakalne vrste. Nato nastavimo glavo na položaj -1, kar pomeni, da je ta vrednost odstranjena iz čakalne vrste. Po tem preverimo, ali sta glava in rep enaka ali ne. Če sta oba enaka, obema dodelimo vrednost '-1', ki predstavlja prazno krožno čakalno vrsto. Na koncu preverimo, ali dequeue() deluje, če je glava na zadnjem indeksu čakalne vrste. Za to smo ga nastavili z vrednostjo '0', ki se vrti na začetku matrike. Če nobeden od danih pogojev ni resničen, se vrednost glave poveča in vrne element iz vrste.
3. korak: Ustvarite funkcijo za prikaz elementov krožnega medpomnilnika
V tem razdelku pokličemo funkcijo showQueue(), da prikažemo elemente krožne čakalne vrste »NewArr«.
void MyQueue::showQueue ( ){
če ( glavo == - 1 )
{
cout << ' \n Čakalna vrsta je brezplačna' ;
vrnitev ;
}
cout << ' \n Elementi krožne čakalne vrste: ' ;
če ( rep > = glavo )
{
za ( int i = glavo ; jaz < = rep ; i++ )
cout << NewArr [ jaz ] << ' ' ;
}
drugače
{
za ( int i = glavo ; jaz < Qsize; i++ )
cout << NewArr [ jaz ] << ' ' ;
za ( int i = 0 ; jaz < = rep ; i++ )
cout << NewArr [ jaz ] << ' ' ;
}
}
Najprej se preveri prazen status čakalne vrste. Oznaka, da je krožna vrsta prosta, se prikaže, če je čakalna vrsta prosta. V nasprotnem primeru bo funkcija prikazala elemente krožne čakalne vrste. Za to definiramo stavek 'če', kjer imamo rep, ki je večji ali enak glavi. Ta pogoj je nastavljen za obravnavo primera, ko krožna čakalna vrsta ni dokončana.
V tem primeru uporabimo zanko »za« za ponavljanje od glave do repa in tiskanje vrednosti krožne čakalne vrste. Naslednji primer je, ko je krožna čakalna vrsta zaključena. Za to preverimo s pogojem 'če', kjer je rep manjši od glave. Nato moramo uporabiti dve zanki, kjer prva iterira od glave do konca čakalne vrste, druga pa od začetka repa.
4. korak: Ustvarite funkcijo Main() programa Circular Queue
Nazadnje ustvarimo programsko funkcijo main(), kjer v krožno čakalno vrsto vstavimo pet celih števil in prikažemo cela števila čakalne vrste. Nato s klicem funkcije dequeue() prikažemo izbrisana cela števila iz krožne čakalne vrste. Ko odstranimo nekaj elementov iz vrste, ponovno zapolnimo čakalno vrsto z vstavljanjem novih elementov s funkcijo enqueue().
int main ( ){
MyQueue to ( 5 ) ;
// Vstavljanje elementov v Krožna čakalna vrsta
que.enQueue ( enajst ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( petnajst ) ;
// Prikazni elementi so prisotni v Krožna čakalna vrsta
que.showQueue ( ) ;
// Brisanje elementov iz krožne čakalne vrste
cout << ' \n Izbrisan element = ' << que.deQueue ( ) ;
cout << ' \n Izbrisan element = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
vrnitev 0 ;
}
Izhod:
Rezultati implementacije krožne čakalne vrste so prikazani na pozivnem zaslonu C++.
Zaključek
Za zaključek je v tem članku podrobno razložena tema krožnega medpomnilnika. Najprej smo ustvarili krožni medpomnilnik, nato razložili, kako izbrisati iz krožne čakalne vrste, in nato prikazali elemente krožnega v C++.