So implementieren Sie eine Prioritätswarteschlange in C ++



Dieser Artikel bietet Ihnen ein detailliertes und umfassendes Wissen zum Implementieren einer Prioritätswarteschlange in C ++ mit Beispielen.

Eine Prioritätswarteschlange ist ein Container in der STL. Es ähnelt der Warteschlange mit der Ausnahme, dass jedes Element der Prioritätswarteschlange eine bestimmte Priorität hat. Wenn wir Elemente aus der Prioritätswarteschlange entfernen, werden die Elemente mit der höchsten Priorität zuerst angezeigt. Wie in der Prioritätswarteschlange gibt es 10 verschiedene Arten von Containern STL . Ein Container ist ein Objekt, das Daten speichert. Die STL-Container werden mithilfe von Vorlagenklassen implementiert, sodass die Anpassung an verschiedene Datentypen einfach ist. In diesem Beitrag werden die Prioritätswarteschlange und die damit verbundenen Konzepte ausführlich erläutert. Die folgenden Hinweise werden in diesem Priority Queue in C ++ - Artikel behandelt:

Fahren Sie mit diesem Artikel über die Prioritätswarteschlange in C ++ fort





Komponenten von STL

STL besteht aus Vorlagenklassen und -funktionen, die als Standardansatz zum Speichern und Verarbeiten von Daten verwendet werden können. Lassen Sie uns die Komponenten der STL diskutieren

Behälter- In STL sind 10 Arten von Containern definiert, die in drei Kategorien unterteilt sind. Von diesen 3 gehören Prioritätswarteschlangen zur Kategorie des abgeleiteten Containers. Jede Containerklasse verfügt über eigene Funktionen, mit denen die Daten bearbeitet werden können.



Algorithmus - Ein Algorithmus ist eine Methode zur Verarbeitung der im Containerobjekt vorhandenen Daten. STL bietet viele verschiedene Arten von Algorithmen, die zum Initialisieren, Suchen, Sortieren, Zusammenführen und Kopieren verwendet werden können. Algorithmen werden mit Hilfe von Vorlagenfunktionen implementiert.

Iterator- Ein Iterator ist ein Objekt, das auf ein Element im Container zeigt. Iteratoren können beim Durchlaufen des Inhalts eines Containers hilfreich sein. Iteratoren sind wie Zeiger, die inkrementiert und dekrementiert werden können. Es fungiert als Verbindung zwischen dem Algorithmus und dem Container. Iteratoren werden zum Bearbeiten der in einem Container gespeicherten Daten verwendet.

Fahren Sie mit diesem Artikel über die Prioritätswarteschlange in C ++ fort



Heaps und Priority Queue

Wie wir bereits gesehen haben, gehört die Prioritätswarteschlange zur Kategorie der abgeleiteten Container. Andere Mitglieder dieser Kategorie sind Stapel und Warteschlange. Diese abgeleiteten Container werden auch als Containeradapter bezeichnet.

Stapel-, Warteschlangen- und Prioritätswarteschlange werden als abgeleitete Container bezeichnet, da sie aus verschiedenen Sequenzcontainern bestehen. Diese Container unterstützen keine Art von Iteratoren, die nicht für die Datenmanipulation verwendet werden.

Was genau ist eine Prioritätswarteschlange?

In einfachen Worten, es ist ein Container, in dem wir Daten gespeichert haben. Jedem Element der gespeicherten Daten wird eine Priorität zugewiesen, die uns beim Speichern von Daten in einer logischen Reihenfolge helfen kann.
Syntax:Priority_queue Variablenname

Es ist wichtig, eine Header-Datei in das Programm aufzunehmen, um eine Prioritätswarteschlange zu verwenden.

Prioritätswarteschlange in c ++Wenn wir beispielsweise 2, 10, 30, 5, 6 mit der Push-Funktion in unsere Prioritätswarteschlange einfügen und dann die Elemente mit der Pop-Funktion platzieren, lautet die Ausgabe 30, 10, 6, 5, 2.

