Comment gérer une file d'attente circulaire complète d'événements en C++ ?

Présentation

Circular Queue est une amélioration de la file d'attente linéaire, qui a été introduite pour résoudre le problème du gaspillage de mémoire dans la file d'attente linéaire. Les files d'attente circulaires utilisent le principe FIFO pour y insérer et supprimer des éléments. Dans ce tutoriel, nous aborderons le fonctionnement d'une file d'attente circulaire et comment la gérer.

Qu'est-ce qu'une file d'attente circulaire ?

La file d'attente circulaire est un autre type de file d'attente dans la structure de données où le front-end et le back-end sont connectés l'un à l'autre. Il est également connu sous le nom de tampon circulaire. Il fonctionne de la même manière qu’une file d’attente linéaire, alors pourquoi devons-nous introduire une nouvelle file d’attente dans la structure des données ?

Lors de l'utilisation d'une file d'attente linéaire, lorsque la file d'attente atteint sa limite maximale, il peut y avoir de l'espace mémoire avant le pointeur de queue. Cela entraîne une perte de mémoire et un bon algorithme devrait être capable d’utiliser pleinement les ressources.

Pour résoudre le problème du gaspillage de mémoire, les développeurs ont introduit le concept de file d'attente circulaire, qui a la capacité de se lier de manière circulaire au backend et au frontend, et peut insérer plus d'éléments.

Fonctions de base de la file d'attente circulaire

• Post - Il renvoie la valeur de publication de la file d'attente.

• Front - Il renvoie la valeur avant de la file d'attente.

• deQueue - Cette méthode intégrée est utilisée pour supprimer des éléments de la file d'attente tout en vérifiant si la file d'attente est vide.

• enQueue - Cette méthode est utilisée pour insérer de nouveaux éléments tout en vérifiant la taille de la file d'attente.

Dans une file d'attente circulaire, les éléments sont ajoutés depuis le backend et supprimés du frontend. deQueue et enQueue sont des fonctions indépendantes de la taille de la file d'attente et sont implémentées à l'aide de l'opérateur modulo. Leur complexité temporelle est O(1).

Gérer la file d'attente circulaire

Nous gérons les files d'attente circulaires en utilisant les opérations enQueue et deQueue. Initialement, la valeur avant de la file d'attente circulaire est 0, la valeur arrière est -1 et tous les éléments de la file d'attente circulaire sont NULL.

Exemple

Code C++, utilisant des tableaux pour implémenter une file d'attente circulaire

#include <bits/stdc++.h>
using namespace std;
 
class Queue {
   //Initializing front and rear of the queue
   int rear, front;
   int sz;
   int* arr;
 
   public:
   Queue(int s) {
      front = rear = -1;
      sz = s;
      arr = new int[s];
   }
   
   void enQueue(int v);
   int deQueue();
   void displayQueue();
};
 
//Circular queue function
void Queue::enQueue(int v) {
   if ((front == 0 && rear == sz - 1)
      || (rear == (front - 1) % (sz - 1))) {
         printf("\nNo Space Queue is Full");
         return;
      }
   
      //Inserting the front element
      else if (front == -1) {
         front = rear = 0;
         arr[rear] = v;
      }
   
      else if (rear == sz - 1 && front != 0) {
         rear = 0;
         arr[rear] = v;
      }
   
      else {
         rear++;
         arr[rear] = v;
      }
}
 
//Function for deleting queue elements
int Queue::deQueue() {
   if (front == -1) {
      printf("\nQueue needs data it is empty");
      return INT_MIN;
   }
   
   int ele = arr[front];
   arr[front] = -1;
   if (front == rear) {
      front = -1;
      rear = -1;
   }
   else if (front == sz - 1)
      front = 0;
   else
      front++;
   return ele;
}
 
//Printing Circular queue elements
void Queue::displayQueue() {
   if (front == -1) {
      printf("\nQueue Empty");
      return;
   }
   printf("\nCircular Queue elements are: \n");
   if (rear >= front) {
      for (int i = front; i <= rear; i++)
      printf("%d ", arr[i]);
   } else {
      for (int i = front; i < sz; i++)
      printf("%d ", arr[i]);
   
      for (int i = 0; i <= rear; i++)
      printf("%d ", arr[i]);
   }
}
 
int main() {
   Queue q(5);
   //Pushing data in circular queue
   q.enQueue(10);
   q.enQueue(20);
   q.enQueue(3);
   q.enQueue(5);
   //Printing circular queue elements
   q.displayQueue();
   
   //Deleting front elements of circular queue
   printf("\nDeleted element = %d\n", q.deQueue());
   printf("\nDeleted element = %d", q.deQueue());
   q.displayQueue();
   q.enQueue(13);
   q.enQueue(27);
   q.enQueue(50);
   q.displayQueue();
   q.enQueue(22);
   
   return 0;
}

Sortie

Circular Queue elements are: 
10 20 3 5 
Deleted element = 10

Deleted element = 20
Circular Queue elements are: 
3 5 
Circular Queue elements are: 
3 5 13 27 50 
No Space Queue is Full

Conclusion

Les files d'attente circulaires sont utilisées dans la gestion de la mémoire et la planification du processeur. Il utilise la fonction displayQueue() pour afficher les éléments de la file d'attente.

Nous avons atteint la fin de ce tutoriel. J'espère que ce tutoriel vous a aidé à comprendre comment implémenter une file d'attente circulaire.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!