Extrahieren Sie das letzte Element der Prioritätswarteschlange, ohne es zu durchlaufen

Einführung

Die Prioritätswarteschlange in C++ unterscheidet sich von der normalen Warteschlange in der Datenstruktur. Sie hat einen Unterschied: Alle Elemente haben Priorität. Wir können seine Elemente extrahieren, indem wir über die Warteschlange iterieren.

In diesem Tutorial versuchen wir jedoch, das letzte Element der Prioritätswarteschlange zu extrahieren, ohne es zu durchlaufen. Fangen wir an...

Was ist eine Prioritätswarteschlange?

In Datenstrukturen sind abstrakte Datentypen Prioritätswarteschlangen. Es handelt sich um eine Warteschlange, in der alle Elemente eine bestimmte Priorität haben. Alle seine Elemente werden entsprechend ihrer Priorität entfernt. Daten mit höherer Priorität werden zuerst extrahiert, Daten mit niedrigerer Priorität werden zuerst extrahiert. Warteschlangendaten/-elemente können Ganzzahlen oder Zeichenfolgen sein, dürfen jedoch keine NULL-Werte sein.

Wenn zwei Elemente die gleiche Priorität haben, wird die Prioritätswarteschlange nach dem FIFO-Prinzip (First In, First Out) abgerufen.

Es gibt zwei Arten von Prioritätswarteschlangen, deren Elemente extrahiert werden können –

• Ascending Priority Queue − In dieser Art von Prioritätswarteschlange werden Elemente in aufsteigender Reihenfolge abgerufen. Elemente mit der niedrigsten Priorität werden zuerst entfernt.

• Absteigende Prioritätswarteschlange − In dieser Art von Prioritätswarteschlange werden Elemente in aufsteigender Reihenfolge abgerufen. Elemente mit der höchsten Priorität werden zuerst entfernt.

Grammatik

 priority_queue<queue_type> queue_name

Nicht durchlaufen, um das letzte Element der Prioritätswarteschlange zu extrahieren

Hier extrahieren wir das letzte Element der Prioritätswarteschlange, ohne die gesamte Warteschlange zu durchlaufen. Wir implementieren Prioritätswarteschlangen durch Binärbäume. Verwenden Sie während dieses Vorgangs die folgenden integrierten Methoden -

• size() – Gibt die Größe der Prioritätswarteschlange zurück.

  Syntax− Warteschlangenname .size()

• insert() – Fügt ein Element in die Prioritätswarteschlange ein.

  Syntax−queue_name.insert(data_type)

• getMin() – Gibt das minimale Element der Prioritätswarteschlange zurück.

  Syntax−queue_name.getMin()

• getMax() − Es gibt das größte Element in der Prioritätswarteschlange zurück.

  Die chinesische Übersetzung von

  Syntax − queue_name.getMax()

lautet:

Syntax − queue_name.getMax()

• isEmpty() − Gibt true zurück, wenn die Warteschlange leer ist.

• deleteMin() − Das kleinste Warteschlangenelement löschen.

  Syntax−queue_name.deleteMin()

• deleteMax() – das größte Warteschlangenelement löschen

  Syntax−queue_name.deleteMax()

Algorithmus

Schritt 1− Erstellen Sie eine Strukturklasse für Warteschlangenoperationen.

Schritt 2− Erstellen Sie ein Multiset, um Elemente automatisch zu sortieren.

Schritt 3− Fügen Sie das Element in die Prioritätswarteschlange ein.

Schritt 4− Ermitteln Sie die minimalen und maximalen Elemente ohne Traversierung (), indem Sie integrierte Funktionen wie getMin() und getMax verwenden.

Beispiel

C++-Code zum Extrahieren des letzten Elements aus der Warteschlange

#include <bits/stdc++.h>
using namespace std;
  
// declaring a struct class for the Priority Queue
struct PQ  {
   multiset<int> s;
   
   //Getting the size of the Queue
   int size() { 
      return s.size(); 
   }
   
   //Checking Queue is empty or not
   bool isEmpty() { 
      return (s.size() == 0); 
   }
   
   void insert(int i) { 
      s.insert(i); 
   }
  
   //Method to get the smallest element of the Queue
   int getMin() { 
      return *(s.begin()); 
   }
   
   // Method to get the largest Queue element
   int getMax() { 
      return *(s.rbegin()); 
   }
   
   // Deleting Queue elements
   void deleteMin() {
      if (s.size() == 0)
         return;
      
      auto i = s.begin();
      s.erase(i);
   }
      
   // Method to delete the largest element
   void deleteMax() {
      if (s.size() == 0)
      return;
      
      auto i = s.end();
      i--;
      s.erase(i);
   }
};
  
//Main code
int main() {
   PQ p;   //initializing the Priority Queue
   
//inserting Queue elements
   p.insert(20);      
   p.insert(30);
   p.insert(50);
   p.insert(60);
   p.insert(90);
   
   cout << "Smallest Element is: " << p.getMin() << endl;
   cout << "Largest Element is: " << p.getMax() << endl;
   
   p.deleteMin();
   cout << "Smallest Element is: " << p.getMin() << endl;
   
   p.deleteMax();
   cout << "Largest Element is: " << p.getMax() << endl;
   
   cout << "Size of the Queue is: " << p.size() << endl;
   
   cout << "Queue is empty?: "
   << (p.isEmpty() ? "YES" : "NO") << endl;
   
   return 0;
}

Ausgabe

Smallest Element is: 20
Largest Element is: 90
Smallest Element is: 30
Largest Element is: 50
Queue is Empty?: NO

Fazit

Prioritätswarteschlangen können über Arrays, Heap-Datenstrukturen, verknüpfte Listen und Binärbäume implementiert werden. Es hilft dabei, versteckte Pfade und verschiedene Algorithmen aufzudecken.

Das ist das Ende dieses Tutorials. Ich hoffe, Sie fanden es sinnvoll.

Das obige ist der detaillierte Inhalt vonExtrahieren Sie das letzte Element der Prioritätswarteschlange, ohne es zu durchlaufen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!