Fonctions de file d'attente prioritaire C ++

«La file d'attente est une structure de données FIFO (premier dans, première sortie), indiquant que l'insertion est placée à la fin et que le retrait est effectué de l'avant. Une variété spécifique de files d'attente est une file d'attente prioritaire. Contrairement à la file d'attente, la file d'attente prioritaire n'adhère pas au principe FIFO.

Les files d'attente prioritaires sont une forme d'adaptateur de conteneurs spécialement développé afin que, selon certaines conditions de tri faibles rigoureuses, sa composante initiale est toujours la plus grande des éléments qu'il détient. Ce cadre ressemble à un tas dans la mesure où les composants peuvent être ajoutés à tout moment, et seul le nombre maximum de composants de tas peut être récupéré (le premier élément de la liste des priorités).

Les files d'attente prioritaires sont construites comme onduleurs de conteneurs, qui sont des classes qui utilisent une instance ci-jointe d'une catégorie de conteneurs particulière comme conteneur réel et offrent un ensemble particulier de variables et de fonctions pour récupérer leurs composants. La valeur la plus élevée de la file d'attente prioritaire, ou le «dos» du conteneur, est d'où les composants sont poussés à partir de."

Qu'est-ce qu'une file d'attente prioritaire en C++?

Le premier composant d'une file d'attente prioritaire est le plus grand de tous les composants de la file d'attente, et les composants sont en ordre décroissant. Une file d'attente prioritaire est une forme d'adaptateur de conteneur en C ++ qui ne gère que le composant prioritaire le plus élevé.

Comparez une file d'attente avec une file d'attente prioritaire

Il n'y a aucune priorité dans une file d'attente; En revanche, un conteneur de file d'attente considère l'élément comme ayant la priorité absolue. La règle du premier entrée en dépasse (FIFO) s'applique à la file d'attente; Cependant, dans la file d'attente de priorité, le composant avec la plus haute priorité serait supprimé en premier. Si plusieurs articles ont une priorité similaire, l'ordre de la file d'attente serait utilisé dans cette situation.

Syntaxe de la file d'attente prioritaire

La file d'attente prioritaire en C ++ a la syntaxe suivante:

Les paramètres sont décrits comme suit:

• Type: le type de contenu ou de composants qui sont conservés dans la file d'attente prioritaire.
• Conteneur: Étant donné que la file d'attente prioritaire est un adaptateur de conteneur, son exécution nécessite un conteneur réel sous-jacent. Le conteneur à utiliser pour créer la file d'attente prioritaire est spécifié par cette option. Le vecteur sert de conteneur standard par défaut.
• Comparez: ce paramètre est facultatif. Les composants de la file d'attente prioritaire sont organisés dans la file d'attente prioritaire en fonction de la commande interne d'un objet. Il conserve les positions relatives des articles lors de leur comparaison. La valeur possible de l'objet fonction est la moins, ce qui donne le même résultat que l'opérateur moins que.

La file d'attente prioritaire est construite avec un maximum-heap par défaut en c++.

Syntaxe de la file d'attente prioritaire

La création de la syntaxe Min-Heap de la file d'attente prioritaire est la suivante:

Ici plus grand est une classe de comparaison, et le vecteur est un conteneur de bibliothèque de modèle standard.

Avantages de l'utilisation de la file d'attente prioritaire

Les sommets se voient attribuer du poids, ce qui leur permet de monter la file d'attente au lieu de tomber à l'arrière car ils sont dans une file d'attente standard.

Inconvénients de l'utilisation de la file d'attente prioritaire

Parce que nous devons également utiliser une opération d'addition pour ajouter les éléments en fonction de leur priorité, l'insertion ne prend plus de temps fixe, comme la file d'attente. L'implémentation à l'aide d'une liste liée permet de maintenir un temps d'insertion cohérent.

Méthodologies de file d'attente prioritaire

Les fonctions de file d'attente prioritaire C ++ sont les suivantes:

• Fonction vide (): cette méthode est utilisée pour déterminer si le conteneur maintenant la file d'attente prioritaire est vide ou non. Retour True s'il est vide; Faux autrement. Il ne nécessite aucun argument.
• Méthode size (): cette fonction renvoie le nombre d'articles de la file d'attente prioritaire. La taille est rendue en tant qu'entier. Il ne nécessite aucun argument.
• Fonction push (): L'élément est ajouté à la file d'attente en appliquant cette approche. L'article est d'abord ajouté à la fin de la file d'attente, et en même temps, les composants se réalisent en fonction de la priorité. Comme dans l'argument, il accepte les entiers.
• Fonction pop (): cette technique supprime le plus grand composant de la file d'attente prioritaire. Il ne nécessite aucun argument.
• Fonction top (): le composant supérieur de la file d'attente prioritaire est renvoyé par cette fonction. Il ne nécessite aucun argument.
• Fonction swap (): en utilisant cette fonction, une file d'attente prioritaire d'une taille et d'un type similaire est échangée contre ses composants avec une autre file d'attente prioritaire. Il accepte un attribut dont les chiffres doivent être commutés et la file d'attente prioritaire.
• Fonction EMPlace (): avec cette approche, un élément de données est ajouté à un conteneur en haut de la file d'attente. Il accepte une valeur d'attribut.

