stack,queue,priority_queueの使い方 - 秋田大学ICPC対策室@wiki

stack,queue,priority_queueの使い方

データ構造でスタック、キュー、優先度付きキュー(priority_queue:プライオリティキュー)を使いたいことがあります。
C++ではSTLに最初から存在するので自分で実装する必要がありません。

データ構造としてのスタック、キュー、優先度付きキューについてはアルゴリズムの本に書いてあることが多いのでちゃんと理解をしておきましょう。
スタックについてはプログラミングコンテストチャレンジブック第二版p.31, キューについてはp.32, 優先度付きキューについてはp.69に説明があるので読んでおくとよいでしょう。
主にスタックは深さ優先探索をするときに、キューは幅優先探索をするときに、優先度付きキューはダイクストラ法やプリム法やA*探索をするときに使います。

stackでよく使うメンバ関数

// stack<T> st; とします.

// スタックの先頭に val を追加する. (戻り値:void)
st.push( const T& val );

// スタックの先頭の要素を削除する. (戻り値:void)
st.pop();

// スタックの先頭の要素への参照を返す. (戻り値:T&)
st.top();

// スタックの要素数を返す. (戻り値:size_type)
st.size();

// スタックの要素数が 0 のとき true , そうでないときは false を返す. (戻り値:bool)
st.empty();

queueでよく使うメンバ関数

// queue<T> que; とします.

// キューの先頭に val を追加する. (戻り値:void)
que.push( const T& val );

// キューの先頭の要素を削除する. (戻り値:void)
que.pop();

// キューの先頭の要素への参照を返す. (戻り値:T&)
que.front();

// キューの要素数を返す. (戻り値:size_type)
que.size();

// キューの要素数が 0 のとき true , そうでないときは false を返す. (戻り値:bool)
que.empty();

priority_queueでよく使うメンバ関数

優先度付きキューは値の最も大きいものから順に出てきます。

// priority_queue<T> que; とします.
// 宣言するときに
// priority_queue<T, vector<T>, greater<T> > que;
// とすることで値の小さい方から順に取り出すことができます.

// 優先度付きキューの先頭に val を追加する. (戻り値:void)
que.push( const T& val );

// 優先度付きキューの先頭の要素を削除する. (戻り値:void)
que.pop();

// 優先度付きキューの先頭の要素への参照を返す. (戻り値:T&)
que.top();

// 優先度付きキューの要素数を返す. (戻り値:size_type)
que.size();

// 優先度付きキューの要素数が 0 のとき true , そうでないときは false を返す. (戻り値:bool)
que.empty();

...