C++ の優先キューは、最も優先度の高い要素のみを考慮する STL の派生コンテナです。キューは FIFO ポリシーに従い、優先キューは優先度に基づいて要素をポップします。つまり、最も優先度の高い要素が最初にポップされます。
特定の点では通常のキューと似ていますが、次の点で異なります。
- 優先キューでは、キュー内のすべての要素が何らかの優先順位に関連付けられますが、優先順位はキューのデータ構造には存在しません。
- 優先キュー内の最も高い優先順位を持つ要素が最初に削除され、キューはその後に続きます。 FIFO(先入れ先出し) ポリシーは、最初に挿入された要素が最初に削除されることを意味します。
- 同じ優先度を持つ要素が複数存在する場合、キュー内の要素の順序が考慮されます。
注: 優先キューは、最も高い優先順位を持つ要素が最初に優先キューから削除される点を除いて、通常のキューの拡張バージョンです。
プライオリティキューの構文
priority_queue variable_name;
簡単な例を通してプライオリティ キューを理解しましょう。
上の図では、push() 関数を使用して要素を挿入しています。挿入操作は通常のキューと同じです。ただし、pop() 関数を使用してキューから要素を削除すると、最も優先度の高い要素が最初に削除されます。
プライオリティキューのメンバ関数
| 関数 | 説明 |
|---|---|
| 押す（） | 新しい要素を優先キューに挿入します。 |
| ポップ（） | 最も高い優先度を持つ先頭の要素をキューから削除します。 |
| 上（） | この関数は、優先キューの最上位の要素をアドレス指定するために使用されます。 |
| サイズ（） | 優先キューのサイズを決定します。 |
| 空の（） | キューが空かどうかを確認します。検証に基づいてステータスを返します。 |
| スワップ（） | 優先キューの要素を、同じタイプとサイズを持つ別のキューと交換します。 |
| 位置（） | 新しい要素を優先キューの先頭に挿入します。 |
プライオリティキューの簡単なプログラムを作成してみましょう。
#include #include using namespace std; int main() { priority_queue p; // variable declaration. p.push(10); // inserting 10 in a queue, top=10 p.push(30); // inserting 30 in a queue, top=30 p.push(20); // inserting 20 in a queue, top=20 cout<<'number of elements available in 'p' :'<<p>In the above code, we have created a priority queue in which we insert three elements, i.e., 10, 30, 20. After inserting the elements, we display all the elements of a priority queue by using a while loop.<p></p> <p> <strong>Output</strong> </p> <pre> Number of elements available in 'p' :3 30 20 10 zzzzz/ </pre> <p> <strong>Let's see another example of a priority queue.</strong> </p> <pre> #include #include using namespace std; int main() { priority_queue p; // priority queue declaration priority_queue q; // priority queue declaration p.push(1); // inserting element '1' in p. p.push(2); // inserting element '2' in p. p.push(3); // inserting element '3' in p. p.push(4); // inserting element '4' in p. q.push(5); // inserting element '5' in q. q.push(6); // inserting element '6' in q. q.push(7); // inserting element '7' in q. q.push(8); // inserting element '8' in q. p.swap(q); std::cout << 'Elements of p are : ' << std::endl; while(!p.empty()) { std::cout << p.top() << std::endl; p.pop(); } std::cout << 'Elements of q are :' << std::endl; while(!q.empty()) { std::cout << q.top() << std::endl; q.pop(); } return 0; } </pre> <p>In the above code, we have declared two priority queues, i.e., p and q. We inserted four elements in 'p' priority queue and four in 'q' priority queue. After inserting the elements, we swap the elements of 'p' queue with 'q' queue by using a swap() function.</p> <p> <strong>Output</strong> </p> <pre> Elements of p are : 8 7 6 5 Elements of q are : 4 3 2 1 </pre> <hr></'number> 優先キューの別の例を見てみましょう。
#include #include using namespace std; int main() { priority_queue p; // priority queue declaration priority_queue q; // priority queue declaration p.push(1); // inserting element '1' in p. p.push(2); // inserting element '2' in p. p.push(3); // inserting element '3' in p. p.push(4); // inserting element '4' in p. q.push(5); // inserting element '5' in q. q.push(6); // inserting element '6' in q. q.push(7); // inserting element '7' in q. q.push(8); // inserting element '8' in q. p.swap(q); std::cout << 'Elements of p are : ' << std::endl; while(!p.empty()) { std::cout << p.top() << std::endl; p.pop(); } std::cout << 'Elements of q are :' << std::endl; while(!q.empty()) { std::cout << q.top() << std::endl; q.pop(); } return 0; } 上記のコードでは、2 つの優先キュー、つまり p と q を宣言しました。 「p」優先キューに 4 つの要素を挿入し、「q」優先キューに 4 つの要素を挿入しました。要素を挿入した後、swap() 関数を使用して、「p」キューの要素を「q」キューと交換します。
出力
Elements of p are : 8 7 6 5 Elements of q are : 4 3 2 1