Extraire le dernier élément de la file d'attente prioritaire sans traverser

Présentation

La file d'attente prioritaire en C++ est différente de la file d'attente ordinaire dans la structure de données. Elle présente une différence : tous les éléments sont prioritaires. Nous pouvons extraire ses éléments en parcourant la file d'attente.

Cependant, dans ce tutoriel, nous essayons un moyen d'extraire le dernier élément de la file d'attente prioritaire sans le parcourir. Commençons…

Qu'est-ce que la file d'attente prioritaire ?

Dans les structures de données, les types de données abstraits sont des files d'attente prioritaires. C'est une file d'attente où tous les éléments ont une priorité associée. Tous ses éléments sont supprimés selon leur priorité. Les données avec une priorité plus élevée sont extraites en premier, les données avec une priorité plus faible sont extraites en premier. Les données/éléments de la file d'attente peuvent être des entiers ou des chaînes, mais ne peuvent pas être des valeurs NULL.

Si deux éléments ont la même priorité, la file d'attente prioritaire sera récupérée selon le principe FIFO (premier entré, premier sorti).

Il existe deux types de files d'attente prioritaires dont les éléments peuvent être extraits -

• File d'attente prioritaire ascendante - Dans ce type de file d'attente prioritaire, les éléments sont récupérés par ordre croissant. Les éléments ayant la priorité la plus basse seront supprimés en premier.

• File d'attente prioritaire décroissante - Dans ce type de file d'attente prioritaire, les éléments sont récupérés par ordre croissant. Les éléments ayant la priorité la plus élevée seront supprimés en premier.

Grammaire

 priority_queue<queue_type> queue_name

Ne pas parcourir pour extraire le dernier élément de la file d'attente prioritaire

Ici, nous extrayons le dernier élément de la file d'attente prioritaire sans parcourir toute la file d'attente. Nous implémentons des files d'attente prioritaires via des arbres binaires. Utilisez les méthodes intégrées suivantes pendant ce processus -

• size() - Il renvoie la taille de la file d'attente prioritaire.

  Syntaxe− queue_name .size()

• insert() - Insère un élément dans la file d'attente prioritaire.

  Syntaxe−queue_name.insert(data_type)

• getMin() - Il renvoie l'élément minimum de la file d'attente prioritaire.

  Syntaxe−queue_name.getMin()

• getMax() - Il renvoie le plus grand élément de la file d'attente prioritaire.

  La traduction chinoise de

  Syntaxe − queue_name.getMax()

est :

Syntaxe − queue_name.getMax()

• isEmpty() - Renvoie vrai si la file d'attente est vide.

• deleteMin() −Supprimez le plus petit élément de file d'attente.

  Syntaxe−queue_name.deleteMin()

• deleteMax() - supprime le plus grand élément de file d'attente

  Syntaxe−queue_name.deleteMax()

Algorithme

Étape 1− Créez une classe de structure pour les opérations de file d'attente.

Étape 2− Créez un multiset pour trier automatiquement les éléments.

Étape 3− Insérez l'élément dans la file d'attente prioritaire.

Étape 4− Obtenez les éléments minimum et maximum sans traverser () en utilisant des fonctions intégrées comme getMin() et getMax.

Exemple

Code C++ pour extraire le dernier élément de la file d'attente

#include <bits/stdc++.h>
using namespace std;
  
// declaring a struct class for the Priority Queue
struct PQ  {
   multiset<int> s;
   
   //Getting the size of the Queue
   int size() { 
      return s.size(); 
   }
   
   //Checking Queue is empty or not
   bool isEmpty() { 
      return (s.size() == 0); 
   }
   
   void insert(int i) { 
      s.insert(i); 
   }
  
   //Method to get the smallest element of the Queue
   int getMin() { 
      return *(s.begin()); 
   }
   
   // Method to get the largest Queue element
   int getMax() { 
      return *(s.rbegin()); 
   }
   
   // Deleting Queue elements
   void deleteMin() {
      if (s.size() == 0)
         return;
      
      auto i = s.begin();
      s.erase(i);
   }
      
   // Method to delete the largest element
   void deleteMax() {
      if (s.size() == 0)
      return;
      
      auto i = s.end();
      i--;
      s.erase(i);
   }
};
  
//Main code
int main() {
   PQ p;   //initializing the Priority Queue
   
//inserting Queue elements
   p.insert(20);      
   p.insert(30);
   p.insert(50);
   p.insert(60);
   p.insert(90);
   
   cout << "Smallest Element is: " << p.getMin() << endl;
   cout << "Largest Element is: " << p.getMax() << endl;
   
   p.deleteMin();
   cout << "Smallest Element is: " << p.getMin() << endl;
   
   p.deleteMax();
   cout << "Largest Element is: " << p.getMax() << endl;
   
   cout << "Size of the Queue is: " << p.size() << endl;
   
   cout << "Queue is empty?: "
   << (p.isEmpty() ? "YES" : "NO") << endl;
   
   return 0;
}

Sortie

Smallest Element is: 20
Largest Element is: 90
Smallest Element is: 30
Largest Element is: 50
Queue is Empty?: NO

Conclusion

Les files d'attente prioritaires peuvent être implémentées via des tableaux, des structures de données de tas, des listes chaînées et des arbres binaires. Il permet d’exposer les chemins cachés et divers algorithmes.

C'est la fin de ce tutoriel, j'espère que vous l'avez trouvé significatif.

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!