提取優先隊列的最後一個元素而不進行遍歷

簡介

C 中的優先權佇列與資料結構中的普通佇列不同，它有一個差異：所有元素都有優先權。我們可以透過在佇列中遍歷來提取其元素。

但是，在本教學中，我們正在嘗試一種無需遍歷即可提取優先權佇列最後一個元素的方法。讓我們開始吧…

什麼是優先隊列？

在資料結構中，抽象資料型別是優先權佇列。它是一個佇列，其中所有元素都有一些關聯的優先權。它的所有元素都根據其優先順序被刪除。優先順序較高的數據首先被提取，優先順序較低的數據首先被提取。佇列資料/元素可以是整數或字串，但不能為 NULL 值。

如果兩個元素的優先權相同，則優先權佇列將依照 FIFO（先進先出）原則進行提取。

有兩種類型的優先隊列可以提取其元素 -

• 升序優先權佇列 − 在這種類型的優先權佇列中，元素會依升序擷取。優先順序最低的元素將首先被移除。

• 降序優先權佇列 − 在這種類型的優先權佇列中，元素會依升序被提取。具有最大優先權的元素將首先被移除。

文法

 priority_queue<queue_type> queue_name

不遍歷提取優先權佇列的最後一個元素

在這裡，我們提取優先權佇列的最後一個元素，而不遍歷整個佇列。我們透過二元樹來實現優先權隊列。在此過程中使用以下內建方法 -

• size() - 它會傳回優先權佇列的大小。

  語法− queue_name .size()

• insert() - 將元素插入優先權佇列。

  語法−queue_name.insert(data_type)

• getMin() -它傳回優先權佇列的最小元素。

  語法−queue_name.getMin()

• getMax() −它會傳回優先權佇列中最大的元素。

  Syntax − queue_name.getMax()

# 的中文翻譯為：

Syntax − queue_name.getMax()

• isEmpty() −如果佇列為空，則傳回true。

• deleteMin() −刪除最小的佇列元素。

  語法−queue_name.deleteMin()

• deleteMax() - 刪除最大的佇列元素

  語法−queue_name.deleteMax()

演算法

第 1 步 − 為佇列操作建立一個結構類別。

第 2 步驟 − 建立一個多重集合以對元素進行自動排序。

第 3 步 − 將元素插入優先權佇列。

第 4 步 − 透過使用 getMin() 和 getMax 等內建函數，無需遍歷即可取得最小和最大元素()。

範例

從佇列中提取最後一個元素的C 程式碼

#

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

輸出

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

結論

優先隊列可以透過陣列、堆疊資料結構、鍊錶和二元樹來實現。它有助於暴露隱藏的路徑和各種演算法。

本教學到此結束，希望您覺得它有意義。

以上是提取優先隊列的最後一個元素而不進行遍歷的詳細內容。更多資訊請關注PHP中文網其他相關文章！