Kružni međuspremnik ili kružni red čekanja napredna je verzija normalnog reda čekanja gdje su zadnji indeks i repni indeks povezani u kružnu strukturu. Kružni međuspremnik u C++ slijedi dvije metode: enqueue() i dequeue(). Na temelju ovih metoda izvodimo operaciju kružnog međuspremnika ili kružnog čekanja.
- Metoda enqueue() provjerava je li međuspremnik popunjen. Inače, provjerite je li krajnji indeks posljednji. Ako je tako, postavite repnu vrijednost na 0. Ako nije, povećajte repnu vrijednost za vrijednost tog indeksa.
- Funkcija dequeue() preuzima vrijednost iz prednjeg indeksa u kružnom redu čekanja. Ako je red čekanja prazan, poruka će prikazati taj prazan red čekanja. U suprotnom, dobiva posljednju vrijednost i briše je iz reda čekanja.
Program za implementaciju kružnog međuspremnika u C++
Slijedeći spomenute dvije metode, implementiramo kružni međuspremnik u C++. Razmotrimo sve korake za implementaciju kružnog reda čekanja u C++.
#include
korištenje imenskog prostora std;
struct MyQueue
{
int glava , rep ;
int Qsize;
int * NewArr;
MyQueue ( int br ) {
glava = rep = -1 ;
Qsize = veličina;
NewArr = novi int [ s ] ;
}
void enQueue ( int val ) ;
int deQueue ( ) ;
void showQueue ( ) ;
} ;
Počevši od koda, prvo stvaramo strukturu 'MyQueue' za inicijalizaciju varijabli glave i repa. Varijabla glave predstavlja prednje indekse, a rep predstavlja stražnje stražnje indekse niza. Nakon toga se definira veličina kružnog reda čekanja, označena varijablom 'Qsize'.
Zatim definiramo dinamički dodijeljeni niz 'NewArr' koji pohranjuje vrijednosti kružnog reda čekanja. Zatim pozivamo MyQueue() koji je konstruktor i prosljeđujemo parametar “sz” za kružnu veličinu reda čekanja. Unutar konstruktora MyQueue() dodjeljujemo vrijednost “-1” pokazivačima na čelu i repu. Ova negativna vrijednost označava da je red sada prazan. Idemo dalje, dodjeljujemo vrijednost 'sz' koja predstavlja veličinu kružnog reda čekanja. Kružni red čekanja 'NewArr' postavlja se s novom ključnom riječi za stvaranje niza cijelih brojeva unutar navedene veličine 'sz'.
Zatim definiramo funkcije enQueue() i dequeue(). Enqueue() umeće vrijednosti u definirani kružni red iz repa. Međutim, elementi u glavi kružnog reda eliminiraju se funkcijom dequeue(). Funkcija članica showQueue() prikazuje vrijednosti kružnog reda čekanja.
Korak 1: Stvorite funkciju za umetanje elemenata u kružni međuspremnik
U prethodnom koraku postavili smo klasu u kojoj su privatni članovi inicijalizirani, a privatne funkcije članova postavljene za implementaciju kružnog reda čekanja. Sada postavljamo funkciju za stvaranje kružnog reda i umetanje vrijednosti unutar kružnog reda pomoću algoritma.
void MyQueue::enQueue ( int val ){
ako ( ( glava == 0 && rep == Qveličina - 1 ) || ( rep == ( glava - 1 ) % ( Qveličina - 1 ) ) )
{
cout << ' \n Red je popunjen' ;
povratak ;
}
drugo ako ( glava == - 1 )
{
glava = rep = 0 ;
NewArr [ rep ] = val;
}
drugo ako ( rep == Qveličina - 1 && glava ! = 0 )
{
rep = 0 ;
NewArr [ rep ] = val;
}
drugo {
rep ++;
NewArr [ rep ] = val;
}
}
Ovdje pozivamo funkciju 'enqueue()' iz klase 'MyQueue' kako bismo umetnuli element u kružni red čekanja ako je red čekanja prazan ili ga nema. Funkcija 'enqueue()' prosljeđuje se s parametrom 'val' i umeće vrijednost iz repa kružnog reda čekanja. Postavili smo uvjet 'if-else' za umetanje vrijednosti u kružni red za ovo. Prva izjava “if” koja glasi “if ((head == 0 && tail == Qsize – 1) || (tail == (head – 1) % (Qsize – 1)))” provjerava dva uvjeta je li glava nalazi se na početnoj poziciji, a rep je na krajnjoj poziciji kružnog reda čekanja. Zatim provjerava je li rep u jednom položaju na stražnjem dijelu glave. Ako je bilo koji od ovih uvjeta ispunjen, red čekanja nije prazan i prompt generira poruku.
Zatim imamo uvjet 'else-if' koji identificira je li red čekanja prazan. Ako je tako, vrijednost se ubacuje u red čekanja. Budući da je glava jednaka -1, to pokazuje da je red čekanja prazan i da se vrijednost mora umetnuti u kružni red čekanja. Za ovo smo postavili glavu i rep jednake 0. Zatim smo umetnuli vrijednost iz pozicije repa u 'NewArr' kružni red čekanja.
Zatim imamo naš treći 'else-if' uvjet koji provjerava je li rep na posljednjoj poziciji reda i glava nije početna pozicija reda. Ovaj uvjet vrijedi kada rep dođe do kraja, a početna pozicija još ima mjesta. Za ovo moramo postaviti glavu na 0, a element se dodaje iz pozicije repa. Na kraju, ako svi zadani uvjeti nisu ispunjeni, red čekanja nije ni prazan ni pun. U ovom slučaju, povećavamo rep za 1 i vrijednost se dodaje s novog položaja repa.
Korak 2: Napravite funkciju za brisanje elemenata iz kružnog međuspremnika
Postavili smo prethodni kod za stvaranje i umetanje elemenata u kružni red pomoću funkcije enqueue(). Sada definiramo implementaciju uklanjanja elemenata iz kružnog međuspremnika ako se prelije.
int MyQueue::deQueue ( ){
ako ( glava == - 1 )
{
cout << ' \n Red je besplatan' ;
povratak INT_MIN;
}
int MyData = NewArr [ glava ] ;
NewArr [ glava ] = -1 ;
ako ( glava == rep )
{
glava = -1 ;
rep = -1 ;
}
drugo ako ( glava == Qveličina - 1 )
glava = 0 ;
drugo
glava ++;
povratak MyData;
}
U danom kodu pozivamo funkciju dequeue() iz klase 'Myqueue' kako bismo uklonili element iz indeksa glave. Dakle, imamo naredbu “if” koja provjerava da li je red čekanja prazan. Glava je postavljena s vrijednošću '-1' koja predstavlja prazan red čekanja. Generira se poruka da je red čekanja prazan i zatim vraća INT_MIN što je konstantna minimalna vrijednost za int. Naredba “if” određuje je li red čekanja nezauzet. U tu svrhu definiramo varijablu 'MyData' i postavljamo vrijednost elementa na čelu reda čekanja. Zatim postavljamo glavu na poziciju -1 što označava da je ova vrijednost uklonjena iz reda čekanja. Nakon toga provjeravamo jesu li glava i rep jednaki ili ne. Ako su oba jednaka, objema dodjeljujemo vrijednost '-1', što predstavlja prazan kružni red čekanja. Na kraju, provjeravamo funkcionira li dequeue() ako je glava na zadnjem indeksu reda. Za ovo smo postavili vrijednost '0' koja se vrti okolo na početku niza. Ako niti jedan od zadanih uvjeta nije istinit, vrijednost glave se povećava i vraća se element koji je uklonjen iz reda čekanja.
Korak 3: Napravite funkciju za prikaz elemenata kružnog međuspremnika
U ovom odjeljku pozivamo funkciju showQueue() za prikaz elemenata kružnog reda čekanja 'NewArr'.
void MyQueue::showQueue ( ){
ako ( glava == - 1 )
{
cout << ' \n Red je besplatan' ;
povratak ;
}
cout << ' \n Elementi kružnog reda: ' ;
ako ( rep > = glava )
{
za ( int i = glava ; ja < = rep ; i++ )
cout << NewArr [ ja ] << ' ' ;
}
drugo
{
za ( int i = glava ; ja < Qsize; i++ )
cout << NewArr [ ja ] << ' ' ;
za ( int i = 0 ; ja < = rep ; i++ )
cout << NewArr [ ja ] << ' ' ;
}
}
Prvo se provjerava prazan status reda čekanja. Indikacija da je kružni red slobodan prikazuje se ako je red slobodan. U suprotnom, funkcija će prikazati elemente kružnog reda čekanja. Za ovo definiramo naredbu “if” gdje imamo rep koji je veći ili jednak glavi. Ovaj uvjet je postavljen za obradu slučaja kada kružni red čekanja nije dovršen.
U ovom slučaju koristimo petlju 'for' za ponavljanje od glave do repa i ispis vrijednosti kružnog reda čekanja. Sljedeći slučaj je kada je kružni red čekanja dovršen. Za ovo provjeravamo pomoću uvjeta 'ako' gdje je rep manji od glave. Zatim trebamo koristiti dvije petlje gdje prva ponavlja od glave do kraja reda, a druga ponavlja od početka repa.
Korak 4: Stvorite funkciju Main() programa Circular Queue
Na kraju, stvaramo programsku funkciju main() gdje umećemo pet cijelih brojeva u kružni red i prikazujemo cijele brojeve reda. Nakon toga prikazujemo izbrisane cijele brojeve iz kružnog reda pozivanjem funkcije dequeue(). Nakon uklanjanja nekoliko elemenata iz reda čekanja, ponovno popunjavamo red umetanjem novih elemenata pomoću funkcije enqueue().
int glavni ( ){
MyQueue to ( 5 ) ;
// Umetanje elemenata u Kružni red
que.enQueue ( jedanaest ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( petnaest ) ;
// Prikazni elementi prisutni u Kružni red
que.showQueue ( ) ;
// Brisanje elemenata iz kružnog reda
cout << ' \n Izbrisani element = ' << que.deQueue ( ) ;
cout << ' \n Izbrisani element = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
povratak 0 ;
}
Izlaz:
Rezultati implementacije kružnog reda čekanja prikazani su na C++ promptnom zaslonu.
Zaključak
Zaključno, tema kružnog međuspremnika detaljno je objašnjena u ovom članku. Prvo smo stvorili kružni međuspremnik, zatim objasnili kako izbrisati iz kružnog reda čekanja, a zatim smo prikazali elemente kružnog međuspremnika u C++.