Detaillierte Erläuterung der Verwendung der C++-Prioritätswarteschlange

Detaillierte Erläuterung der Verwendung der C++-Prioritätswarteschlange

Prioritätswarteschlange ist auch eine Art Datenstruktur wie Warteschlange. Seine Funktionsweise ist nicht auf das First-In-First-Out-Prinzip aus der Warteschlange beschränkt, sondern kann auch logisch erfolgen (Verlassen der Warteschlange entsprechend dem Maximalwert oder Minimalwert usw.).

Empfohlenes Lernen: C++-Video-Tutorial

Eine normale Warteschlange ist eine First-In-First-Out-Datenstruktur, die an das Ende der Warteschlange angehängt und gelöscht wird vom Kopf der Warteschlange.

In einer Prioritätswarteschlange erhalten Elemente Priorität. Beim Zugriff auf Elemente wird zuerst das Element mit der höchsten Priorität entfernt. Die Prioritätswarteschlange weist die Verhaltensmerkmale First In, Largest Out auf.

Zuerst müssen Sie die Header-Datei #include578d2716abf2876f231498269846f87d einbinden. Der Unterschied zwischen it und queue besteht darin, dass wir die Priorität der Daten anpassen können, sodass die Daten mit Hohe Priorität wird an die Spitze der Warteschlange gestellt. Holen Sie sich Priorität aus der Warteschlange.

Die Prioritätswarteschlange verfügt über alle Funktionen der Warteschlange, einschließlich der grundlegenden Operationen der Warteschlange. Sie fügt lediglich eine interne Sortierung auf dieser Basis hinzu. Sie ist im Wesentlichen als Heap implementiert.

Die Grundoperation ist die gleiche wie bei der Warteschlange:

top greift auf das Kopfelement der Warteschlange zu

empty, ob die Warteschlange leer ist

size gibt die Anzahl der Elemente in der Warteschlange zurück

push Element an das Ende der Warteschlange einfügen (und sortieren)

emplace Konstruiert ein Element an Ort und Stelle und fügt es in die Warteschlange ein

pop Pop das Element an der Spitze der Warteschlange

Swap Exchange Content

Definition: priority_queueab91b0b20a82ad8d07046f6e05e9fd7f

Type ist der Datentyp, Container ist der Containertyp (Container muss ein Container sein, der mit einem Array wie Vektor, Deque usw. implementiert ist, kann jedoch nicht in der Liste verwendet werden. Vektor wird standardmäßig in STL verwendet), und Functional ist die Vergleichsmethode.

Wenn Sie einen benutzerdefinierten Datentyp verwenden müssen, müssen Sie diese drei Parameter übergeben. Wenn Sie einen Basisdatentyp verwenden, müssen Sie nur den Datentyp übergeben.

ist im Allgemeinen:

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

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

1. Beispiel einer Basistyp-Prioritätswarteschlange:

#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;
}

Laufergebnis:

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

2. Beispiel für die Verwendung eines Paars als Prioritätswarteschlangenelement:

Regel: Vergleichen Sie beim Paarvergleich zuerst das erste Element und vergleichen Sie das zweite Element, wenn das erste gleich ist.

#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();
    }
}

Laufergebnis:

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

3. Beispiel für die Verwendung eines benutzerdefinierten Typs als Prioritätswarteschlangenelement

#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();
    }
}

Laufergebnis:

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

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Verwendung der C++-Prioritätswarteschlange. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!