Exécutons les fonctions susmentionnées dans différents codes.

Exemple n ° 1

Nous ajouterons un élément à une file d'attente prioritaire dans cet exemple. Pour ajouter un élément à la file d'attente prioritaire, nous utiliserons la fonction push ().

Les fichiers d'en-tête requis et seront intégrés au début du programme. Ensuite, l'espace de noms standard sera ajouté en tant que MST. Maintenant, la fonction principale () serait appelée. La file d'attente des valeurs entières sera créée ensuite. Cette file d'attente sera une file d'attente prioritaire. Différentes valeurs seront ajoutées à cette file d'attente prioritaire. Les nombres seront insérés par l'utilisation de la fonction push (). Trois valeurs aléatoires seront ajoutées en utilisant la méthode push. La déclaration «cout» sera utilisée pour représenter le texte «Éléments de la file d'attente de priorité» sur la console.

Après avoir affiché cette ligne pour imprimer les valeurs de la boucle «while» de file d'attente sera utilisée; À l'intérieur de la boucle «while», la fonction vide () sera appliquée pour vérifier si la file d'attente est vide ou non. La méthode pop () sera utilisée pour commencer à imprimer les valeurs de la file d'attente dans l'ordre descendant. Alors la méthode pop () est également appliquée aux valeurs de la file d'attente. Le «retour 0» doit être incorporé à la fin.

Nous avons construit une file d'attente prioritaire ayant des entiers nommés num. La fonction push () a été utilisée pour ajouter les différentes entrées à la file d'attente: 12, 30 et 72.

Exemple n ° 2

Contrairement aux vecteurs et autres structures, nous ne pouvons pas traverser une file d'attente prioritaire. Pour cette raison, nous avons imprimé les membres de la file d'attente prioritaire en utilisant une boucle while et différentes méthodes de file d'attente de priorité.

C'est ainsi que la file d'attente prioritaire fonctionnera comme une structure de données de file d'attente prioritaire typique, c'est pourquoi il s'agit d'un adaptateur de conteneur STL avec un accès limité. En conséquence, nous imprimons son haut avant de faire en sorte que l'élément à l'intérieur d'une boucle jusqu'à ce que la file d'attente soit vide.

Exemple n ° 3

Nous avons décidé d'éliminer l'élément de la file d'attente prioritaire dans ce cas. La fonction pop () pourrait être utilisée pour supprimer un composant de la file d'attente prioritaire. La valeur maximale est éliminée dans cette approche.

Nous commencerons le code en intégrant les bibliothèques et l'espace de noms standard. Les bibliothèques contiennent et . La méthode pour afficher la file d'attente prioritaire serait alors appelée en utilisant display_priority_queue (). La file d'attente contient les numéros entiers, donc «int» sera fourni comme argument de la fonction. Après tout cela, la méthode principale () sera invoquée. La file d'attente sera créée. La fonction push () sera utilisée pour ajouter différentes valeurs dans la file d'attente de priorité définie. La déclaration «cout» est utilisée pour afficher les éléments originaux de la file d'attente prioritaire.

Alors la méthode pop () sera appliquée. Cette fonction élimine la valeur spécifiée de la file d'attente prioritaire. Maintenant, l'instruction «cout» sera utilisée pour afficher les valeurs de la file d'attente après avoir supprimé un élément de la file d'attente. La commande «return 0» - serait ajoutée. Ensuite, la méthode de l'utilitaire sera utilisée pour afficher la file d'attente de priorité définie. La boucle «while» sera employée. Dans la boucle «while» vide () et top () seront utilisés. La condition de boucle sera appliquée à la fonction vide (). La méthode pop () serait utilisée pour supprimer la valeur la plus élevée de la file d'attente prioritaire.

Ici, nous avons fait une file d'attente prioritaire entière appelée num. Les composantes initiales de la file d'attente prioritaire sont «61, 23, 45."L'attribut le plus élevé a ensuite été supprimé à l'aide de la technique POP (). Ainsi, le résultat sera «45, 23."

