Implementierung einer Prioritätswarteschlange

Einführung

In diesem Lab werden wir uns mit der grundlegenden Funktionalität der Prioritätswarteschlange in der Programmiersprache C++ befassen. Die Prioritätswarteschlange ist ein Container in der C++ STL (Standard Template Library), der es Ihnen ermöglicht, Elemente nach ihrer Priorität einzufügen und zu entfernen. Das Element mit der höchsten Priorität befindet sich immer am Anfang der Warteschlange. Wenn ein Element aus der Warteschlange entfernt wird, kümmert sich die Prioritätswarteschlange automatisch darum, das nächsthöchstprioritäre Element an der richtigen Position einzufügen.

Skills Graph

Die erforderlichen Bibliotheken einbinden

Wir werden eine neue Datei namens main.cpp im Verzeichnis ~/project mit dem folgenden Befehl erstellen:

touch ~/project/main.cpp

Wir müssen zunächst die erforderlichen Bibliotheken einbinden, damit unser Programm richtig funktioniert. In diesem Programm werden wir die Bibliotheken iostream und bits/stdc++.h verwenden.

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

Die show-Funktion definieren

Die show-Funktion wird verwendet, um alle Elemente in der Prioritätswarteschlange anzuzeigen. Die Funktion nimmt ein Prioritätswarteschlangenobjekt als Argument entgegen und kopiert die Warteschlange in eine andere, um die ursprüngliche Prioritätswarteschlange zu erhalten. Danach druckt es alle Elemente in der Prioritätswarteschlange, indem es über sie iteriert.

void show(priority_queue<int> q)
{
    priority_queue<int> pq = q;
    while (!pq.empty())
    {
        cout << "\t" << pq.top(); //druckt das oberste Element
        pq.pop();                 //löscht das oberste Element, um zum nächsten zu gelangen
    }
    cout << endl;
}

Die Hauptfunktion implementieren

In der main-Funktion passiert alles. Wir deklarieren zunächst eine ganzzahlige Variable i. Dann erstellen wir eine Prioritätswarteschlange von ganzen Zahlen namens q. Danach fügen wir einige ganze Zahlen zur Prioritätswarteschlange hinzu, indem wir die push-Funktion verwenden.

Danach zeigen wir die Elemente in der Prioritätswarteschlange mit der show-Funktion an. Dann verwenden wir die size-Funktion, um die Anzahl der Elemente in der Warteschlange anzuzeigen, und wir verwenden die top-Funktion, um das Element mit der höchsten Priorität anzuzeigen.

Als nächstes verwenden wir die pop-Funktion, um das Element mit der höchsten Priorität zu entfernen und die aktualisierte Prioritätswarteschlange mit der show-Funktion anzuzeigen.

int main()
{
    priority_queue<int> q;

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

    cout << "The Priority Queue is: ";
    show(q);

    cout << "\n\nThe number of elements in the Priority Queue are: " << q.size();

    cout << "\n\nThe element with the highest priority is: " << q.top();

    q.pop();
    cout << "\n\nAfter Deleting the top most element, Priority Queue becomes: ";
    show(q);

    return 0;
}

Endgültiger Code

Sie können den folgenden Code verwenden, um eine Prioritätswarteschlange in C++ zu implementieren:

#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 << "The Priority Queue is: ";
    show(q);

    cout << "\n\nThe number of elements in the Priority Queue are: " << q.size();

    cout << "\n\nThe element with the highest priority is: " << q.top();

    q.pop();
    cout << "\n\nAfter Deleting the top most element, Priority Queue becomes: ";
    show(q);

    return 0;
}

Speichern Sie den obigen Code in ~/project/main.cpp. Um diesen Code zu kompilieren und auszuführen, verwenden Sie die folgenden Befehle:

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

Zusammenfassung

In diesem Lab haben wir uns mit den Grundkonzepten der Prioritätswarteschlange in C++ beschäftigt. Wir haben auch gesehen, wie man eine Prioritätswarteschlange deklariert und initialisiert und wie man Elemente hinzufügt, entfernt und anzeigt. Wir hoffen, dass Ihnen dieser Tutorial hilfreich war.