Il buffer circolare o coda circolare è la versione avanzata della coda normale in cui l'ultimo indice e l'indice di coda sono collegati in una struttura circolare. Il buffer circolare in C++ segue due metodi: enqueue() e dequeue(). Eseguiamo l'operazione del buffer circolare o della coda circolare in base a questi metodi.
- Il metodo enqueue() controlla se il buffer è pieno. Altrimenti verifica che l'indice finale sia l'ultimo. In tal caso, impostare il valore della coda su 0. In caso contrario, aumentare il valore della coda del valore di quell'indice.
- La funzione dequeue() prende il valore dall'indice anteriore nella coda circolare. Se la coda è vuota, un messaggio visualizzerà la coda vuota. Altrimenti, ottiene l'ultimo valore e lo elimina dalla coda.
Programma per implementare un buffer circolare in C++
Seguendo i due metodi menzionati, implementiamo il buffer circolare in C++. Consideriamo tutti i passaggi per l'implementazione della coda circolare in C++.
#include
utilizzando lo spazio dei nomi std;
struttura MyQueue
{
int Testa , coda ;
int Qdimensione;
int * NuovoArr;
MyQueue ( int no ) {
Testa = coda = -1 ;
Qdimensione = dimensione;
NuovoArr = nuovo interno [ S ] ;
}
void enQueue ( val.int ) ;
int deQueue ( ) ;
void showQueue ( ) ;
} ;
A partire dal codice, creiamo prima la struttura “MyQueue” per inizializzare le variabili head e tail. La variabile head rappresenta gli indici anteriori e la coda rappresenta gli indici posteriori posteriori di un array. Successivamente viene definita la dimensione della coda circolare, indicata dalla variabile “Qsize”.
Quindi, definiamo l'array allocato dinamicamente di 'NewArr' che memorizza i valori della coda circolare. Successivamente, chiamiamo MyQueue() che è un costruttore e passiamo il parametro 'sz' per la dimensione della coda circolare. All'interno del costruttore MyQueue(), assegniamo il valore '-1' ai puntatori head e tail. Questo valore negativo indica che la coda ora è vuota. Andando avanti, assegniamo il valore “sz” che rappresenta la dimensione della coda circolare. La coda circolare 'NewArr' viene impostata con una nuova parola chiave per creare l'array di numeri interi all'interno della dimensione 'sz' specificata.
Quindi, definiamo le funzioni enQueue() e dequeue(). L'enqueue() inserisce i valori nella coda circolare definita dalla coda. Tuttavia, gli elementi nella testa della coda circolare vengono eliminati dalla funzione dequeue(). La funzione membro showQueue() visualizza i valori della coda circolare.
Passaggio 1: creare una funzione per inserire gli elementi in un buffer circolare
Nel passaggio precedente, impostiamo una classe in cui i membri privati vengono inizializzati e le funzioni dei membri privati vengono impostate per implementare la coda circolare. Ora impostiamo la funzione per creare la coda circolare e inseriamo i valori all'interno della coda circolare utilizzando l'algoritmo.
void MyQueue::enQueue ( val.int ){
Se ( ( Testa == 0 && coda == Qdimensione - 1 ) || ( coda == ( Testa - 1 ) % ( Qdimensione- 1 ) ) )
{
cout << ' \N La coda è piena' ;
ritorno ;
}
altro Se ( Testa == - 1 )
{
Testa = coda = 0 ;
NuovoArr [ coda ] = val;
}
altro Se ( coda == Qdimensione - 1 && Testa ! = 0 )
{
coda = 0 ;
NuovoArr [ coda ] = val;
}
altro {
coda ++;
NuovoArr [ coda ] = val;
}
}
Qui chiamiamo la funzione “enqueue()” dalla classe “MyQueue” per inserire l'elemento nella coda circolare se la coda è vuota o underflow. La funzione “enqueue()” viene passata con il parametro “val” e inserisce il valore dalla coda della coda circolare. Impostiamo la condizione 'if-else' per inserire i valori nella coda circolare per questo. La prima istruzione 'if' che è 'if ((head == 0 && tail == Qsize – 1) || (tail == (head – 1) % (Qsize – 1)))' controlla due condizioni se l'head è nella posizione iniziale e la coda è nella posizione finale della coda circolare. Quindi, controlla se la coda è in una posizione dietro la testa. Se una qualsiasi di queste condizioni è soddisfatta, la coda non è vuota e il prompt genera il messaggio.
Successivamente, abbiamo la condizione “else-if” che identifica se la coda è vuota. In tal caso il valore viene inserito nella coda. Poiché l'intestazione viene mantenuta uguale a -1, ciò indica che la coda è vuota e il valore deve essere inserito nella coda circolare. Per questo, impostiamo head e tail uguali a 0. Quindi, inseriamo il valore dalla posizione tail nella coda circolare 'NewArr'.
Poi, abbiamo la nostra terza condizione “else-if” che controlla se la coda è nell’ultima posizione della coda e la testa non è la posizione iniziale della coda. Questa condizione si applica quando la coda raggiunge la fine e la posizione iniziale ha ancora spazio. Per questo, dobbiamo impostare la testa su 0 e l'elemento viene aggiunto dalla posizione della coda. Infine, se non vengono soddisfatte tutte le condizioni indicate, la coda non sarà né vuota né piena. In questo caso, incrementiamo la coda di 1 e il valore viene aggiunto dalla nuova posizione della coda.
Passaggio 2: crea una funzione per eliminare gli elementi dal buffer circolare
Impostiamo il codice precedente per creare e inserire gli elementi nella coda circolare utilizzando la funzione enqueue(). Ora definiamo l'implementazione della rimozione degli elementi dal buffer circolare in caso di overflow.
int MyQueue::deQueue ( ){
Se ( Testa == - 1 )
{
cout << ' \N La coda è gratuita' ;
ritorno INT_MIN;
}
int MieiDati = NuovoArr [ Testa ] ;
NuovoArr [ Testa ] = -1 ;
Se ( Testa == coda )
{
Testa = -1 ;
coda = -1 ;
}
altro Se ( Testa == Qdimensione - 1 )
Testa = 0 ;
altro
Testa ++;
ritorno I miei dati;
}
Nel codice fornito, chiamiamo la funzione dequeue() dalla classe “Myqueue” per rimuovere l'elemento dall'indice head. Quindi, abbiamo l'istruzione 'if' che controlla se la coda è vuota. L'intestazione è impostata con il valore “-1” che rappresenta la coda vuota. Viene generato il messaggio che la coda è vuota e quindi restituisce INT_MIN che è il valore minimo costante per un int. L'istruzione 'if' determina se la coda non è occupata. Per questo, definiamo la variabile “MyData” e impostiamo il valore dell’elemento in testa alla coda. Quindi, impostiamo la testa sulla posizione -1 che indica che questo valore viene rimosso dalla coda. Successivamente controlliamo se la testa e la coda sono uguali o meno. Se entrambi sono uguali, assegniamo ad entrambi il valore “-1”, che rappresenta la coda circolare vuota. Infine, controlliamo se dequeue() funziona se head si trova all'ultimo indice della coda. Per questo, lo impostiamo con il valore '0' che si ripete all'inizio dell'array. Se nessuna delle condizioni indicate è vera, il valore di head viene incrementato e viene restituito l'elemento deaccodato.
Passaggio 3: crea una funzione per mostrare gli elementi del buffer circolare
In questa sezione chiamiamo la funzione showQueue() per visualizzare gli elementi della coda circolare “NewArr”.
void MyQueue::showQueue ( ){
Se ( Testa == - 1 )
{
cout << ' \N La coda è gratuita' ;
ritorno ;
}
cout << ' \N Elementi della coda circolare: ' ;
Se ( coda > = Testa )
{
per ( int io = Testa ; io < = coda ; i++ )
cout << NuovoArr [ io ] << ' ' ;
}
altro
{
per ( int io = Testa ; io < Qdimensione; i++ )
cout << NuovoArr [ io ] << ' ' ;
per ( int io = 0 ; io < = coda ; i++ )
cout << NuovoArr [ io ] << ' ' ;
}
}
Viene prima verificato lo stato vuoto della coda. Se la coda è libera viene visualizzata un'indicazione che la coda circolare è libera. Altrimenti la funzione mostrerà gli elementi della coda circolare. Per questo definiamo l'istruzione 'se' in cui abbiamo la coda maggiore o uguale alla testa. Questa condizione è impostata per gestire il caso in cui la coda circolare non viene completata.
In questo caso, utilizziamo il ciclo “for” per scorrere dalla testa alla coda e stampare i valori della coda circolare. Il caso successivo è quello in cui la coda circolare viene completata. Per questo controlliamo utilizzando la condizione “se” in cui la coda è inferiore alla testa. Quindi, dobbiamo utilizzare due cicli in cui il primo itera dalla testa alla fine della coda e il secondo itera dall'inizio della coda.
Passaggio 4: creare la funzione Main() del programma Circular Queue
Infine, creiamo la funzione main() del programma in cui inseriamo cinque numeri interi nella coda circolare e visualizziamo i numeri interi della coda. Successivamente, mostriamo gli interi cancellati dalla coda circolare chiamando la funzione dequeue(). Dopo aver rimosso dalla coda alcuni elementi, riempiamo nuovamente la coda inserendo i nuovi elementi utilizzando la funzione enqueue().
int principale ( ){
MyQueue quello ( 5 ) ;
// Inserimento di elementi In Coda circolare
que.enQueue ( undici ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( quindici ) ;
// Elementi di visualizzazione presenti In Coda circolare
que.showQueue ( ) ;
// Eliminazione di elementi dalla coda circolare
cout << ' \N Elemento eliminato = ' << que.deQueue ( ) ;
cout << ' \N Elemento eliminato = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
ritorno 0 ;
}
Produzione:
I risultati dell'implementazione della coda circolare vengono visualizzati nella schermata del prompt di C++.
Conclusione
In conclusione, l'argomento del buffer circolare è spiegato in modo approfondito in questo articolo. Abbiamo prima creato il buffer circolare, poi spiegato come eliminare dalla coda circolare e quindi visualizzato gli elementi del circolare in C++.