c circular queue data structure
Ce didacticiel sur la structure de données de la file d'attente circulaire C ++ explique ce qu'est la file d'attente circulaire, quelles sont les opérations de base avec l'implémentation et les applications:
Une file d'attente circulaire est une extension de la file d'attente de base dont nous avons parlé précédemment. Il est également connu sous le nom de «tampon en anneau».
Qu'est-ce que la file d'attente circulaire en C ++?
Une file d'attente circulaire est une structure de données linéaire utilisée pour stocker des éléments de données. Il effectue des opérations en suivant l'approche FIFO (First In, First Out) et la dernière position de la file d'attente est reliée à la première position pour former un cercle.
=> Recherchez la série complète de formations C ++ ici
Ce que vous apprendrez:
File d'attente circulaire en C ++
Le diagramme suivant montre une file d'attente circulaire.
L'image ci-dessus montre une structure de données circulaire de taille 10. Les six premiers éléments sont déjà dans la file d'attente et nous voyons que la première position et la dernière position sont jointes. Grâce à cette disposition, l’espace n’est pas gaspillé comme dans une file d’attente linéaire.
que faire des fichiers .torrent
Dans une file d'attente linéaire une fois que la file d'attente est pleine, nous supprimons les éléments d'une autre extrémité, et l'état de la file d'attente est toujours affiché comme plein et nous ne pouvons pas insérer plus d'éléments.
Dans la file d'attente circulaire, lorsque la file d'attente est pleine, et lorsque l'on enlève des éléments de l'avant puisque la dernière et la première positions sont connectées, on peut insérer les éléments à l'arrière qui ont été libérés en supprimant l'élément.
Dans la section suivante, nous découvrirons les opérations de base de la file d'attente circulaire.
Opérations de base
Certaines des opérations de base de la file d'attente circulaire sont les suivantes:
Devant: Renvoie la position avant dans la file d'attente circulaire.
Arrière: Renvoie la position arrière dans la file d'attente circulaire.
Mettre en file d'attente: Enqueue (valeur) est utilisé pour insérer un élément dans la file d'attente circulaire. L'élément est toujours inséré à l'arrière de la file d'attente.
Nous suivons la séquence d'étapes suivante pour insérer un nouvel élément dans la file d'attente circulaire.
#1) Vérifiez si la file d'attente circulaire est pleine: test ((arrière == SIZE-1 && avant == 0) || (arrière == avant-1)), où «SIZE» est la taille de la file d'attente circulaire.
#deux) Si la file d'attente circulaire est pleine, elle affiche le message «La file d'attente est pleine». Si la file d'attente n'est pas pleine, vérifiez si (arrière == SIZE - 1 && avant! = 0). Si c'est vrai, définissez back = 0 et insérez l'élément.
Retirer la file d'attente: La fonction Dequeue est utilisée pour supprimer un élément de la file d'attente. Dans la file d'attente circulaire, l'élément est toujours supprimé du frontal. Vous trouverez ci-dessous la séquence d'opération de retrait de la file d'attente dans une file d'attente circulaire.
Pas:
#1) Vérifiez si la file d'attente circulaire est vide: vérifiez si (front == - 1).
#deux) S'il est vide, affichez le message «La file d'attente est vide». Si la file d'attente n'est pas vide, effectuez l'étape 3.
# 3) Vérifiez si (avant == arrière). Si c'est vrai, définissez avant = arrière = -1 sinon vérifiez si (avant == taille-1), si c'est vrai, définissez front = 0 et renvoyez l'élément.
Illustration
Dans cette section, nous allons passer par une illustration détaillée de l'ajout / suppression d'éléments dans la file d'attente circulaire.
Considérez la file d'attente circulaire suivante de 5 éléments, comme indiqué ci-dessous:
Ensuite, nous insérons l'élément 1 dans la file d'attente.
Le meilleur VPN reddit
Ensuite, nous insérons un élément avec la valeur 3.
Lorsque nous insérons les éléments pour remplir une file d'attente, la représentation sera comme ci-dessous.
Maintenant, nous supprimons les deux éléments, à savoir l'élément 1 et l'élément 3 de la file d'attente, comme indiqué ci-dessous.
Ensuite, nous insérons ou mettons l'élément 11 en file d'attente dans la file d'attente circulaire comme représenté ci-dessous.
Insérons à nouveau l'élément 13 dans la file d'attente circulaire. La file d'attente ressemblera à celle ci-dessous.
Nous voyons que dans la file d'attente circulaire, nous déplaçons ou insérons des éléments dans un cercle. Par conséquent, nous pouvons consommer tout l'espace de la file d'attente jusqu'à ce qu'elle soit pleine.
Mise en œuvre
Implémentons la file d'attente circulaire à l'aide de C ++.
#include using namespace std; class Queue { public: // Initialize front and rear int rear, front; // Circular Queue int size; int *circular_queue; Queue(int sz) { front = rear = -1; size = sz; circular_queue = new int(sz); } void enQueue(int elem); int deQueue(); void displayQueue(); }; /* Function to create Circular queue */ void Queue::enQueue(int elem) { if ((front == 0 && rear == size-1) || (rear == (front-1)%(size-1))) { cout<<'
Queue is Full'; return; } else if (front == -1) { /* Insert First Element */ front = rear = 0; circular_queue(rear) = elem; } else if (rear == size-1 && front != 0) { rear = 0; circular_queue(rear) = elem; } else { rear++; circular_queue(rear) = elem; } } // Function to delete element from Circular Queue int Queue::deQueue() { if (front == -1) { cout<<'
Queue is Empty'; return -1; } int data = circular_queue(front); circular_queue(front) = -1; if (front == rear) { front = -1; rear = -1; } else if (front == size-1) front = 0; else front++; return data; } //display elements of Circular Queue void Queue::displayQueue() { if (front == -1) { cout<<'
Queue is Empty'<= front) { for (int i = front; i <= rear; i++) cout< Ci-dessus, la sortie des opérations de file d'attente circulaire. Tout d'abord, nous ajoutons les éléments, puis retirons ou supprimons deux éléments. Ensuite, nous insérons ou mettons en file d'attente trois autres éléments dans la file d'attente circulaire. On voit que contrairement à la file d'attente linéaire, les éléments sont ajoutés à la fin de la file d'attente.
Implémentation de liste liée
Parlons maintenant de la mise en œuvre d'une liste liée d'une file d'attente circulaire. Vous trouverez ci-dessous l'implémentation de la liste chaînée de la file d'attente circulaire en C ++. Notez que nous utilisons struct pour représenter chaque nœud. Les opérations sont les mêmes que celles décrites précédemment, sauf que dans ce cas, nous devons les effectuer par rapport aux nœuds de la liste chaînée.
La sortie affiche la file d'attente circulaire après l'opération de mise en file d'attente, de retrait de la file d'attente et également après la deuxième opération de mise en file d'attente.
#include using namespace std; struct Node { int data; struct Node* link; }; struct PQueue { struct Node *front, *rear; }; /* this functions performs enqueue operation for circular queue */ void enQueue(PQueue *pq,int elem) { struct Node *temp = new Node; temp->data = elem; if (pq->front == NULL) pq->front = temp; else pq->rear->link = temp; pq->rear = temp; pq->rear->link = pq->front; } // This function performs dequeue operation for Circular Queue int deQueue(PQueue *pq) { if (pq->front == NULL) { cout<<'Queue is empty!!'; return -1; } int elem; // item to be dequeued // item is the last node to be deleted if (pq->front == pq->rear) { elem = pq->front->data; free(pq->front); pq->front = NULL; pq->rear = NULL; } else //more than one nodes { struct Node *temp = pq->front; elem = temp->data; pq->front = pq->front->link; pq->rear->link= pq->front; free(temp); } return elem ; } //display elements of Circular Queue void displayQueue(struct PQueue *pq) { struct Node *temp = pq->front; while (temp->link != pq->front) { cout<data<<' '; temp = temp->link; } cout<data; } //main program int main() { // Create a circular queue and initialize front and rear PQueue *pq = new PQueue; pq->front = pq->rear = NULL; // Insert/enqueue elements in Circular Queue enQueue(pq, 1); enQueue(pq, 3); enQueue(pq, 5); cout<<'
Circular Queue elements after enqueue operation: '; // Display elements in Circular Queue displayQueue(pq); // Delete/dequeue elements from Circular Queue cout<<'
Dequeued Item: '< Production:
La prochaine implémentation est un programme Java pour illustrer la file d'attente circulaire à l'aide de la liste liée.
import java.util.* ; class Main { // Node structure static class Node { int data; Node link; } static class CQueue { Node front, rear; } // Enqueue operation for circular queue static void enQueue(CQueue cq, int value) { Node temp = new Node(); temp .data = value; if (cq .front == null) cq .front = temp; else cq .rear .link = temp; cq .rear = temp; cq .rear .link = cq .front; } // Dequeue operation for Circular Queue static int deQueue(CQueue cq) { if (cq .front == null) { System.out.printf ('Queue is empty!!'); return Integer.MIN_VALUE; } int value; // Value to be dequeued // the last node to be deleted if (cq.front == cq.rear) { value = cq.front.data; cq.front = null; cq.rear = null; } else { // There are more than one nodes Node temp = cq.front; value = temp.data; cq.front = cq.front.link; cq.rear.link= cq.front; } return value ; } // display the elements of Circular Queue static void displayQueue( CQueue cq) { Node temp = cq.front; while (temp.link != cq.front) { System.out.printf('%d ', temp.data); temp = temp.link; } System.out.printf('%d', temp.data); } /* main program */ public static void main(String args()) { // Create a queue and initialize front and rear CQueue cq = new CQueue(); cq.front = cq.rear = null; // Insert/enqueue elements in Circular Queue enQueue(cq, 2); enQueue(cq, 4); enQueue(cq, 6); System.out.print('
Circular Queue elements after Enqueue Operation:'); // Display elements in Circular Queue displayQueue(cq); // Delete/dequeue elements from Circular Queue System.out.printf('
Dequeued Item = %d', deQueue(cq)); System.out.printf('
Dequeued Item = %d', deQueue(cq)); System.out.print('
Circular Queue elements after Dequeue Operation:'); displayQueue(cq); enQueue(cq, 8); enQueue(cq, 10); System.out.print('
Circular Queue elements after second Enqueue Operation:'); displayQueue(cq); } } Production:
La sortie du programme ci-dessus est similaire au programme précédent.
Applications
Discutons de certaines des applications de la file d'attente circulaire.
- Planification du processeur: Les processus du système d'exploitation qui nécessitent qu'un événement se produise ou que certains autres processus se terminent pour l'exécution sont souvent conservés dans une file d'attente circulaire afin qu'ils s'exécutent les uns après les autres lorsque toutes les conditions sont remplies ou lorsque tous les événements se produisent.
- Gestion de la mémoire: L'utilisation de files d'attente ordinaires gaspille de l'espace mémoire comme déjà mentionné dans notre discussion ci-dessus. L'utilisation d'une file d'attente circulaire pour la gestion de la mémoire est bénéfique pour une utilisation optimale de la mémoire.
- Système de signalisation routière contrôlé par ordinateur: Les feux de circulation informatisés sont souvent ajoutés à une file d'attente circulaire afin qu'ils se répètent après que l'intervalle de temps spécifié se soit écoulé.
Conclusion
Les files d'attente circulaires corrigent l'inconvénient majeur d'une file d'attente normale dans laquelle nous ne pouvons pas insérer d'éléments lorsque le pointeur arrière est à la fin de la file d'attente même lorsque nous supprimons les éléments et que l'espace est vidé. Dans une file d'attente circulaire, les éléments sont disposés de manière circulaire, de sorte que l'espace n'est pas du tout gaspillé.
Nous avons également vu les opérations majeures de la file d'attente circulaire. Les files d'attente circulaires sont principalement utiles à des fins de planification et pour des applications telles que les systèmes de signalisation routière où les signaux brillent à tour de rôle.
qu'est-ce que le test de la boîte blanche avec l'exemple
Dans notre prochain didacticiel, nous découvrirons les files d'attente doubles qui sont simplement appelées «deque».
=> Visitez ici pour apprendre le C ++ à partir de zéro
lecture recommandée
- Structure de données de file d'attente en C ++ avec illustration
- Structure de données de file d'attente prioritaire en C ++ avec illustration
- Structure de données de liste liée circulaire en C ++ avec illustration
- Tutoriel Data Mart - Types, exemples et implémentation de Data Mart
- Empiler la structure de données en C ++ avec illustration
- Exemples d'exploration de données: applications les plus courantes de l'exploration de données 2021
- Structure de données d'arbre binaire en C ++
- File d'attente prioritaire dans STL
