Pyöreä puskuri tai Circular queue on edistynyt versio normaalista jonosta, jossa viimeinen indeksi ja loppuindeksi on yhdistetty pyöreäksi rakenteeksi. C++:n pyöreä puskuri noudattaa kahta menetelmää: enqueue() ja dequeue(). Suoritamme pyöreän puskurin tai pyöreän jonotoiminnon näiden menetelmien perusteella.
- Enqueue()-menetelmä tarkistaa, onko puskuri täytetty. Muussa tapauksessa varmista, että loppuindeksi on viimeinen. Jos näin on, aseta hännän arvoksi 0. Jos ei, lisää hännän arvoa kyseisen indeksin arvolla.
- Dequeue()-funktio ottaa arvon pyöreän jonon etuindeksistä. Jos jono on tyhjä, tyhjän jonon näyttöön tulee viesti. Muussa tapauksessa se saa viimeisen arvon ja poistaa sen jonosta.
Ohjelma pyöreän puskurin toteuttamiseksi C++:ssa
Seuraamalla mainittuja kahta menetelmää toteutamme pyöreän puskurin C++:ssa. Harkitse kaikkia vaiheita pyöreän jonon toteuttamiseksi C++:ssa.
#include
käyttäen nimiavaruutta std;
rakentaa MyQueue
{
int pää , häntää ;
int Qsize;
int * NewArr;
MyQueue ( int nro ) {
pää = häntää = -1 ;
Qsize = koko;
UusiArr = uusi int [ s ] ;
}
tyhjä enQueue ( int val ) ;
int deQueue ( ) ;
tyhjä showQueue ( ) ;
} ;
Koodista alkaen luomme ensin 'MyQueue'-rakenteen pää- ja hännänmuuttujien alustamiseksi. Päämuuttuja edustaa etu-indeksejä ja häntä edustaa taulukon taka-indeksejä. Tämän jälkeen määritellään pyöreän jonon koko, jota merkitään muuttujalla 'Qsize'.
Sitten määritämme dynaamisesti allokoidun 'NewArr'-taulukon, joka tallentaa pyöreän jonon arvot. Seuraavaksi kutsumme MyQueue():tä, joka on konstruktori ja välitämme pyöreän jonon koon 'sz'-parametrin. MyQueue()-konstruktorissa annamme pää- ja hännänosoittimille arvon -1. Tämä negatiivinen arvo osoittaa, että jono on nyt tyhjä. Eteenpäin määritämme 'sz'-arvon, joka edustaa pyöreän jonon kokoa. 'NewArr' ympyräjono asetetaan uudella avainsanalla kokonaislukujen taulukon luomiseksi määritetyn 'sz'-koon sisällä.
Sitten määritämme enQueue()- ja dequeue()-funktiot. Enqueue() lisää arvot määritettyyn ympyräjonoon hännästä. Pyöreän jonon pään elementit kuitenkin eliminoidaan dequeue()-funktiolla. Jäsenfunktio showQueue() näyttää ympyränmuotoisen jonon arvot.
Vaihe 1: Luo funktio elementtien lisäämiseksi pyöreään puskuriin
Aiemmassa vaiheessa asetimme luokan, jossa yksityiset jäsenet alustetaan ja yksityisen jäsenen toiminnot asetetaan toteuttamaan pyöreä jono. Nyt asetamme funktion luomaan pyöreän jonon ja lisäämme arvot pyöreän jonon sisään algoritmin avulla.
mitätön MyQueue::enQueue ( int val ){
jos ( ( pää == 0 && häntää == Qsize - 1 ) || ( häntää == ( pää - 1 ) % ( Qsize - 1 ) ) )
{
cout << ' \n Jono on täynnä' ;
palata ;
}
muu jos ( pää == - 1 )
{
pää = häntää = 0 ;
UusiArr [ häntää ] = val;
}
muu jos ( häntää == Qsize - 1 && pää ! = 0 )
{
häntää = 0 ;
UusiArr [ häntää ] = val;
}
muu {
häntää ++;
UusiArr [ häntää ] = val;
}
}
Tässä kutsumme 'enqueue()'-funktiota 'MyQueue'-luokasta lisätäksesi elementin pyöreään jonoon, jos jono on tyhjä tai alivuoto. Funktio 'enqueue()' välitetään 'val'-parametrin kanssa ja lisää arvo pyöreän jonon loppupäästä. Asetamme 'jos-else' -ehdon lisäämään arvot pyöreään jonoon tätä varten. Ensimmäinen 'jos'-lause, joka on 'if ((pää == 0 && tail == Qsize – 1) || (häntä == (pää - 1) % (Qsize - 1)))' tarkistaa kaksi ehtoa, onko pää on pyöreän jonon alkuasemassa ja loppupää on pyöreän jonon lopussa. Sitten se tarkistaa, onko häntä yhdessä asennossa pään takaosassa. Jos jokin näistä ehdoista täyttyy, jono ei ole tyhjä ja kehote luo viestin.
Seuraavaksi meillä on 'else-if' -ehto, joka tunnistaa, onko jono tyhjä. Jos näin on, arvo lisätään jonoon. Koska pää pidetään arvossa -1, se osoittaa, että jono on tyhjä ja arvo on lisättävä pyöreään jonoon. Tätä varten asetamme pään ja hännän arvoksi 0. Sen jälkeen lisäämme arvon hännän sijainnista 'NewArr' pyöreään jonoon.
Sitten meillä on kolmas 'else-if' -ehto, joka tarkistaa, onko häntä jonon viimeisessä paikassa ja pää ei ole jonon aloituspaikka. Tämä ehto pätee, kun häntä saavuttaa pään ja aloitusasennossa on vielä tilaa. Tätä varten meidän on asetettava pää arvoon 0, ja elementti lisätään häntäasennosta. Lopuksi, jos kaikki annetut ehdot eivät täyty, jono ei ole tyhjä eikä täynnä. Tässä tapauksessa lisäämme häntää yhdellä ja arvo lisätään uudesta hännän sijainnista.
Vaihe 2: Luo funktio elementtien poistamiseksi kiertopuskurista
Asetimme edellisen koodin luomaan ja lisäämään elementit pyöreään jonoon enqueue()-funktiolla. Nyt määrittelemme toteutuksen elementtien poistamiseksi pyöreästä puskurista, jos se ylivuodon.
int MyQueue::deQueue ( ){
jos ( pää == - 1 )
{
cout << ' \n Jono on vapaa' ;
palata INT_MIN;
}
int MyData = UusiArr [ pää ] ;
UusiArr [ pää ] = -1 ;
jos ( pää == häntää )
{
pää = -1 ;
häntää = -1 ;
}
muu jos ( pää == Qsize - 1 )
pää = 0 ;
muu
pää ++;
palata MyData;
}
Annetussa koodissa kutsumme dequeue()-funktiota 'Myqueue'-luokasta poistaaksesi elementin päähakemistosta. Joten meillä on 'if'-lause, joka tarkistaa, onko jono tyhjä. Päälle asetetaan '-1'-arvo, joka edustaa tyhjää jonoa. Sanoma luodaan, että jono on tyhjä, ja sitten palautetaan INT_MIN, joka on int:n vakio minimiarvo. 'if'-käsky määrittää, onko jono vapaa. Tätä varten määritämme 'MyData'-muuttujan ja asetamme elementin arvon jonon päähän. Sitten asetamme pään kohtaan -1, mikä osoittaa, että tämä arvo on poistettu jonosta. Tämän jälkeen tarkistamme, ovatko pää ja häntä yhtä suuria vai eivät. Jos molemmat ovat yhtä suuria, annamme molemmille arvon '-1', joka edustaa tyhjää pyöreää jonoa. Lopuksi tarkistamme, toimiiko dequeue() jos pää on jonon viimeisessä indeksissä. Tätä varten asetamme sen arvoksi '0', joka kiertää taulukon alussa. Jos mikään annetuista ehdoista ei pidä paikkaansa, pään arvoa kasvatetaan ja jonotettu elementti palautetaan.
Vaihe 3: Luo funktio pyöreän puskurin elementtien näyttämiseksi
Tässä osiossa kutsumme showQueue()-funktiota näyttämään 'NewArr' pyöreän jonon elementit.
mitätöi MyQueue::showQueue ( ){
jos ( pää == - 1 )
{
cout << ' \n Jono on vapaa' ;
palata ;
}
cout << ' \n Pyöreän jonon elementit: ' ;
jos ( häntää > = pää )
{
varten ( int i = pää ; i < = häntää ; i++ )
cout << UusiArr [ i ] << ' ' ;
}
muu
{
varten ( int i = pää ; i < Qsize; i++ )
cout << UusiArr [ i ] << ' ' ;
varten ( int i = 0 ; i < = häntää ; i++ )
cout << UusiArr [ i ] << ' ' ;
}
}
Jonon tyhjä tila tarkistetaan ensin. Jos jono on vapaa, näyttöön tulee ilmoitus siitä, että pyöreä jono on vapaa. Muussa tapauksessa funktio näyttää pyöreän jonon elementit. Tätä varten määrittelemme 'jos'-lausekkeen, jossa häntä on suurempi tai yhtä suuri kuin pää. Tämä ehto on asetettu käsittelemään tapausta, jossa pyöreä jono ei ole valmis.
Tässä tapauksessa käytämme 'for'-silmukkaa iteroimaan päästä loppuun ja tulostamaan pyöreän jonon arvot. Seuraava tapaus on, kun pyöreä jono on valmis. Tätä varten tarkistamme käyttämällä 'jos'-ehtoa, jossa häntä on pienempi kuin pää. Sitten meidän on käytettävä kahta silmukkaa, joissa ensimmäinen iteroidaan jonon päästä ja toinen iteroidaan hännän alusta.
Vaihe 4: Luo Circular Queue -ohjelman Main()-funktio
Lopuksi luomme ohjelman main()-funktion, jossa lisäämme viisi kokonaislukua pyöreään jonoon ja näytämme jonon kokonaisluvut. Sen jälkeen näytämme poistetut kokonaisluvut pyöreästä jonosta kutsumalla dequeue()-funktiota. Kun muutama elementti on poistettu jonosta, täytämme jonon uudelleen lisäämällä uudet elementit enqueue()-funktiolla.
int main ( ){
MyQueue tuo ( 5 ) ;
// Elementtien lisääminen sisään Pyöreä jono
que.enQueue ( yksitoista ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( viisitoista ) ;
// Näyttöelementit esillä sisään Pyöreä jono
que.showQueue ( ) ;
// Poistetaan elementtejä kiertojonosta
cout << ' \n Poistettu elementti = ' << que.deQueue ( ) ;
cout << ' \n Poistettu elementti = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
palata 0 ;
}
Lähtö:
Pyöreän jonon toteutuksen tulokset näkyvät C++-kehotenäytössä.
Johtopäätös
Yhteenvetona voidaan todeta, että pyöreän puskurin aihe selitetään perusteellisesti tässä artikkelissa. Loimme ensin pyöreän puskurin, selitimme sitten kuinka poistamme pyöreän jonon ja näytimme sitten ympyrän elementit C++:ssa.