不遍历提取优先队列的最后一个元素

介绍

C++ 中的优先队列与数据结构中的普通队列不同，它有一个区别：所有元素都有优先级。我们可以通过遍历队列来提取其元素。

但是，在本教程中，我们尝试了一种方法，用于在不遍历的情况下提取优先队列的最后一个元素。让我们开始吧……

什么是优先队列？

在数据结构中，抽象数据类型是优先队列。它是一个队列，其中所有元素都有一些相关的优先级。所有元素都根据其优先级被移除。优先级较高的数据优先于优先级较低的数据被提取。队列数据/元素可以是整数或字符串，但不能是 NULL 值。

如果两个元素具有相同的优先级，则优先队列将遵循 FIFO（先进先出）原则进行提取。

有两种类型的优先队列来提取其元素：

  • 升序优先队列 - 在这种类型的优先队列中，元素按升序提取。优先级最低的元素将首先被移除。

  • 降序优先队列 - 在这种类型的优先队列中，元素按降序提取。优先级最高的元素将首先被移除。

语法

 priority_queue<queue_type> queue_name

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

不遍历提取优先队列的最后一个元素

在这里，我们不遍历整个队列，而是提取优先队列的最后一个元素。我们通过二叉树实现优先队列。在过程中使用了以下内置方法：

  • 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++ 中提取队列中最后一个元素的代码

Open Compiler
#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

结论

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

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

更新于: 2023-02-22

2K+ 次浏览

开启您的 职业生涯

完成课程获得认证

立即开始
广告