C++のStandard Template Library (STL) において、stack、queue、そして priority_queue はコンテナアダプタ（Container Adapters）として分類されます。これらは単独のデータ構造を実装しているわけではなく、deque、vector、list といった既存のシーケンスコンテナをラップし、特定のアクセスルールと制約を持ったインターフェースを提供します。
std::stack
std::stack は LIFO（後入れ先出し）の原則に従うデータ構造を提供します。最後に追加された要素が最初にアクセスされ、削除されます。
ヘッダーとテンプレート定義
#include <stack>
template <
class T,
class Container = std::deque<T>
> class stack;
デフォルトの基盤コンテナは std::deque ですが、std::vector や std::list など、back()、push_back()、pop_back() のメンバ関数を持つ任意のシーケンスコンテナを指定できます。
初期化とコンストラクタ
stack(): 空のスタックを作成します。explicit stack(const Container& cont): 既存のコンテナの要素をコピーしてスタックを初期化します。要素の順序は元のコンテナと同じになります。
実装例：std::list を基盤としたスタックの操作
#include <iostream>
#include <stack>
#include <list>
#include <string>
int main() {
std::list<std::string> initial_tasks = {"Task_A", "Task_B", "Task_C"};
// std::listを基盤コンテナとしてスタックを構築
std::stack<std::string, std::list<std::string>> task_stack(initial_tasks);
// 新たな要素を追加
task_stack.push("Task_D");
// LIFOの順序で要素を処理して出力
while (!task_stack.empty()) {
std::cout << "Processing: " << task_stack.top() << '\n';
task_stack.pop();
}
return 0;
}
主要メンバ関数
void push(const T& value): スタックの最上部に要素を追加します。void pop(): スタックの最上部にある要素を削除します（値の返却は行いません）。T& top(): 最上部の要素への参照を返します。size_type size() const: スタックに格納されている要素数を返します。bool empty() const: スタックが空であるかどうかを判定します。void swap(stack& other) noexcept: 2つのスタックの要素を交換します。
比較演算子
スタック同士は、基盤となるコンテナの要素を先頭から順に比較することで、==, !=, <, <=, >, >= の辞書的比較が可能です。
std::queue
std::queue は FIFO（先入れ先出し）の原則に従うデータ構造を提供します。最初に追加された要素が最初にアクセスされ、削除されます。
ヘッダーとテンプレート定義
#include <queue>
template <
class T,
class Container = std::deque<T>
> class queue;
こちらもデフォルトでは std::deque を基盤としますが、std::list などの両端での挿入・削除が可能なコンテナを指定できます。
実装例：メッセージキューのシミュレーション
#include <iostream>
#include <queue>
int main() {
std::queue<int> message_queue;
// データのエンキュー
message_queue.push(101);
message_queue.push(202);
message_queue.push(303);
// 先頭と末尾の要素へのアクセス
std::cout << "Front element: " << message_queue.front() << '\n';
std::cout << "Back element: " << message_queue.back() << '\n';
// 先頭要素のデキュー
message_queue.pop();
std::cout << "After pop, new front: " << message_queue.front() << '\n';
return 0;
}
主要メンバ関数
void push(const T& value): キューの末尾に要素を追加します。void pop(): キューの先頭にある要素を削除します。T& front(): 先頭の要素への参照を返します。T& back(): 末尾の要素への参照を返します。size_type size() const: 格納されている要素数を返します。bool empty() const: キューが空かどうかを判定します。void swap(queue& other) noexcept: 2つのキューの要素を交換します。
std::priority_queue
std::priority_queue は、ヒープデータ構造を基盤とするキューです。要素は追加された順序ではなく、指定された優先度（デフォルトでは値の大小）に基づいて常に最も優先度の高い要素が先頭に配置されるようにソートされます。
ヘッダーとテンプレート定義
#include <queue>
template <
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
> class priority_queue;
基盤コンテナのデフォルトは std::vector です。比較関数オブジェクト（Compare）によって、最大ヒープ（デフォルト、std::less）または最小ヒープ（std::greater）としての振る舞いを決定します。
実装例：最大ヒープと最小ヒープの挙動
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
int main() {
// デフォルトの最大ヒープ（std::less を使用）
std::priority_queue<int> max_heap;
max_heap.push(45);
max_heap.push(12);
max_heap.push(88);
std::cout << "Max-Heap Top: " << max_heap.top() << '\n'; // 88が出力される
// 最小ヒープ（std::greater を使用）
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
min_heap.push(45);
min_heap.push(12);
min_heap.push(88);
std::cout << "Min-Heap Top: " << min_heap.top() << '\n'; // 12が出力される
// 要素の取り出し（最大ヒープ）
while (!max_heap.empty()) {
std::cout << max_heap.top() << " ";
max_heap.pop();
}
// 出力結果: 88 45 12
return 0;
}
主要メンバ関数
std::priority_queue は FIFO の順序保証を行わないため、front() や back() は提供されません。代わりに top() を使用して最優先要素にアクセスします。
void push(const T& value): 要素を挿入し、ヒープ構造を再構築します。void pop(): 優先度が最も高い要素（ヒープのルート）を削除します。T& top(): 優先度が最も高い要素への参照を返します。size_type size() const: 要素数を返します。bool empty() const: 空かどうかを判定します。void swap(priority_queue& other) noexcept: 要素を交換します。