Implémentation d'une file d'attente prioritaire

Introduction

Dans ce laboratoire, nous allons apprendre les fonctionnalités de base de la File d'attente prioritaire en langage de programmation C++. La File d'attente prioritaire est un conteneur de la bibliothèque standard de plantilles (STL en anglais) de C++ qui vous permet d'insérer et de supprimer des éléments selon leur priorité. L'élément ayant la plus haute priorité est toujours placé au début de la file. Lorsqu'un élément est supprimé de la file, la file d'attente prioritaire s'occupe automatiquement d'insérer le prochain élément ayant la plus haute priorité à sa position correcte.

Inclure les bibliothèques requises

Nous allons créer un nouveau fichier nommé main.cpp dans le répertoire ~/project en utilisant la commande suivante :

touch ~/project/main.cpp

Nous devons tout d'abord inclure les bibliothèques requises pour que notre programme fonctionne correctement. Dans ce programme, nous utiliserons les bibliothèques iostream et bits/stdc++.h.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

Définir la fonction show

La fonction show est utilisée pour afficher tous les éléments présents dans la file d'attente prioritaire. La fonction prend un objet de file d'attente prioritaire en argument et copie la file dans une autre pour conserver la file d'attente prioritaire d'origine. Ensuite, elle imprime tous les éléments présents dans la file d'attente prioritaire en itérant sur elle.

void show(priority_queue<int> q)
{
    priority_queue<int> pq = q;
    while (!pq.empty())
    {
        cout << "\t" << pq.top(); //impression de l'élément le plus haut
        pq.pop();                 //suppression de l'élément le plus haut pour passer au suivant
    }
    cout << endl;
}

Implémenter la fonction principale

La fonction main est là où tout l'action a lieu. Nous déclarons tout d'abord une variable entière i. Ensuite, nous créons une file d'attente prioritaire d'entiers nommée q. Ensuite, nous ajoutons quelques entiers à la file d'attente prioritaire en utilisant la fonction push.

Après cela, nous affichons les éléments présents dans la file d'attente prioritaire en utilisant la fonction show. Ensuite, nous utilisons la fonction size pour afficher le nombre d'éléments présents dans la file, et nous utilisons la fonction top pour afficher l'élément ayant la plus haute priorité.

Ensuite, nous utilisons la fonction pop pour supprimer l'élément ayant la plus haute priorité et affichons la file d'attente prioritaire mise à jour en utilisant la fonction show.

int main()
{
    priority_queue<int> q;

    for (int i = 1; i < 6; i++)
    {
        q.push(i * 10);
    }

    cout << "La file d'attente prioritaire est : ";
    show(q);

    cout << "\n\nLe nombre d'éléments dans la file d'attente prioritaire est : " << q.size();

    cout << "\n\nL'élément ayant la plus haute priorité est : " << q.top();

    q.pop();
    cout << "\n\nAprès avoir supprimé l'élément le plus haut, la file d'attente prioritaire devient : ";
    show(q);

    return 0;
}

Code final

Vous pouvez utiliser le code suivant pour implémenter une file d'attente prioritaire en C++ :

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void show(priority_queue<int> q)
{
    priority_queue<int> pq = q;
    while (!pq.empty())
    {
        cout << "\t" << pq.top();
        pq.pop();
    }
    cout << endl;
}

int main()
{
    priority_queue<int> q;

    for (int i = 1; i < 6; i++)
    {
        q.push(i * 10);
    }

    cout << "La file d'attente prioritaire est : ";
    show(q);

    cout << "\n\nLe nombre d'éléments dans la file d'attente prioritaire est : " << q.size();

    cout << "\n\nL'élément ayant la plus haute priorité est : " << q.top();

    q.pop();
    cout << "\n\nAprès avoir supprimé l'élément le plus haut, la file d'attente prioritaire devient : ";
    show(q);

    return 0;
}

Enregistrez le code ci-dessus dans ~/project/main.cpp. Pour compiler et exécuter ce code, utilisez les commandes suivantes :

g++ main.cpp -o main &&./main

Résumé

Dans ce laboratoire, nous avons appris les concepts de base de la file d'attente prioritaire en C++. Nous avons également vu comment déclarer et initialiser une file d'attente prioritaire et comment y ajouter, supprimer et afficher des éléments. Nous espérons que ce tutoriel vous a été utile.