Okay, jetzt kennen wir den Zweck oder die Verwendung der Prioritätswarteschlange. Aber woher wusste es, ob 30> 10? Macht es eine Art Sortierung? An diesem Punkt kommen Haufen ins Bild. Weitere Informationen zu Heaps finden Sie in diesem Artikel.

Haufen - Haufen sind baumartige Strukturen. Basierend darauf, wie die untergeordneten Elementknoten in Bezug auf die übergeordneten Knoten in einem Heap angeordnet sind, werden Heaps in zwei Teile unterteilt

datengetriebenes Framework in Selen

ein. Min Heap- In Min Heap ist der Wert des übergeordneten Knotens kleiner oder gleich dem Wert der untergeordneten Knoten.

2. Max Heap- In Max Heap ist der Wert des übergeordneten Knotens größer oder gleich dem Wert der untergeordneten Knoten.

Hinweis- Die Prioritätswarteschlange sortiert die Elemente nicht mithilfe eines Sortieralgorithmus, sondern speichert die Daten in Form eines Heaps.

Fahren Sie mit diesem Artikel über die Prioritätswarteschlange in C ++ fort

Drucken aller Elemente einer Prioritätswarteschlange

Nachdem Sie die Grundlagen der Prioritätswarteschlange verstanden haben, implementieren wir Programme, um die am häufigsten verwendeten Methoden mit einer Prioritätswarteschlange zu verstehen

#include #include using Namespace std int main () {priority_queue Prior_q Prior_q.push (10) Prior_q.push (30) Prior_q.push (6) Prior_q.push (2) Prior_q.push (15) Prior_q.push (9) Prior_q.push (7) while (Prior_q.empty () == false) {cout<< Prior_q.top() << ' ' Prior_q.pop() } return 0 }

Ausgabe:

30 15 10 9 6 2

Fibonacci-Funktion c ++

Im obigen Programm haben wir die Funktionen pop (), top () und push () verwendet, die meistens beim Umgang mit einer Prioritätswarteschlange verwendet werden. Schauen wir uns einige der Methoden an, die wir mit einer Prioritätswarteschlange verwenden können

Größe( ): Diese Funktion gibt die Größe der Prioritätswarteschlange zurück

leer (): Mit dieser Funktion wird überprüft, ob die Prioritätswarteschlange leer ist oder nicht. Es wird true zurückgegeben, wenn die Prioritätswarteschlange leer ist.

drücken( ): Fügt ein Element in die Prioritätswarteschlange ein.

pop (): Diese Funktion entfernt das oberste Element der Prioritätswarteschlange, das das Element mit der höchsten Priorität ist.

Tauschen( ): Diese Funktion tauscht die Elemente der Prioritätswarteschlange gegen eine andere Prioritätswarteschlange aus. Die Funktion verwendet eine Prioritätswarteschlange als Parameter.

emplace (): Diese Funktion wird verwendet, um ein Element am Anfang der Prioritätswarteschlange hinzuzufügen.

Schauen wir uns noch ein Programm an.

#include #include using Namespace std int main () {priority_queue Prior_q Prior_q.push (10) Prior_q.push (30) Prior_q.push (6) Prior_q.push (2) Prior_q.push (15) Prior_q.push (9) Prior_q.push (7) while (Prior_q.empty () == false) {cout<< Prior_q.top() << ' ' Prior_q.pop() } return 0 }

Ausgabe:

2 6 7 9 10 15 30

Damit ist das Ende dieser Prioritätswarteschlange in C ++ erreicht. Wenn Sie mehr erfahren möchten, lesen Sie die von Edureka, einem vertrauenswürdigen Online-Lernunternehmen. Der Java J2EE- und SOA-Schulungs- und Zertifizierungskurs von Edureka wurde entwickelt, um Sie für Kern- und fortgeschrittene Java-Konzepte sowie für verschiedene Java-Frameworks wie Hibernate & Spring zu schulen.

Hast du eine Frage an uns? Bitte erwähne es im Kommentarbereich dieses Blogs und wir werden uns so schnell wie möglich bei dir melden.