ｐｒｉｏｒｉｔｙ＿ｑｕｅｕｅ

[機能]

　　優先順位付き待ち行列を保持します．要素を追加すると，優先順位に従いソートされます．STL コンテナの一部を利用して，特別な機能を持たせたクラスであり，コンテナアダプタと呼ばれています．Container は queue を実際に保持するコンテナであり，省略すると vector になります．Comp に対しては，比較を行う二項関数オブジェクト名を指定します．指定しないと less （この場合は，降順）が選択されます．

template <class T, class Container = vector<T>, class Comp = less<Container::value_type> > class priority_queue
		

[使用方法]

#include <queue>
using namespace std;
priority_queue <T> 変数名;
		

[メンバー関数等]

• bool empty()
  コンテナが空か否かを返す

• void pop()
  先頭の要素を削除する

• void push(const value_type& x)
  要素を追加する

• size_type size()
  要素数を返す

• value_type& top()
  先頭の要素を返す

[使用例]

1. priority_queue の使用方法です．

   #include <stdio.h>
   #include <queue>
   using namespace std;
   
   void print1(priority_queue<int> &q) {
   	if (q.empty())
   		printf("   priority_queue は空です\n");
   	else
   		printf("   先頭の要素： %d\n", q.top());
   }
   
   void print2(priority_queue<int, vector<int>, greater<int> > &q) {
   	if (q.empty())
   		printf("   priority_queue は空です\n");
   	else
   		printf("   先頭の要素： %d\n", q.top());
   }
   
   int main()
   {
   	printf("less の場合\n");
   	priority_queue<int, vector<int>, less<int> > q1;
   					// push
   	q1.push(1);
   	print1(q1);
   	q1.push(3);
   	print1(q1);
   	q1.push(2);
   	print1(q1);
   					// pop
   	q1.pop();
   	print1(q1);
   	q1.pop();
   	print1(q1);
   	q1.pop();
   	print1(q1);
   
   	printf("\ngreater の場合\n");
   	priority_queue<int, vector<int>, greater<int> > q2;
   					// push
   	q2.push(1);
   	print2(q2);
   	q2.push(3);
   	print2(q2);
   	q2.push(2);
   	print2(q2);
   					// pop
   	q2.pop();
   	print2(q2);
   	q2.pop();
   	print2(q2);
   	q2.pop();
   	print2(q2);
   
   	return 0;
   }
   
   （出力）
   
   less の場合
      先頭の要素： 1
      先頭の要素： 3
      先頭の要素： 3
      先頭の要素： 2
      先頭の要素： 1
      priority_queue は空です
   
   greater の場合
      先頭の要素： 1
      先頭の要素： 1
      先頭の要素： 1
      先頭の要素： 2
      先頭の要素： 3
      priority_queue は空です
   			
   priority_queue の使用方法です（クラスオブジェクトを要素とした場合）．
   			
   #include <stdio.h>
   #include <queue>
   using namespace std;
   
   class Test {
   	public:
   		char *str;
   		int n;
   		Test (char *str1, int n1) {
   			str = new char [strlen(str1)+1];
   			strcpy(str, str1);
   			n = n1;
   		}
   };
   
   bool operator< (Test t1, Test t2)
   {
   	return strcmp(t1.str, t2.str) < 0 ? true : false;
   }
   
   int main()
   {
   	Test t1("abc", 20), t2("xyz", 30), t3("ghq", 40);
   	priority_queue<Test> q;
   					// push
   	q.push(t1);
   	q.push(t2);
   	q.push(t3);
   					// pop
   	printf("%s %d\n", (q.top()).str, (q.top()).n);
   	q.pop();
   	printf("%s %d\n", (q.top()).str, (q.top()).n);
   	q.pop();
   	printf("%s %d\n", (q.top()).str, (q.top()).n);
   	q.pop();
   
   	return 0;
   }
   
   （出力）
   
   xyz 30
   ghq 40
   abc 20
   			
   		

[参照]

queue， stack