Exemple n ° 4

Dans ce cas, la fonction supérieure () sera utilisée pour récupérer la valeur maximale de la file d'attente prioritaire.

Les bibliothèques et l'espace de noms par défaut seront intégrés avant de commencer à écrire le code. et sont tous deux disponibles dans les bibliothèques. Nous appellerons alors la fonction principale (). La méthode de création de file d'attente prioritaire serait alors invoquée. La fonction sera donnée l'argument «int» car la file d'attente ne contient que des nombres entiers. Différentes valeurs seront ajoutées à la file d'attente prioritaire spécifiée en utilisant la fonction push ().

Pop () sera utilisé après que les éléments auront été ajoutés à la file d'attente prioritaire. Cette fonction a montré la valeur maximale de la file d'attente prioritaire fournie. Le texte «l'élément supérieur de la file d'attente prioritaire» est affiché en utilisant l'instruction COUT. L'instruction «retour 0» pourrait être appliquée pour mettre fin au programme.

Exemple n ° 5

Dans cette illustration, nous vérifions si la file d'attente prioritaire est vide ou non en utilisant la fonction vide (). Cette méthodologie produit:

• Lorsque la file d'attente prioritaire ne contient aucun élément, la valeur 1 (true)
• Lorsque la file d'attente prioritaire contient l'élément 0 (false).

Au début du programme, les fichiers d'en-tête requis et seraient inclus. Ensuite, la MST sera ajoutée à l'espace de noms standard. Maintenant, la méthode principale () serait invoquée. Il y aurait une file d'attente créée en utilisant la fonction. Cette méthode prendra le paramètre «String» car il contient des valeurs avec le type de données «String» dans cette file d'attente. Cela aura une priorité. «La file d'attente contient une valeur?«Serait imprimé en utilisant la commande« cout ».

La condition «if-else» serait utilisée pour déterminer la réponse. La fonction vide () sera appliquée à l'intérieur de l'instruction «IF» pour vérifier si la file d'attente a des valeurs ou non. Si la file d'attente contient une valeur, l'instruction «cout» imprime «oui», une autre instruction «cout» imprime «non» comme sortie. En conséquence, la ligne intitulée «Pousser les valeurs de la file d'attente prioritaire» s'affiche à l'écran par l'instruction «cout». La file d'attente prioritaire sera mise à jour pour inclure les noms de divers pays. La méthode push () serait utilisée pour insérer les noms. La technique de poussée ajoutera les noms de trois pays. «La file d'attente contient une valeur?"Sera imprimé sur la console à l'aide de la commande" cout ".

La condition «if-else» sera appliquée après l'affichage de cette ligne. La méthode vide () sera utilisée à nouveau pour confirmer si la file d'attente est vide ou non. Le dernier «retour 0» doit être présent.

Pour vérifier si la file d'attente prioritaire du pays est remplie ou non, nous avons utilisé la fonction vide (). La file d'attente est vide au début. Pays.vide () renvoie donc vrai. Après cela, nous avons ajouté des éléments à la file d'attente et utilisé une fois de plus la fonction vide (). Cette fois, cela donne de faux résultats.

Conclusion

Tout d'abord, nous avons exploré ce qu'une file d'attente prioritaire en C ++ est dans cet article. Ensuite, nous contrastons la file d'attente simple avec la file d'attente prioritaire. De plus, nous avons examiné la syntaxe de la file d'attente prioritaire ainsi que ses avantages et inconvénients. De plus, nous avons discuté des différentes méthodes C ++ pour les files d'attente prioritaires. Un conteneur appelé une file d'attente de priorité est utilisé pour contenir des composants avec des priorités. Contrairement aux files d'attente, qui ajoutent ou suppriment les composants en fonction de la règle FIFO, les éléments d'une file d'attente de priorité sont supprimés en fonction de la priorité. Le composant initial supprimé de la file d'attente sera celui qui a une priorité absolue. Le but de la file d'attente prioritaire est de gérer les composants en fonction de la priorité.

Cinq instances différentes ont été mises en œuvre dans cet article. Dans le premier cas, nous avons utilisé la fonction push () pour insérer les éléments dans la file d'attente prioritaire. Le deuxième exemple utilise une boucle «while» pour montrer les valeurs de la file d'attente prioritaire. Dans le troisième scénario, nous avons utilisé la méthode POP () pour supprimer la valeur maximale de la file d'attente prioritaire. Avec l'aide de la fonction supérieure (), nous avons pu récupérer la valeur la plus élevée de la quatrième illustration. Dans le dernier, nous avons utilisé la méthode vide () pour déterminer si la file d'attente prioritaire était vide ou non.