Afin d'utiliser la file d'attente prioritaire C++, le programme doit commencer par un code tel que :
#comprendre
#comprendre
à l'aide de espace de nomsles heures;
Il inclut la bibliothèque de files d'attente dans le programme.
Afin de continuer à lire, le lecteur doit avoir une connaissance de base du C++.
Contenu de l'article
- Construction de base
- Fonctions membres importantes
- Autres fonctions de file d'attente prioritaire
- Données de chaîne
- Autres constructions de file d'attente prioritaires
- Conclusion
Construction de base
La structure de données doit d'abord être construite avant de pouvoir être utilisée. La construction signifie ici instancier un objet de la classe de file d'attente de la bibliothèque. L'objet file d'attente doit alors avoir un nom qui lui est attribué par le programmeur. La syntaxe la plus simple pour créer une file d'attente prioritaire est :
File d'attente de priorité<taper>nom de file d'attente;
Avec cette syntaxe, la plus grande valeur est supprimée en premier. Un exemple d'instanciation est :
File d'attente de priorité<entier>pq;ou
File d'attente de priorité<carboniser>pq;
Le vecteur et le deque sont deux structures de données en C++. Une priorité_queue peut être créée avec l'un ou l'autre. La syntaxe pour créer une file d'attente prioritaire à partir de la structure vectorielle est :
File d'attente de priorité<type, vecteur<même type>, comparer>pq;Un exemple de cette instanciation est :
File d'attente de priorité<entier, vecteur<entier>, moins<entier> >pq;Notez l'écart entre > et > à la fin de la déclaration. Ceci afin d'éviter toute confusion avec >>. Le code de comparaison par défaut est less, ce qui signifie que la plus grande, et pas nécessairement la première valeur, serait supprimée en premier. Ainsi, la déclaration de création peut simplement être écrite comme:
File d'attente de priorité<entier, vecteur<entier> >pq;Si la plus petite valeur doit être supprimée en premier, alors l'instruction doit être :
File d'attente de priorité<entier, vecteur<entier>, plus grand<entier> >pq;Fonctions membres importantes
La fonction push()
Cette fonction pousse une valeur, qui est son argument, dans la priorité_queue. Il renvoie le vide. Le code suivant illustre cela :
pq.pousser(dix);
pq.pousser(30);
pq.pousser(vingt);
pq.pousser(cinquante);
pq.pousser(40);
Cette priorité_queue a reçu 5 valeurs entières dans l'ordre de 10, 30, 20, 50, 40. Si tous ces éléments doivent être extraits de la file d'attente prioritaire, ils sortiront dans l'ordre de 50, 40, 30, 20, 10.
La fonction pop()
Cette fonction supprime de la priorité_queue la valeur avec la priorité la plus élevée. Si le code de comparaison est supérieur, il supprimera l'élément avec la valeur la plus petite. S'il est appelé à nouveau, il supprime l'élément suivant avec la plus petite valeur du reste ; appelé à nouveau, il supprime la prochaine plus petite valeur présente, et ainsi de suite. Il renvoie le vide. Le code suivant illustre cela :
pq.pousser('à');pq.pousser('c');pq.pousser('b');pq.pousser('Et');pq.pousser('ré');
Notez que pour appeler une fonction membre, le nom de l'objet doit être suivi d'un point, puis de la fonction.
La fonction top()
Les pop () La fonction supprime la valeur suivante de la priorité la plus élevée, mais ne la renvoie pas, car pop () est une fonction vide. Utilisez le Haut() fonction afin de connaître la valeur de priorité la plus élevée qui doit être supprimée ensuite. Les Haut() La fonction renvoie une copie de la valeur de priorité la plus élevée dans la file d'attente prioritaire. Le code suivant, où la valeur suivante de la priorité la plus élevée est la valeur la moins élevée, illustre ce
pq.pousser('à');pq.pousser('c');pq.pousser('b');pq.pousser('Et');pq.pousser('ré');
carboniserch1=pq.Haut();pq.pop();
carboniserch2=pq.Haut();pq.pop();
carboniserch3=pq.Haut();pq.pop();
carboniserch4=pq.Haut();pq.pop();
carboniserch5=pq.Haut();pq.pop();
cout<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<' ';
La sortie est 'a' 'b' 'c' 'd' 'e'.
La fonction vide()
Si un programmeur utilise le Haut() fonction sur une file d'attente_priorité vide, après la compilation réussie, il recevrait un message d'erreur tel que :
Donc, vérifiez toujours si la file d'attente prioritaire n'est pas vide avant d'utiliser le Haut() fonction. Les vide() La fonction membre renvoie un bool, true si la file d'attente est vide et false si la file d'attente n'est pas vide. Le code suivant illustre cela :
File d'attente de priorité<entier>pq;entieri1= dix; entieri2= 30; entieri3= vingt; entieri4= cinquante; entieri5= 40;
pq.pousser(i1);pq.pousser(i2);pq.pousser(i3);pq.pousser(i4);pq.pousser(i5);
tandis que(!pq.vide())
{
cout <<pq.Haut() << '';
pq.pop();
}
cout << ' ';
Autres fonctions de file d'attente prioritaire
La fonction size()
Cette fonction renvoie la longueur de la file d'attente prioritaire, comme l'illustre le code suivant :
entieri1= dix; entieri2= 30; entieri3= vingt; entieri4= cinquante; entieri5= 40;
pq.pousser(i1);pq.pousser(i2);pq.pousser(i3);pq.pousser(i4);pq.pousser(i5);
entierlongueur=pq.Taille();
cout <<longueur<< ' ';
La sortie est 5.
La fonction swap()
Si deux priority_queues sont du même type et de la même taille, elles peuvent être échangées par cette fonction, comme le montre le code suivant :
entieri1= dix; entieri2= 30; entieri3= vingt; entieri4= cinquante; entieri5= 40;
pq1.pousser(i1);pq1.pousser(i2);pq1.pousser(i3);pq1.pousser(i4);pq1.pousser(i5);
File d'attente de priorité<entier>pqA;
entieril1= 1; entierit2= 3; entierça3= 2; entierit4= 5; entierit5= 4;
pqA.pousser(il1);pqA.pousser(it2);pqA.pousser(ça3);pqA.pousser(it4);pqA.pousser(it5);
pq1.échanger(pqA);
tandis que(!pq1.vide())
{
cout <<pq1.Haut() << '';
pq1.pop();
} cout<<' ';
tandis que(!pqA.vide())
{
cout <<pqA.Haut() << '';
pqA.pop();
} cout<<' ';
La sortie est :
5 4 3 2 1
50 40 30 20 10
La fonction emplace()
Les remplacer() fonction est similaire à la fonction push. Le code suivant illustre cela :
entieri1= dix; entieri2= 30; entieri3= vingt; entieri4= cinquante; entieri5= 40;
pq1.mettre en place(i1);pq1.mettre en place(i2);pq1.mettre en place(i3);pq1.mettre en place(i4);pq1.mettre en place(i5);
tandis que(!pq1.vide())
{
cout <<pq1.Haut() << '';
pq1.pop();
} cout<<' ';
La sortie est :
50 40 30 20 10
Données de chaîne
Lors de la comparaison de chaînes, la classe de chaînes doit être utilisée et non l'utilisation directe des littéraux de chaîne, car elle comparerait les pointeurs et non les chaînes réelles. Le code suivant montre comment la classe de chaîne est utilisée :
#comprendreFile d'attente de priorité<chaîne de caractères>pq1;
chaîne s1=chaîne de caractères('stylo'), s2=chaîne de caractères('crayon'), s3=chaîne de caractères('livre d'exercices'), s4=chaîne de caractères('cahier de texte'), s5=chaîne de caractères('règle');
pq1.pousser(s1);pq1.pousser(s2);pq1.pousser(s3);pq1.pousser(s4);pq1.pousser(s5);
tandis que(!pq1.vide())
{
cout <<pq1.Haut() << '';
pq1.pop();
} cout<<' ';
La sortie est :
manuel règle crayon stylo livre d'exercices
Autres constructions de file d'attente prioritaires
Création explicite à partir d'un vecteur
Une file d'attente prioritaire peut être créée explicitement à partir d'un vecteur comme le montre le code suivant :
vecteur<entier>magnétoscope= {dix,30,vingt,cinquante,40};
File d'attente de priorité<entier>pq(vtr.commencer(), vtr.finir());
tandis que(!pq.vide())
{
cout <<pq.Haut() << '';
pq.pop();
} cout<<' ';
La sortie est : 50 40 30 20 10. Cette fois, l'en-tête du vecteur doit également être inclus. Les arguments de la fonction constructeur prennent les pointeurs de début et de fin du vecteur. Le type de données du vecteur et le type de données de la priorité_queue doivent être identiques.
Afin de faire de la moindre valeur la priorité, la déclaration pour le constructeur serait :
File d'attente de priorité<entier, vecteur<entier>, plus grand>entier> >pq(vtr.commencer(), vtr.finir()); Création explicite à partir d'un tableau
Une file d'attente prioritaire peut être créée explicitement à partir d'un tableau comme le montre le code suivant :
File d'attente de priorité<entier>pq(arr, arr+5);
tandis que(!pq.vide())
{
cout <<pq.Haut() << '';
pq.pop();
} cout<<' ';
La sortie est : 50 40 30 20 10. Les arguments de la fonction constructeur prennent les pointeurs de début et de fin du tableau. arr renvoie le pointeur de début, arr+5 renvoie le pointeur juste après le tableau et 5 est la taille du tableau. Le type de données du tableau et le type de données de la priorité_queue doivent être identiques.
Afin de faire de la moindre valeur la priorité, la déclaration pour le constructeur serait :
File d'attente de priorité<entier, vecteur<entier>, plus grand<entier> >pq(arr, arr+5);Remarque : en C++, la priorité_queue est en fait appelée un adaptateur, pas seulement un conteneur.
Code de comparaison personnalisé
Le fait que toutes les valeurs de la file d'attente prioritaire soient ascendantes ou descendantes n'est pas la seule option pour la file d'attente prioritaire. Par exemple, une liste de 11 entiers pour un tas maximum est :
88, 86, 87, 84, 82, 79,74, 80, 81,, 64, 69
La valeur la plus élevée est 88. Elle est suivie de deux nombres : 86 et 87, qui sont inférieurs à 88. Le reste des nombres est inférieur à ces trois nombres, mais pas vraiment dans l'ordre. Il y a deux cellules vides dans la liste. Les nombres 84 et 82 sont inférieurs à 86. Les nombres 79 et 74 sont inférieurs à 87. Les nombres 80 et 81 sont inférieurs à 84. Les nombres 64 et 69 sont inférieurs à 79.
Le placement des nombres suit les critères max-heap - voir plus loin. Afin de fournir un tel schéma pour la priorité_queue, le programmeur doit fournir son propre code de comparaison – voir plus loin.
Conclusion
Une file d'attente prioritaire C++ est une file d'attente premier entré, premier sorti. La fonction membre, pousser(), ajoute une nouvelle valeur dans la file d'attente. La fonction membre, Haut(), lit la valeur supérieure dans la file d'attente. La fonction membre, pop (), supprime sans renvoyer la valeur supérieure de la file d'attente. La fonction membre, vide(), vérifie si la file d'attente est vide. Cependant, la priorité_queue diffère de la file d'attente, en ce sens qu'elle suit un algorithme de priorité. Il peut être le plus grand, du premier au dernier, ou le moins, du premier au dernier. Les critères (algorithme) peuvent également être définis par le programmeur.