Bufferul circular sau Coada circulară este versiunea avansată a cozii normale în care ultimul index și indicele de coadă sunt conectate într-o structură circulară. Bufferul circular în C++ urmează două metode: enqueue() și dequeue(). Efectuăm operația de buffer circular sau coadă circulară pe baza acestor metode.
- Metoda enqueue() verifică dacă tamponul este umplut. În caz contrar, verificați dacă indexul final este ultimul. Dacă da, setați valoarea cozii la 0. Dacă nu, creșteți valoarea cozii cu valoarea de la acel indice.
- Funcția dequeue() preia valoarea din indexul frontal din coada circulară. Dacă coada este goală, un mesaj va afișa coada goală. În caz contrar, primește ultima valoare și o șterge din coadă.
Program pentru implementarea unui buffer circular în C++
Urmând cele două metode menționate, implementăm bufferul circular în C++. Să luăm în considerare toți pașii pentru implementarea cozii circulare în C++.
#include
folosind namespace std;
struct MyQueue
{
int cap , coadă ;
int Qsize;
int * NewArr;
MyQueue ( int nr ) {
cap = coadă = -1 ;
Qsize = dimensiune;
NewArr = nou int [ s ] ;
}
void enQueue ( int val ) ;
int deQueue ( ) ;
void showQueue ( ) ;
} ;
Începând cu codul, creăm mai întâi structura „MyQueue” pentru a inițializa variabilele head și tail. Variabila cap reprezintă indicii din față, iar coada reprezintă indicii din spate din spate ai unui tablou. După aceea, este definită dimensiunea cozii circulare, notată cu variabila „Qsize”.
Apoi, definim matricea alocată dinamic a „NewArr” care stochează valorile cozii circulare. Apoi, apelăm MyQueue() care este un constructor și trecem parametrul „sz” pentru dimensiunea cozii circulare. În interiorul constructorului MyQueue(), atribuim valoarea „-1” pointerilor cap și coadă. Această valoare negativă indică faptul că coada este goală acum. Mergând înainte, atribuim valoarea „sz” care reprezintă dimensiunea cozii circulare. Coada circulară „NewArr” este setată cu un nou cuvânt cheie pentru a crea o matrice de numere întregi în dimensiunea „sz” specificată.
Apoi, definim funcțiile enQueue() și dequeue(). Enqueue() inserează valorile în coada circulară definită de la coadă. Cu toate acestea, elementele din capul cozii circulare sunt eliminate de funcția dequeue(). Funcția membru showQueue() afișează valorile cozii circulare.
Pasul 1: Creați o funcție pentru a introduce elementele într-un tampon circular
În pasul anterior, am setat o clasă în care membrii privați sunt inițializați și funcțiile de membru privat sunt setate pentru a implementa coada circulară. Acum, setăm funcția pentru a crea coada circulară și introducem valorile în coada circulară folosind algoritmul.
void MyQueue::enQueue ( int val ){
dacă ( ( cap == 0 && coadă == Qsize - 1 ) || ( coadă == ( cap - 1 ) % ( Dimensiune Q - 1 ) ) )
{
cout << ' \n Coada este umplută' ;
întoarcere ;
}
altfel dacă ( cap == - 1 )
{
cap = coadă = 0 ;
NewArr [ coadă ] = val;
}
altfel dacă ( coadă == Qsize - 1 && cap ! = 0 )
{
coadă = 0 ;
NewArr [ coadă ] = val;
}
altfel {
coadă ++;
NewArr [ coadă ] = val;
}
}
Aici, numim funcția „enqueue()” din clasa „MyQueue” pentru a insera elementul în coada circulară dacă coada este goală sau sub depășire. Funcția „enqueue()” este transmisă cu parametrul „val” și se inserează valoarea din coada cozii circulare. Am stabilit condiția „if-else” pentru a introduce valorile în coada circulară pentru aceasta. Prima afirmație „dacă” care este „dacă ((cap == 0 && coada == Qsize – 1) || (tail == (head – 1) % (Qsize – 1)))” verifică două condiții dacă capul este în poziția de început, iar coada este în poziția finală a cozii circulare. Apoi, verifică dacă coada este într-o singură poziție în partea din spate a capului. Dacă oricare dintre aceste condiții este îndeplinită, coada nu este goală și promptul generează mesajul.
În continuare, avem condiția „altfel dacă” care identifică dacă coada este goală. Dacă da, valoarea este inserată în coadă. Deoarece capul este menținut egal cu -1, asta arată că coada este goală și valoarea trebuie să fie inserată în coada circulară. Pentru aceasta, setăm capul și coada egale cu 0. Apoi, inserăm valoarea din poziția coadă în coada circulară „NewArr”.
Apoi, avem a treia condiție „altfel dacă” care verifică dacă coada se află în ultima poziție a cozii și capul nu este poziția de pornire a cozii. Această condiție se aplică atunci când coada ajunge la capăt și poziția de pornire mai are spațiu. Pentru aceasta, trebuie să setăm capul la 0, iar elementul este adăugat din poziția cozii. În sfârșit, dacă nu sunt îndeplinite toate condițiile date, coada nu este nici goală, nici plină. În acest caz, creștem coada cu 1 și valoarea este adăugată din noua poziție a cozii.
Pasul 2: Creați o funcție pentru a șterge elementele din tamponul circular
Setăm codul anterior să creeze și să insereze elementele în coada circulară folosind funcția enqueue(). Acum, definim implementarea eliminării elementelor din buffer-ul circular dacă acesta se depășește.
int MyQueue::deQueue ( ){
dacă ( cap == - 1 )
{
cout << ' \n Coada este liberă' ;
întoarcere INT_MIN;
}
int MyData = NewArr [ cap ] ;
NewArr [ cap ] = -1 ;
dacă ( cap == coadă )
{
cap = -1 ;
coadă = -1 ;
}
altfel dacă ( cap == Qsize - 1 )
cap = 0 ;
altfel
cap ++;
întoarcere Datele mele;
}
În codul dat, apelăm funcția dequeue() din clasa „Myqueue” pentru a elimina elementul din indexul head. Deci, avem instrucțiunea „dacă” care verifică dacă coada este goală. Capul este setat cu valoarea „-1” care reprezintă coada goală. Se generează mesajul că coada este goală și apoi returnează INT_MIN care este valoarea minimă constantă pentru un int. Declarația „dacă” determină dacă coada este neocupată. Pentru aceasta, definim variabila „MyData” și setăm valoarea elementului în capul cozii. Apoi, setăm capul în poziția -1, ceea ce indică faptul că această valoare este eliminată din coadă. După aceasta, verificăm dacă capul și coada sunt egale sau nu. Dacă ambele sunt egale, le atribuim valoarea „-1” ambelor, reprezentând coada circulară goală. În sfârșit, verificăm dacă dequeue() funcționează dacă capul se află la ultimul index al cozii. Pentru aceasta, l-am setat cu valoarea „0” care circulă în jurul valorii de la începutul matricei. Dacă niciuna dintre condițiile date nu este adevărată, valoarea capului este incrementată și elementul scos din coadă este returnat.
Pasul 3: Creați o funcție pentru a afișa elementele tamponului circular
În această secțiune, apelăm funcția showQueue() pentru a afișa elementele cozii circulare „NewArr”.
void MyQueue::showQueue ( ){
dacă ( cap == - 1 )
{
cout << ' \n Coada este liberă' ;
întoarcere ;
}
cout << ' \n Elemente de coadă circulară: ' ;
dacă ( coadă > = cap )
{
pentru ( int i = cap ; i < = coadă ; i++ )
cout << NewArr [ i ] << ' ' ;
}
altfel
{
pentru ( int i = cap ; i < Qsize; i++ )
cout << NewArr [ i ] << ' ' ;
pentru ( int i = 0 ; i < = coadă ; i++ )
cout << NewArr [ i ] << ' ' ;
}
}
Starea goală a cozii este mai întâi verificată. O indicație că coada circulară este liberă este afișată dacă coada este liberă. În caz contrar, funcția va afișa elementele cozii circulare. Pentru aceasta, definim afirmația „dacă” în care avem coada care este mai mare sau egală cu capul. Această condiție este setată pentru a gestiona cazul în care coada circulară nu este finalizată.
În acest caz, folosim bucla „for” pentru a itera de la cap la coadă și pentru a imprima valorile cozii circulare. Următorul caz este în care coada circulară este finalizată. Pentru aceasta, verificăm folosind condiția „dacă” în care coada este mai mică decât capul. Apoi, trebuie să folosim două bucle în care prima iterează de la cap până la sfârșitul cozii, iar a doua iterează de la începutul cozii.
Pasul 4: Creați funcția Main() a programului Circular Queue
În cele din urmă, creăm funcția main() a programului în care inserăm cinci numere întregi în coada circulară și afișăm numerele întregi ale cozii. După aceea, arătăm numerele întregi șterse din coada circulară apelând funcția dequeue(). După scoaterea din coadă a câtorva elemente, umplem din nou coada inserând noile elemente folosind funcția enqueue().
int principal ( ){
MyQueue asta ( 5 ) ;
// Inserarea elementelor în Coada circulară
que.enQueue ( unsprezece ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( cincisprezece ) ;
// Elemente de afișare prezente în Coada circulară
que.showQueue ( ) ;
// Ștergerea elementelor din coada circulară
cout << ' \n Element șters = ' << que.deQueue ( ) ;
cout << ' \n Element șters = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
întoarcere 0 ;
}
Ieșire:
Rezultatele implementării cozii circulare sunt afișate pe ecranul prompt C++.
Concluzie
În concluzie, subiectul bufferului circular este explicat profund în acest articol. Am creat mai întâi tamponul circular, apoi am explicat cum să ștergem din coada circulară și apoi am afișat elementele circularei în C++.