Explication détaillée de l'utilisation de la file d'attente prioritaire C++

Explication détaillée de l'utilisation de la file d'attente prioritaire C++

La file d'attente prioritaire est également un type de structure de données telle qu'une file d'attente. Son fonctionnement ne se limite pas au premier entré, premier sorti de la file d'attente, mais peut également se faire de manière logique (sortie de la file d'attente selon la valeur maximale ou la valeur minimale, etc.).

Apprentissage recommandé : Tutoriel vidéo C++

Une file d'attente normale est une structure de données premier entré, premier sorti. Les éléments sont ajoutés à la fin de la file d'attente et supprimés. de la tête de la file d'attente.

Dans une file d'attente prioritaire, les éléments sont prioritaires. Lors de l'accès aux éléments, l'élément ayant la priorité la plus élevée est supprimé en premier. La file d'attente prioritaire présente les caractéristiques comportementales du premier entré, le plus grand sorti.

Tout d'abord, vous devez inclure le fichier d'en-tête #include. La différence entre celui-ci et la file d'attente est que nous pouvons personnaliser la priorité des données, de sorte que les données avec. la priorité élevée sera mise en file d'attente au début. Obtenez la priorité hors de la file d'attente.

La file d'attente prioritaire possède toutes les fonctionnalités de la file d'attente, y compris les opérations de base de la file d'attente. Elle ajoute simplement un tri interne sur cette base. Elle est essentiellement implémentée sous forme de tas.

Le fonctionnement de base est le même que celui de la file d'attente :

top accède à l'élément de tête de la file d'attente

vide si la file d'attente est vide

size renvoie le nombre d'éléments dans la file d'attente

push Insérer l'élément à la fin de la file d'attente (et trier)

emplace Construire un élément sur place et l'insérer dans la file d'attente

emplace Construire un élément sur place et l'insérer dans la file d'attente

🎜>

pop Pop l'élément en tête de file d'attente

swap Exchange Contentpriority_queue<type container functional></type>

Définition :

Type est le type de données, Container est le type de conteneur (Container doit être un conteneur implémenté avec un tableau, tel que vector, deque, etc., mais il ne peut pas être utilisé comme liste. La valeur par défaut dans STL est vector), et Functional est la méthode de comparaison.

Lorsque vous devez utiliser un type de données personnalisé, vous devez transmettre ces trois paramètres. Lorsque vous utilisez un type de données de base, il vous suffit de transmettre le type de données. La valeur par défaut est un gros tas.

est généralement :

//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

1 Exemple de file d'attente prioritaire de type de base :

#include<iostream>
#include <queue>
using namespace std;
int main() 
{
    //对于基础类型 默认是大顶堆
    priority_queue<int> a; 
    //等同于 priority_queue<int, vector<int>, less<int> > a;
    
    //      这里一定要有空格，不然成了右移运算符↓↓
    priority_queue<int, vector<int>, greater<int> > c;  //这样就是小顶堆
    priority_queue<string> b;

    for (int i = 0; i < 5; i++) 
    {
        a.push(i);
        c.push(i);
    }
    while (!a.empty()) 
    {
        cout << a.top() << &#39; &#39;;
        a.pop();
    } 
    cout << endl;

    while (!c.empty()) 
    {
        cout << c.top() << &#39; &#39;;
        c.pop();
    }
    cout << endl;

    b.push("abc");
    b.push("abcd");
    b.push("cbd");
    while (!b.empty()) 
    {
        cout << b.top() << &#39; &#39;;
        b.pop();
    } 
    cout << endl;
    return 0;
}

Résultat d'exécution :

4 3 2 1 0
0 1 2 3 4
cbd abcd abc
请按任意键继续. . .

2. Exemple d'utilisation d'une paire comme élément de file d'attente prioritaire :

Règle : Pour une comparaison de paires, comparez d'abord le premier élément, et comparez le deuxième élément si le premier est égal.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() 
{
    priority_queue<pair<int, int> > a;
    pair<int, int> b(1, 2);
    pair<int, int> c(1, 3);
    pair<int, int> d(2, 5);
    a.push(d);
    a.push(c);
    a.push(b);
    while (!a.empty()) 
    {
        cout << a.top().first << &#39; &#39; << a.top().second << &#39;\n&#39;;
        a.pop();
    }
}

Résultat d'exécution :

2 5
1 3
1 2
请按任意键继续. . .

3. Exemple d'utilisation d'un type personnalisé comme élément de file d'attente prioritaire

#include <iostream>
#include <queue>
using namespace std;

//方法1
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};

//方法2
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};

int main() 
{
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue<tmp1> d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty()) 
    {
        cout << d.top().x << &#39;\n&#39;;
        d.pop();
    }
    cout << endl;

    priority_queue<tmp1, vector<tmp1>, tmp2> f;
    f.push(b);
    f.push(c);
    f.push(a);
    while (!f.empty()) 
    {
        cout << f.top().x << &#39;\n&#39;;
        f.pop();
    }
}

Résultat d'exécution :

3
2
1
 
3
2
1
请按任意键继续. . .

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!