Ang Circular buffer o Circular queue ay ang advanced na bersyon ng normal na pila kung saan ang huling index at tail index ay konektado sa isang pabilog na istraktura. Ang pabilog na buffer sa C++ ay sumusunod sa dalawang pamamaraan: enqueue() at dequeue(). Ginagawa namin ang circular buffer o circular queue operation batay sa mga pamamaraang ito.
- Sinusuri ng enqueue() na paraan upang makita kung napuno ang buffer. Kung hindi, i-verify na ang end index ay ang huli. Kung gayon, itakda ang tail value sa 0. Kung hindi, dagdagan ang tail value sa halaga sa index na iyon.
- Kinukuha ng dequeue() function ang value mula sa front index sa circular queue. Kung ang pila ay walang laman, ang isang mensahe ay magpapakita ng walang laman na pila. Kung hindi, nakukuha nito ang huling halaga at tatanggalin ito sa pila.
Programa para Magpatupad ng Circular Buffer sa C++
Kasunod ng nabanggit na dalawang pamamaraan, ipinapatupad namin ang circular buffer sa C++. Isaalang-alang natin ang lahat ng mga hakbang para sa pagpapatupad ng circular queue sa C++.
#include
gamit ang namespace std;
struct MyQueue
{
int ulo , buntot ;
int Qsize;
int * NewArr;
MyQueue ( int hindi ) {
ulo = buntot = -1 ;
Qsize = laki;
NewArr = bagong int [ s ] ;
}
void enQueue ( int val ) ;
int deQueue ( ) ;
void showQueue ( ) ;
} ;
Simula sa code, gagawa muna kami ng struct na 'MyQueue' para masimulan ang mga variable ng ulo at buntot. Kinakatawan ng variable ng ulo ang mga indeks sa harap at ang buntot ay kumakatawan sa mga indeks sa likod ng isang array. Pagkatapos nito, ang laki ng pabilog na pila, na tinutukoy ng variable na 'Qsize', ay tinukoy.
Pagkatapos, tinukoy namin ang dynamic na inilaan na hanay ng 'NewArr' na nag-iimbak ng mga halaga ng circular queue. Susunod, tinatawag namin ang MyQueue() na isang constructor at ipasa ang parameter na 'sz' para sa circular queue size. Sa loob ng MyQueue() constructor, itinatalaga namin ang '-1' na halaga sa mga head at tail pointer. Ang negatibong halaga na ito ay nagpapahiwatig na ang pila ay walang laman ngayon. Sa pagpapatuloy, itinatalaga namin ang 'sz' na halaga na kumakatawan sa laki ng pabilog na pila. Ang 'NewArr' circular queue ay itinakda sa isang bagong keyword upang lumikha ng hanay ng mga integer sa loob ng tinukoy na laki ng 'sz'.
Pagkatapos, tinutukoy namin ang enQueue() at dequeue() function. Ang enqueue() ay naglalagay ng mga halaga sa tinukoy na pabilog na pila mula sa buntot. Gayunpaman, ang mga elemento sa ulo ng pabilog na pila ay inaalis ng dequeue() function. Ipinapakita ng showQueue() member function ang mga value ng circular queue.
Hakbang 1: Gumawa ng Function para Ipasok ang Mga Elemento sa isang Circular Buffer
Sa naunang hakbang, nagtakda kami ng klase kung saan sinisimulan ang mga pribadong miyembro at ang mga function ng pribadong miyembro ay nakatakda upang ipatupad ang circular queue. Ngayon, itinakda namin ang function upang lumikha ng circular queue at ipasok ang mga halaga sa loob ng circular queue gamit ang algorithm.
void MyQueue::enQueue ( int val ){
kung ( ( ulo == 0 && buntot == Qsize - 1 ) || ( buntot == ( ulo - 1 ) % ( Qsize - 1 ) ) )
{
cout << ' \n Napuno ang pila' ;
bumalik ;
}
iba pa kung ( ulo == - 1 )
{
ulo = buntot = 0 ;
BagongArr [ buntot ] = val;
}
iba pa kung ( buntot == Qsize - 1 && ulo ! = 0 )
{
buntot = 0 ;
BagongArr [ buntot ] = val;
}
iba pa {
buntot ++;
BagongArr [ buntot ] = val;
}
}
Dito, tinatawag namin ang function na 'enqueue()' mula sa class na 'MyQueue' upang ipasok ang elemento sa circular queue kung ang queue ay walang laman o underflow. Ang function na 'enqueue()' ay ipinapasa kasama ang parameter na 'val' at ipasok ang halaga mula sa buntot ng pabilog na pila. Itinakda namin ang kundisyon na “if-else” para ipasok ang mga value sa circular queue para dito. Ang unang “if” statement na “if ((head == 0 && tail == Qsize – 1) || (tail == (head – 1) % (Qsize – 1)))” ay nagsusuri ng dalawang kundisyon kung ang head ay nasa panimulang posisyon at ang buntot ay nasa dulong posisyon ng pabilog na pila. Pagkatapos, sinusuri nito kung ang buntot ay nasa isang posisyon sa likod ng posisyon ng ulo. Kung ang alinman sa mga kundisyong ito ay natupad, ang pila ay hindi walang laman at ang prompt ay bumubuo ng mensahe.
Susunod, mayroon kaming kundisyon na 'iba-kung' na tumutukoy kung walang laman ang pila. Kung gayon, ang halaga ay ipinasok sa pila. Habang ang ulo ay pinananatiling katumbas ng -1, iyon ay nagpapakita na ang pila ay walang laman at ang halaga ay kinakailangang maipasok sa pabilog na pila. Para dito, itinakda namin ang ulo at buntot na katumbas ng 0. Pagkatapos, ipinasok namin ang halaga mula sa posisyon ng buntot sa 'NewArr' circular queue.
Pagkatapos, mayroon tayong pangatlong kundisyon na 'else-if' na nagsusuri kung ang buntot ay nasa huling posisyon ng pila at ang ulo ay hindi ang panimulang posisyon ng pila. Nalalapat ang kundisyong ito kapag ang buntot ay umabot sa dulo at ang panimulang posisyon ay mayroon pa ring espasyo. Para dito, kailangan nating itakda ang ulo sa 0, at ang elemento ay idinagdag mula sa posisyon ng buntot. Panghuli, kung ang lahat ng ibinigay na kundisyon ay hindi natutugunan, ang pila ay hindi walang laman o puno. Para sa kasong ito, dinaragdagan namin ang buntot ng 1 at idinagdag ang halaga mula sa bagong posisyon ng buntot.
Hakbang 2: Gumawa ng function para Tanggalin ang Mga Elemento mula sa Circular Buffer
Itinakda namin ang nakaraang code upang lumikha at magpasok ng mga elemento sa pabilog na pila gamit ang enqueue() function. Ngayon, tinutukoy namin ang pagpapatupad ng pag-alis ng mga elemento mula sa pabilog na buffer kung umaapaw ito.
int MyQueue::deQueue ( ){
kung ( ulo == - 1 )
{
cout << ' \n Libre ang pila' ;
bumalik INT_MIN;
}
int MyData = NewArr [ ulo ] ;
BagongArr [ ulo ] = -1 ;
kung ( ulo == buntot )
{
ulo = -1 ;
buntot = -1 ;
}
iba pa kung ( ulo == Qsize - 1 )
ulo = 0 ;
iba pa
ulo ++;
bumalik Ang aking data;
}
Sa ibinigay na code, tinatawag namin ang dequeue() function mula sa klase na 'Myqueue' upang alisin ang elemento mula sa head index. Kaya, mayroon kaming 'kung' na pahayag na nagsusuri kung ang pila ay walang laman. Nakatakda ang head na may value na '-1' na kumakatawan sa walang laman na pila. Ang mensahe ay nabuo na ang queue ay walang laman at pagkatapos ay ibalik ang INT_MIN na kung saan ay ang palaging minimum na halaga para sa isang int. Tinutukoy ng pahayag na 'kung' kung ang pila ay walang tao. Para dito, tinukoy namin ang variable na 'MyData' at itinakda ang halaga ng elemento sa ulo ng queue. Pagkatapos, itinakda namin ang ulo sa -1 na posisyon na nagpapahiwatig na ang halagang ito ay tinanggal mula sa pila. Pagkatapos nito, sinusuri namin kung ang ulo at buntot ay pantay o hindi. Kung pareho ang pareho, itinatalaga namin ang '-1' na halaga sa pareho, na kumakatawan sa walang laman na circular queue. Panghuli, tinitingnan namin kung gumagana ang dequeue() kung ang head ay nasa huling index ng pila. Para dito, itinakda namin ito sa halagang '0' na umiikot sa simula ng array. Kung wala sa mga ibinigay na kundisyon ang totoo, ang halaga ng ulo ay dinadagdagan at ang na-dequeued na elemento ay ibabalik.
Hakbang 3: Gumawa ng Function para Ipakita ang Mga Elemento ng Circular Buffer
Sa seksyong ito, tinatawag namin ang showQueue() function para ipakita ang mga elemento ng circular queue na “NewArr”.
void MyQueue::showQueue ( ){
kung ( ulo == - 1 )
{
cout << ' \n Libre ang pila' ;
bumalik ;
}
cout << ' \n Mga elemento ng Circular Queue: ' ;
kung ( buntot > = ulo )
{
para sa ( int i = ulo ; i < = buntot ; i++ )
cout << BagongArr [ i ] << '' ;
}
iba pa
{
para sa ( int i = ulo ; i < Qsize; i++ )
cout << BagongArr [ i ] << '' ;
para sa ( int i = 0 ; i < = buntot ; i++ )
cout << BagongArr [ i ] << '' ;
}
}
Ang walang laman na katayuan ng pila ay unang na-verify. Ang isang indikasyon na ang pabilog na pila ay libre ay ipinapakita kung ang pila ay libre. Kung hindi, ipapakita ng function ang mga elemento ng circular queue. Para dito, tinukoy namin ang pahayag na 'kung' kung saan mayroon kaming buntot na mas malaki kaysa sa o katumbas ng ulo. Ang kundisyong ito ay nakatakda upang pangasiwaan ang kaso kapag ang pabilog na pila ay hindi nakumpleto.
Para sa kasong ito, ginagamit namin ang loop na 'para sa' upang umulit mula ulo hanggang buntot at i-print ang mga halaga ng pabilog na pila. Ang susunod na kaso ay kung saan nakumpleto ang pabilog na pila. Para dito, sinusuri namin gamit ang 'kung' na kondisyon kung saan ang buntot ay mas mababa kaysa sa ulo. Pagkatapos, kailangan nating gumamit ng dalawang mga loop kung saan ang una ay umuulit mula sa ulo hanggang sa dulo ng pila at ang pangalawa ay umuulit mula sa simula ng buntot.
Hakbang 4: Gumawa ng Main() Function ng Circular Queue Program
Panghuli, ginagawa namin ang main() function ng program kung saan naglalagay kami ng limang integer sa circular queue at ipinapakita ang mga integer ng queue. Pagkatapos nito, ipinapakita namin ang mga tinanggal na integer mula sa circular queue sa pamamagitan ng pagtawag sa dequeue() function. Pagkatapos mag-dequeu ng ilang elemento, pinupunan namin muli ang queue sa pamamagitan ng pagpasok ng mga bagong elemento gamit ang enqueue() function.
int pangunahing ( ){
MyQueue yan ( 5 ) ;
// Pagpasok ng mga elemento sa Circular Queue
que.enQueue ( labing-isa ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( labinlima ) ;
// Ipakita ang mga elemento na naroroon sa Circular Queue
que.showQueue ( ) ;
// Pagtanggal ng mga elemento mula sa Circular Queue
cout << ' \n Tinanggal na Element = ' << que.deQueue ( ) ;
cout << ' \n Tinanggal na Element = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
bumalik 0 ;
}
Output:
Ang mga resulta ng pagpapatupad ng circular queue ay ipinapakita sa C++ prompt screen.
Konklusyon
Sa konklusyon, ang pabilog na paksa ng buffer ay malalim na ipinaliwanag sa artikulong ito. Ginawa muna namin ang circular buffer, pagkatapos ay ipinaliwanag kung paano magtanggal mula sa circular queue, at pagkatapos ay ipinakita ang mga elemento ng circular sa C++.