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

---

介紹

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

但是，在本教程中，我們嘗試了一種方法，用於在不遍歷的情況下提取優先佇列的最後一個元素。讓我們開始吧……

什麼是優先佇列？

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

如果兩個元素具有相同的優先順序，則優先佇列將遵循 FIFO（先進先出）原則進行提取。

有兩種型別的優先佇列來提取其元素：

• 升序優先佇列 - 在這種型別的優先佇列中，元素按升序提取。優先順序最低的元素將首先被移除。

• 降序優先佇列 - 在這種型別的優先佇列中，元素按降序提取。優先順序最高的元素將首先被移除。

語法

 priority_queue<queue_type> queue_name

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

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

• size() - 返回優先佇列的大小。

  語法− queue_name.size()

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

  語法− queue_name.insert(data_type)

• getMin() - 返回優先佇列中最小的元素。

  語法− queue_name.getMin()

• getMax() - 返回優先佇列中最大的元素。

  語法− 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

結論

優先佇列可以透過陣列、堆資料結構、連結串列和二叉樹來實現。它有助於揭示隱藏的路徑和各種演算法。

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