简介

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

结论

优先队列可以通过数组、堆数据结构、链表和二叉树来实现。它有助于暴露隐藏的路径和各种算法。

本教程到此结束，希望您觉得它有意义。