將佇列轉換為優先佇列

---

介紹

佇列是一種線性資料結構，遵循 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 的末尾。

• 遞迴呼叫函式。

結論

優先佇列類似於資料結構中的佇列，唯一的區別在於佇列中每個元素的優先順序。普通佇列使用先進先出原則彈出所有元素，而優先佇列則按升序或降序移除元素。