Le tampon circulaire ou file d'attente circulaire est la version avancée de la file d'attente normale où le dernier index et l'index de queue sont connectés dans une structure circulaire. Le tampon circulaire en C++ suit deux méthodes : enqueue() et dequeue(). Nous effectuons l’opération de tampon circulaire ou de file d’attente circulaire sur la base de ces méthodes.
- La méthode enqueue() vérifie si le tampon est rempli. Sinon, vérifiez que l'index de fin est le dernier. Si tel est le cas, définissez la valeur de queue sur 0. Sinon, augmentez la valeur de queue de la valeur à cet index.
- La fonction dequeue() prend la valeur de l'index avant dans la file d'attente circulaire. Si la file d'attente est vide, un message affichera cette file d'attente vide. Sinon, il récupère la dernière valeur et la supprime de la file d'attente.
Programme pour implémenter un tampon circulaire en C++
En suivant les deux méthodes mentionnées, nous implémentons le tampon circulaire en C++. Considérons toutes les étapes de l'implémentation de la file d'attente circulaire en C++.
#include
en utilisant l'espace de noms std ;
struct MaQueue
{
int tête , queue ;
int Qsize;
int * NouveauArr;
Ma file d'attente ( numéro international ) {
tête = queue = -1 ;
Qsize = taille ;
NewArr = nouvel entier [ s ] ;
}
annuler la mise en file d'attente ( valeur int ) ;
int deQueue ( ) ;
vide showQueue ( ) ;
} ;
En commençant par le code, nous créons d'abord la structure « MyQueue » pour initialiser les variables head et tail. La variable head représente les indices avant et la queue représente les indices arrière-arrière d’un tableau. Après cela, la taille de la file d'attente circulaire, indiquée par la variable « Qsize », est définie.
Ensuite, nous définissons le tableau alloué dynamiquement de « NewArr » qui stocke les valeurs de la file d'attente circulaire. Ensuite, nous appelons MyQueue() qui est un constructeur et passons le paramètre « sz » pour la taille de la file d'attente circulaire. Dans le constructeur MyQueue(), nous attribuons la valeur « -1 » aux pointeurs de tête et de queue. Cette valeur négative indique que la file d'attente est désormais vide. À l'avenir, nous attribuons la valeur « sz » qui représente la taille de la file d'attente circulaire. La file d'attente circulaire « NewArr » est définie avec un nouveau mot-clé pour créer le tableau d'entiers dans la taille « sz » spécifiée.
Ensuite, nous définissons les fonctions enQueue() et dequeue(). Le enqueue() insère les valeurs dans la file d'attente circulaire définie à partir de la queue. Cependant, les éléments en tête de file d’attente circulaire sont éliminés par la fonction dequeue(). La fonction membre showQueue() affiche les valeurs de la file d'attente circulaire.
Étape 1 : Créer une fonction pour insérer les éléments dans un tampon circulaire
À l'étape précédente, nous avons défini une classe dans laquelle les membres privés sont initialisés et les fonctions des membres privés sont définies pour implémenter la file d'attente circulaire. Maintenant, nous définissons la fonction pour créer la file d'attente circulaire et insérons les valeurs dans la file d'attente circulaire à l'aide de l'algorithme.
annuler MyQueue ::enQueue ( valeur int ){
si ( ( tête == 0 && queue == Qtaille - 1 ) || ( queue == ( tête - 1 ) % ( Qsize- 1 ) ) )
{
cout << ' \n La file d'attente est remplie' ;
retour ;
}
autre si ( tête == - 1 )
{
tête = queue = 0 ;
NouveauArr [ queue ] = val;
}
autre si ( queue == Qtaille - 1 && tête ! = 0 )
{
queue = 0 ;
NouveauArr [ queue ] = val;
}
autre {
queue ++ ;
NouveauArr [ queue ] = val;
}
}
Ici, nous appelons la fonction « enqueue() » de la classe « MyQueue » pour insérer l'élément dans la file d'attente circulaire si la file d'attente est vide ou sous-débordée. La fonction « enqueue() » est passée avec le paramètre « val » et insère la valeur de la queue de la file d'attente circulaire. Nous définissons la condition « if-else » pour insérer les valeurs dans la file d'attente circulaire à cet effet. La première instruction « if » qui est « if ((head == 0 && tail == Qsize – 1) || (tail == (head – 1) % (Qsize – 1))) » vérifie deux conditions si la tête est à la position de début et la queue est à la position de fin de la file d'attente circulaire. Ensuite, il vérifie si la queue est dans une position à l’arrière de la tête. Si l'une de ces conditions est remplie, la file d'attente n'est pas vide et l'invite génère le message.
Ensuite, nous avons la condition « else-if » qui identifie si la file d'attente est vide. Si tel est le cas, la valeur est insérée dans la file d'attente. Comme la tête reste égale à -1, cela montre que la file d'attente est vide et que la valeur doit être insérée dans la file d'attente circulaire. Pour cela, nous définissons la tête et la queue égales à 0. Ensuite, nous insérons la valeur de la position de la queue dans la file d'attente circulaire « NewArr ».
Ensuite, nous avons notre troisième condition « else-if » qui vérifie si la queue est à la dernière position de la file d'attente et si la tête n'est pas la position de départ de la file d'attente. Cette condition s'applique lorsque la queue atteint la fin et que la position de départ a encore de l'espace. Pour cela, nous devons mettre la tête à 0 et l'élément est ajouté à partir de la position de queue. Enfin, si toutes les conditions données ne sont pas remplies, la file d'attente n'est ni vide ni pleine. Dans ce cas, nous incrémentons la queue de 1 et la valeur est ajoutée à partir de la nouvelle position de la queue.
Étape 2 : Créez une fonction pour supprimer les éléments du tampon circulaire
Nous définissons le code précédent pour créer et insérer les éléments dans la file d'attente circulaire à l'aide de la fonction enqueue(). Maintenant, nous définissons l'implémentation de la suppression des éléments du tampon circulaire en cas de débordement.
int MaQueue ::deQueue ( ){
si ( tête == - 1 )
{
cout << ' \n La file d'attente est gratuite' ;
retour INT_MIN ;
}
int MesDonnées = NouvelleArr [ tête ] ;
NouveauArr [ tête ] = -1 ;
si ( tête == queue )
{
tête = -1 ;
queue = -1 ;
}
autre si ( tête == Qtaille - 1 )
tête = 0 ;
autre
tête ++ ;
retour Mes données;
}
Dans le code donné, nous appelons la fonction dequeue() de la classe « Myqueue » pour supprimer l'élément de l'index principal. Nous avons donc l'instruction « if » qui vérifie si la file d'attente est vide. La tête est définie avec la valeur « -1 » qui représente la file d'attente vide. Le message est généré indiquant que la file d'attente est vide, puis renvoie le INT_MIN qui est la valeur minimale constante pour un int. L'instruction « if » détermine si la file d'attente est inoccupée. Pour cela, nous définissons la variable « MyData » et fixons la valeur de l'élément en tête de file d'attente. Ensuite, nous plaçons la tête à la position -1, ce qui indique que cette valeur est supprimée de la file d'attente. Après cela, nous vérifions si la tête et la queue sont égales ou non. Si les deux sont égaux, nous attribuons la valeur « -1 » aux deux, représentant la file d'attente circulaire vide. Enfin, nous vérifions si la fonction dequeue() fonctionne si la tête est au dernier index de la file d'attente. Pour cela, nous le définissons avec la valeur « 0 » qui boucle au début du tableau. Si aucune des conditions données n'est vraie, la valeur de la tête est incrémentée et l'élément retiré de la file d'attente est renvoyé.
Étape 3 : Créer une fonction pour afficher les éléments du tampon circulaire
Dans cette section, nous appelons la fonction showQueue() pour afficher les éléments de la file d'attente circulaire « NewArr ».
annuler MyQueue :: showQueue ( ){
si ( tête == - 1 )
{
cout << ' \n La file d'attente est gratuite' ;
retour ;
}
cout << ' \n Éléments de la file d'attente circulaire : ' ;
si ( queue > = tête )
{
pour ( int je = tête ; je < = queue ; je++ )
cout << NouveauArr [ je ] << ' ' ;
}
autre
{
pour ( int je = tête ; je < Qsize ; je++ )
cout << NouveauArr [ je ] << ' ' ;
pour ( int je = 0 ; je < = queue ; je++ )
cout << NouveauArr [ je ] << ' ' ;
}
}
L’état vide de la file d’attente est d’abord vérifié. Une indication indiquant que la file d'attente circulaire est libre s'affiche si la file d'attente est libre. Sinon, la fonction affichera les éléments de la file d'attente circulaire. Pour cela, nous définissons l'instruction « if » où nous avons la queue qui est supérieure ou égale à la tête. Cette condition est définie pour gérer le cas où la file d'attente circulaire n'est pas terminée.
Pour ce cas, nous utilisons la boucle « for » pour itérer de la tête à la queue et imprimer les valeurs de la file d'attente circulaire. Le cas suivant est celui où la file d'attente circulaire est terminée. Pour cela, nous vérifions en utilisant la condition « if » où la queue est inférieure à la tête. Ensuite, nous devons utiliser deux boucles où la première itère de la tête jusqu'à la fin de la file d'attente et la seconde itère depuis le début de la queue.
Étape 4 : Créer la fonction Main() du programme de file d'attente circulaire
Enfin, nous créons la fonction main() du programme dans laquelle nous insérons cinq entiers dans la file d'attente circulaire et affichons les entiers de la file d'attente. Après cela, nous montrons les entiers supprimés de la file d'attente circulaire en appelant la fonction dequeue(). Après avoir retiré quelques éléments de la file d'attente, nous remplissons à nouveau la file d'attente en insérant les nouveaux éléments à l'aide de la fonction enqueue().
int main ( ){
Ma Queue qui ( 5 ) ;
// Insertion d'éléments dans File d'attente circulaire
que.enQueue ( onze ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( quinze ) ;
// Éléments d'affichage présents dans File d'attente circulaire
que.showQueue ( ) ;
// Suppression d'éléments de la file d'attente circulaire
cout << ' \n Élément supprimé = ' << que.deQueue ( ) ;
cout << ' \n Élément supprimé = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
retour 0 ;
}
Sortir:
Les résultats de l'implémentation de la file d'attente circulaire sont affichés sur l'écran d'invite C++.
Conclusion
En conclusion, le sujet du tampon circulaire est expliqué en profondeur dans cet article. Nous avons d'abord créé le tampon circulaire, puis expliqué comment supprimer de la file d'attente circulaire, puis affiché les éléments de la circulaire en C++.