将队列转换为优先队列

---

介绍

队列是一种线性数据结构，遵循 FIFO（先进先出）原则插入和移除元素，并且没有封闭的结尾。它在两端都是功能性的。在本教程中，我们将学习如何将队列转换为优先队列，并了解数据结构中队列和优先队列的含义。

什么是队列？

数据结构中的队列类似于现实生活中的队列，用于处理多个数据。它是一个有序列表，其中元素从后端进入，从前端移除。其中，先进入队列的元素将先被移除。

声明队列的语法

queue<data type> name 

什么是优先队列？

优先队列是一个结构化的队列，每个元素都有一个相关的优先级。优先队列中的元素根据其定义的优先级移除。如果两个元素具有相同的优先级，则它将遵循 FIFO（先进先出）原则。

队列中的优先级是每个元素的值。优先级最高的元素位于前端或顶部，其他元素则根据优先级出队。

声明优先队列的语法

priority_queue<data type> name

优先队列的类型−

1. 升序优先队列 − 在此优先队列中，元素按降序排列。值最小的元素具有最高优先级。例如：{2,6,8,9}，这是一个升序优先队列，2 具有最高优先级。

2. 降序优先队列 − 此队列中的所有元素都按升序排列。值最大的元素具有最高优先级。例如：{8,6,5,4,2}，这是一个降序队列，元素 8 具有最高优先级。

将队列转换为优先队列

我们通过按降序排列队列来将队列转换为优先队列。我们使用三个用户定义的函数和一些 C++ 库的内置函数。

过程中使用的方法

• push() − 用于插入队列数据。

  语法 − queue_name.push();

• pop() − 弹出队列元素。

  语法 − queue_name.pop();

• empty() − 它检查队列是否为空，如果队列为空则返回 True。

  语法 − queue_name.empty();

• front() − 它返回队列的第一个值。

  语法 − queue_name.front();

算法

步骤 1 − 将元素插入队列。

步骤 2 − 通过检查队列是否为空来排序队列。如果队列不为空，则弹出元素并返回；如果队列为空，则返回。

步骤 3 − 通过检查其第一个值来添加元素。

步骤 4 − 递归调用函数。

示例

将队列转换为优先队列的代码如下：

#include <bits/stdc++.h>
using namespace std;
   
void frontelement(queue<int>& q1, int q1size)     //function to check the front value of the queue
{
   if (q1size <= 0)                                                   // checking the queue size
   return;
   
   q1.push(q1.front());
   q1.pop();
   
   frontelement(q1, q1size - 1);
}
   
void addelement(queue<int>& q1, int val1, int q1size) //function to add elements in queue
{
   if (q1size == 0 || q1.empty()) {
      q1.push(val1);
      return;
   } 
   
   else if (val1 >= q1.front()) {
      
      q1.push(val1);
    
      frontelement(q1, q1size);
   } else {
   
      q1.push(q1.front());
      q1.pop();
   
      addelement(q1, val1, q1size - 1);
   }
}
   
void sortqueue(queue<int>& q1)    //function for queue sorting
{
   if (q1.empty()) {
      return;
   }
   
   int element = q1.front();
   q1.pop();
   sortqueue(q1);
   addelement(q1, element, q1.size());
}

// main code
int main()
{
   queue<int> q1;           //initializing queue
     
   //adding elements in the queue
   q1.push(4);
   q1.push(6);
   q1.push(5);
   q1.push(9);
   q1.push(3);
   q1.push(7);
   
   sortqueue(q1);
   
   while (!q1.empty()) {
      cout << q1.front() << " ";
      q1.pop();
   }
   
   return 0;
}

输出

9 7 6 5 4 3                                

上述代码的解释

• 使用 push() 函数将元素添加到队列 q1 中，队列包含 {4,6,5,9,3,7}。

• 调用 Sortqueue() 函数以降序排列队列 q1。

• 如果队列 q1 为空，则返回。

• 如果队列 q1 包含一个值，则将其第一个值存储在一个变量中并将其弹出。

• 声明 Insertqueue() 函数以将值插入队列。

• 它首先检查队列 q1 是否为空。

• 如果插入的值大于第一个值，则插入该值并递归调用该函数以检查所有插入的值。

• Frontelement() 函数检查队列 q1 是否为空，如果不为空，则弹出第一个值并将其添加到队列 q1 的末尾。

• 递归调用函数。

结论

优先队列类似于数据结构中的队列，唯一的区别在于队列中每个元素的优先级。普通队列使用先进先出原则弹出所有元素，而优先队列则按升序或降序移除元素。