A Circular Buffer vagy a Circular queue a normál várólista továbbfejlesztett változata, ahol az utolsó index és a végindex körkörös struktúrában van összekapcsolva. A C++ körkörös puffere két módszert követ: enqueue() és dequeue(). Ezen módszerek alapján hajtjuk végre a körkörös puffer vagy körkörös sor műveletet.
- Az enqueue() metódus ellenőrzi, hogy a puffer megtelt-e. Ellenkező esetben ellenőrizze, hogy a végindex az utolsó. Ha igen, állítsa a farok értékét 0-ra. Ha nem, növelje a farok értékét az index értékével.
- A dequeue() függvény a kör alakú sor elülső indexéből veszi az értéket. Ha a várólista üres, egy üzenet jelenik meg az üres várólista. Ellenkező esetben az utolsó értéket kapja, és törli a sorból.
Program egy körkörös puffer megvalósítására C++ nyelven
Az említett két módszert követve megvalósítjuk a körkörös puffert C++ nyelven. Tekintsük a körkörös sor megvalósításának összes lépését a C++ nyelven.
#include
névtér használata std;
struct MyQueue
{
int fej , farok ;
int Qsize;
int * NewArr;
MyQueue ( int sz ) {
fej = farok = -1 ;
Qsize = sz;
NewArr = új int [ sz ] ;
}
void enQueue ( int val ) ;
int deQueue ( ) ;
érvénytelen showQueue ( ) ;
} ;
A kóddal kezdve először létrehozzuk a „MyQueue” struktúrát a head és a tail változók inicializálására. A fej változó az elülső indexeket, a farok pedig a tömb hátsó hátsó indexeit jelöli. Ezt követően kerül meghatározásra a kör alakú sor mérete, amelyet a „Qsize” változó jelöl.
Ezután meghatározzuk a „NewArr” dinamikusan lefoglalt tömbjét, amely a körkörös sor értékeit tárolja. Ezután meghívjuk a MyQueue()-t, amely egy konstruktor, és átadjuk az „sz” paramétert a kör alakú sor méretéhez. A MyQueue() konstruktoron belül „-1” értéket rendelünk a fej- és farokmutatókhoz. Ez a negatív érték azt jelzi, hogy a sor most üres. Továbbhaladva hozzárendeljük az „sz” értéket, amely a kör alakú sor méretét jelenti. A „NewArr” körkörös sor egy új kulcsszóval van beállítva, hogy létrehozza az egész számokból álló tömböt a megadott „sz” méretben.
Ezután definiáljuk az enQueue() és a dequeue() függvényeket. Az enqueue() beszúrja az értékeket a definiált körkörös sorba a végből. A körkörös sor fejében lévő elemeket azonban a dequeue() függvény kiküszöböli. A showQueue() tagfüggvény megjeleníti a kör alakú sor értékeit.
1. lépés: Hozzon létre egy függvényt az elemek körkörös pufferbe történő beszúrásához
A korábbi lépésben beállítottunk egy osztályt, ahol a privát tagok inicializálásra kerülnek, a privát tagok függvényei pedig a körkörös sor megvalósítására vannak beállítva. Most beállítjuk a függvényt, hogy létrehozza a körkörös sort, és beillesszük az értékeket a körkörös sorba az algoritmus segítségével.
érvénytelen MyQueue::enQueue ( int val ){
ha ( ( fej == 0 && farok == Qsize - 1 ) || ( farok == ( fej - 1 ) % ( Qsize - 1 ) ) )
{
cout << ' \n A sor betelt' ;
Visszatérés ;
}
más ha ( fej == - 1 )
{
fej = farok = 0 ;
NewArr [ farok ] = val;
}
más ha ( farok == Qsize - 1 && fej ! = 0 )
{
farok = 0 ;
NewArr [ farok ] = val;
}
más {
farok ++;
NewArr [ farok ] = val;
}
}
Itt a „MyQueue” osztály „enqueue()” függvényét hívjuk meg, hogy beszúrjuk az elemet a körkörös sorba, ha a sor üres vagy alulcsordult. Az „enqueue()” függvényt a „val” paraméterrel adjuk át, és szúrjuk be az értéket a kör alakú sor végéből. Beállítjuk az „if-else” feltételt, hogy az értékeket beillesszük a körkörös sorba. Az első „if” utasítás, amely az „if ((fej == 0 && tail == Qsize – 1) || (tail == (fej – 1) % (Qsize – 1)))” két feltételt ellenőrzi, hogy a fej a kör alakú sor kezdőpozíciójában, a farok pedig a véghelyzetben van. Ezután ellenőrzi, hogy a farok egy helyzetben van-e a fej hátsó helyzetében. Ha ezen feltételek bármelyike teljesül, a sor nem üres, és a prompt generálja az üzenetet.
Ezután megkapjuk az „else-if” feltételt, amely azonosítja, hogy a sor üres-e. Ha igen, akkor az érték bekerül a sorba. Mivel a fej értéke -1 marad, ez azt mutatja, hogy a sor üres, és az értéket be kell illeszteni a kör alakú sorba. Ehhez a fejet és a farkát 0-ra állítjuk. Ezután a farok pozícióból származó értéket beillesztjük a „NewArr” körkörös sorba.
Ezután van a harmadik „else-if” feltételünk, amely ellenőrzi, hogy a farok a sor utolsó pozíciójában van-e, és a fej nem a sor kezdőpozíciója. Ez a feltétel akkor érvényes, ha a farok eléri a végét, és a kiindulási helyzetben még van hely. Ehhez a fejet 0-ra kell állítanunk, és az elemet a farok pozícióból kell hozzáadni. Végül, ha az összes megadott feltétel nem teljesül, a sor nem üres és nem is tele. Ebben az esetben a farokat 1-gyel növeljük, és az értéket az új farok pozícióból adjuk hozzá.
2. lépés: Hozzon létre egy függvényt az elemek törléséhez a kör alakú pufferből
Az előző kódot úgy állítottuk be, hogy az enqueue() függvény segítségével hozza létre és illessze be az elemeket a kör alakú sorba. Most meghatározzuk az elemek eltávolítását a körkörös pufferből, ha túlcsordul.
int MyQueue::deQueue ( ){
ha ( fej == - 1 )
{
cout << ' \n A sor szabad' ;
Visszatérés INT_MIN;
}
int MyData = NewArr [ fej ] ;
NewArr [ fej ] = -1 ;
ha ( fej == farok )
{
fej = -1 ;
farok = -1 ;
}
más ha ( fej == Qsize - 1 )
fej = 0 ;
más
fej ++;
Visszatérés Adataim;
}
Az adott kódban a „Myqueue” osztályból meghívjuk a dequeue() függvényt, hogy eltávolítsuk az elemet a fejindexből. Tehát megvan az „if” utasítás, amely ellenőrzi, hogy a sor üres-e. A fej a „-1” értékkel van beállítva, amely az üres sort jelképezi. A rendszer azt az üzenetet generálja, hogy a sor üres, majd visszaadja az INT_MIN értéket, amely az int állandó minimális értéke. Az „if” utasítás határozza meg, hogy a sor foglalt-e. Ehhez definiáljuk a „MyData” változót, és beállítjuk az elem értékét a sor elején. Ezután a fejet -1 pozícióba állítjuk, ami azt jelzi, hogy ez az érték eltávolításra került a sorból. Ezt követően ellenőrizzük, hogy a fej és a farok egyenlő-e vagy sem. Ha mindkettő egyenlő, akkor mindkettőhöz „-1” értéket rendelünk, ami az üres kör alakú sort jelképezi. Végül ellenőrizzük, hogy a dequeue() működik-e, ha a fej a sor utolsó indexén van. Ehhez a „0” értékkel állítjuk be, amely a tömb elején körbefordul. Ha a megadott feltételek egyike sem teljesül, a fej értékét megnöveljük, és a sorba állított elemet adjuk vissza.
3. lépés: Hozzon létre egy függvényt a kör alakú puffer elemeinek megjelenítéséhez
Ebben a részben a showQueue() függvényt hívjuk meg a „NewArr” körkörös sor elemeinek megjelenítéséhez.
érvénytelen MyQueue::showQueue ( ){
ha ( fej == - 1 )
{
cout << ' \n A sor szabad' ;
Visszatérés ;
}
cout << ' \n A kör alakú sor elemei: ' ;
ha ( farok > = fej )
{
számára ( int i = fej ; én < = farok ; i++ )
cout << NewArr [ én ] << ' ' ;
}
más
{
számára ( int i = fej ; én < Qsize; i++ )
cout << NewArr [ én ] << ' ' ;
számára ( int i = 0 ; én < = farok ; i++ )
cout << NewArr [ én ] << ' ' ;
}
}
A sor üres állapotát először ellenőrizzük. Ha a sor szabad, megjelenik egy jelzés, hogy a kör alakú sor szabad. Ellenkező esetben a függvény a kör alakú sor elemeit jeleníti meg. Ehhez definiáljuk az „if” utasítást, ahol a farok nagyobb vagy egyenlő, mint a fej. Ez a feltétel úgy van beállítva, hogy kezelje azt az esetet, amikor a körkörös sor nem fejeződött be.
Ebben az esetben a „for” ciklust használjuk a fejtől a végig iteráláshoz, és kinyomtatjuk a kör alakú sor értékeit. A következő eset az, amikor a kör alakú sor elkészül. Ehhez az „if” feltételt használjuk, ahol a farok kisebb, mint a fej. Ezután két ciklust kell használnunk, ahol az első a sor elejétől a sor végéig, a második pedig a vége elejétől iterál.
4. lépés: Hozza létre a Circular Queue Program Main() függvényét
Végül létrehozzuk a program main() függvényét, ahol beszúrunk öt egész számot a kör alakú sorba, és megjelenítjük a sor egész számait. Ezt követően a dequeue() függvény meghívásával megjelenítjük a körkörös sorból törölt egész számokat. Néhány elem sorból történő kivonása után az új elemek beszúrásával az enqueue() függvény segítségével újra kitöltjük a sort.
int fő ( ){
MyQueue azt ( 5 ) ;
// Elemek beillesztése ban ben Körkörös sor
que.enQueue ( tizenegy ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( tizenöt ) ;
// Kijelző elemek jelen vannak ban ben Körkörös sor
que.showQueue ( ) ;
// Elemek törlése a körkörös sorból
cout << ' \n Törölt elem = ' << que.deQueue ( ) ;
cout << ' \n Törölt elem = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
Visszatérés 0 ;
}
Kimenet:
A körkörös sor megvalósításának eredményei a C++ prompt képernyőn jelennek meg.
Következtetés
Összefoglalva, a körkörös puffer témáját ez a cikk részletesen kifejti. Először elkészítettük a kör alakú puffert, majd elmagyaráztuk, hogyan kell törölni a körkörös sorból, majd megjelenítettük a kör elemeit C++ nyelven.