STLスタック、キュー、優先キューの使用方法
STLにおけるスタックの使用方法(stack)
#include
基本操作:
push(x)xをスタックに追加する、すなわちスタック操作
pop()スタックアウト操作(スタックトップの削除)は、スタックアウトのみで、戻り値はありません
top()は、最初の要素(スタックトップ要素)を返します.
size()はスタック内の要素の数を返します.
Empty()スタックが空の場合、trueを返します.
STLでのキューの使用(queue)
#include
基本操作:
push(x)はxをキューの末端に押し込む
pop()ポップアップキューの最初の要素(キュートップ要素)です.この関数は値を返さないことに注意してください.
front()は、最初の要素(キュートップ要素)を返します.
back()は、最後に押し込まれた要素(キューテール要素)を返します.
Empty()キューが空の場合、trueを返します.
Size()戻りキューの長さ
--------スタックとキューの使い方は比較的簡単ですが、優先キューの使い方を詳しく説明します--------
STLでの優先キューの使用の詳細(priority_queu)
#include
基本操作:
Empty()キューが空の場合真を返す
pop()列ヘッダー要素の削除
push()に要素を加える
size()は、優先キューに存在する要素の数を返します.
top()は優先キューヘッダ要素を返す
デフォルトの優先キューでは、優先度の高い先行キューが表示されます.
標準ライブラリのデフォルトでは、要素タイプの<オペレータを使用して、それらの間の優先度関係を決定します.
(1)優先キューの第1の使用法は、最も一般的なデフォルトの優先度使用法、すなわち優先度の高い先出しキュー、例えばint優先キューであり、キューを出るときはintの大きい先出しキューである.
次に例を示します.
運転結果は大きくて小さい:5 4 3 1
(2)では,優先キュー内の優先度の低い要素を先にキューから出すにはどうすればよいのでしょうか.---カスタム優先度
①方法1:functionalヘッダファイルのgreater関数オブジェクトを比較関数として使用する比較関数を入力できます.
注:まずヘッダファイルを追加します:#include
priority_queue< int,vector,greater> q;//注意:>>誤記>>誤記する
これにより、低優先度要素の優先キューを作成します.
上の例を修正すると、実行すると、出力の順序が1 2 3 4 5になります.
もちろんgreaterに対向するlessは、lessという比較関数が入力されると、高優先度要素が先にキューから出ます.
priority_queue< int,vector,less> q;
priority_queue q;
以上で作成した優先キューは同じです.
②方法2:自己実現比較関数
priority_queue,cmp1 > q;
これにより、小さな値要素がキューから先に出る優先キューが作成され、ここでcmp 1の役割はgreaterに相当する.
同じように、私たちは次のように書くことができます.
priority_queue,cmp2 > q;
ここでは、大きな値要素の先頭キューを作成する優先キューです.ここでのcmp 2の役割はlessに相当します.
(3)優先キュー内の要素が構造オブジェクトまたはクラスオブジェクトである場合、優先順位比較を再カスタマイズするにはどうすればいいですか?
例1:要素xが1つしかない構造体を定義します.
①優先度の低い要素が先頭に立つ、すなわちx値の小さい先頭に立つ.
出力:1 2 3 4 5
②優先度の高い要素がキューから出る、すなわちx値の大きい先頭がキューから出る.
ただし、構造体でリロードされる演算子は<のみです.標準ライブラリでは、デフォルトで要素タイプの<オペレータを使用して優先度関係を決定します.リロード>の場合、コンパイルエラーが発生します.
例2:上記の例では,構造体におけるxの大きさを優先度比較値とした.次に、より一般的な例を示す.
この構造体ではpriorityが優先度値をキャラクタリゼーションする.
出力結果は、優先度値9 5 8 2 6 1 2 3 4
#include
基本操作:
push(x)xをスタックに追加する、すなわちスタック操作
pop()スタックアウト操作(スタックトップの削除)は、スタックアウトのみで、戻り値はありません
top()は、最初の要素(スタックトップ要素)を返します.
size()はスタック内の要素の数を返します.
Empty()スタックが空の場合、trueを返します.
STLでのキューの使用(queue)
#include
基本操作:
push(x)はxをキューの末端に押し込む
pop()ポップアップキューの最初の要素(キュートップ要素)です.この関数は値を返さないことに注意してください.
front()は、最初の要素(キュートップ要素)を返します.
back()は、最後に押し込まれた要素(キューテール要素)を返します.
Empty()キューが空の場合、trueを返します.
Size()戻りキューの長さ
--------スタックとキューの使い方は比較的簡単ですが、優先キューの使い方を詳しく説明します--------
STLでの優先キューの使用の詳細(priority_queu)
#include
基本操作:
Empty()キューが空の場合真を返す
pop()列ヘッダー要素の削除
push()に要素を加える
size()は、優先キューに存在する要素の数を返します.
top()は優先キューヘッダ要素を返す
デフォルトの優先キューでは、優先度の高い先行キューが表示されます.
標準ライブラリのデフォルトでは、要素タイプの<オペレータを使用して、それらの間の優先度関係を決定します.
(1)優先キューの第1の使用法は、最も一般的なデフォルトの優先度使用法、すなわち優先度の高い先出しキュー、例えばint優先キューであり、キューを出るときはintの大きい先出しキューである.
次に例を示します.
#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> q;
for(int i = 1;i <= 5;i++)
{
q.push(i);
}
for(int i = 0;i < 5;i++)
{
cout<<q.top()<<endl;
q.pop();
}
return 0;
}
運転結果は大きくて小さい:5 4 3 1
(2)では,優先キュー内の優先度の低い要素を先にキューから出すにはどうすればよいのでしょうか.---カスタム優先度
①方法1:functionalヘッダファイルのgreater関数オブジェクトを比較関数として使用する比較関数を入力できます.
注:まずヘッダファイルを追加します:#include
priority_queue< int,vector
これにより、低優先度要素の優先キューを作成します.
上の例を修正すると、実行すると、出力の順序が1 2 3 4 5になります.
もちろんgreaterに対向するlessは、lessという比較関数が入力されると、高優先度要素が先にキューから出ます.
priority_queue< int,vector
priority_queue
以上で作成した優先キューは同じです.
②方法2:自己実現比較関数
struct cmp1
{
bool operator ()(int x,int y)
{
return x>y; //
}
};
priority_queue
これにより、小さな値要素がキューから先に出る優先キューが作成され、ここでcmp 1の役割はgreaterに相当する.
同じように、私たちは次のように書くことができます.
struct cmp2
{
bool operator ()(int x,int y)
{
return x<y; //
}
};
priority_queue
ここでは、大きな値要素の先頭キューを作成する優先キューです.ここでのcmp 2の役割はlessに相当します.
(3)優先キュー内の要素が構造オブジェクトまたはクラスオブジェクトである場合、優先順位比較を再カスタマイズするにはどうすればいいですか?
例1:要素xが1つしかない構造体を定義します.
①優先度の低い要素が先頭に立つ、すなわちx値の小さい先頭に立つ.
struct number1
{
int x;
bool operator < (const number1 &a) const
{
return x>a.x;//
}
};
number1 num1[5];
priority_queue<number1>q;
for(int i = 1; i <= 5; i++)
{
num1[i].x = i;
q.push(num1[i]);
}
for(int i = 1; i <= 5; i++)
{
cout<<q.top().x<<endl;
q.pop();
}
出力:1 2 3 4 5
②優先度の高い要素がキューから出る、すなわちx値の大きい先頭がキューから出る.
struct number2
{
int x;
bool operator < (const number2 &a) const
{
return x<a.x;//
}
};
ただし、構造体でリロードされる演算子は<のみです.標準ライブラリでは、デフォルトで要素タイプの<オペレータを使用して優先度関係を決定します.リロード>の場合、コンパイルエラーが発生します.
例2:上記の例では,構造体におけるxの大きさを優先度比較値とした.次に、より一般的な例を示す.
struct node
{
friend bool operator < (node n1, node n2)
{
return n1.priority < n2.priority;
}
int priority;
int value;
};
この構造体ではpriorityが優先度値をキャラクタリゼーションする.
priority_queue<node> qn;
node b[5];
b[0].priority = 6; b[0].value = 1;
b[1].priority = 9; b[1].value = 5;
b[2].priority = 2; b[2].value = 3;
b[3].priority = 8; b[3].value = 2;
b[4].priority = 1; b[4].value = 4;
for(int i = 0; i < 5; i++)
qn.push(b[i]);
cout<<" "<<'\t'<<" "<<endl;
for(int i = 0; i < 5; i++)
{
cout<<qn.top().priority<<'\t'<<qn.top().value<<endl;
qn.pop();
}
出力結果は、優先度値9 5 8 2 6 1 2 3 4