C++の標準ライブラリには、データ構造として便利なstd::stackとstd::queueが用意されています。これらは、特定の操作に特化したコンテナアダプタで、効率的なデータ管理と操作が可能です。本記事では、std::stackとstd::queueの基本的な使い方から応用例までを詳しく解説し、データ構造の選択基準や実践的なコード例を通じて、理解を深めます。初心者から上級者まで、C++でのプログラミングをさらに効果的に行うための参考にしてください。
std::stackの基本的な使い方
std::stackは、LIFO（Last In, First Out）のデータ構造を実現するためのコンテナアダプタです。最も基本的な操作は、要素の追加（push）、要素の削除（pop）、およびトップ要素へのアクセス（top）です。以下では、これらの基本操作について説明します。
std::stackのヘッダーファイル
std::stackを使用するためには、まず<stack>ヘッダーファイルをインクルードする必要があります。
#include <stack>std::stackの宣言と初期化
std::stackの宣言は、テンプレート引数としてデータ型を指定するだけです。また、初期化も通常のコンテナと同様に行えます。
std::stack<int> stack; // int型のスタックを宣言要素の追加（push）
スタックに要素を追加するには、pushメソッドを使用します。
stack.push(10); // 10をスタックに追加
stack.push(20); // 20をスタックに追加要素の削除（pop）
スタックのトップ要素を削除するには、popメソッドを使用します。削除された要素は戻り値として取得されません。
stack.pop(); // トップ要素（20）を削除トップ要素へのアクセス（top）
スタックのトップ要素にアクセスするには、topメソッドを使用します。この操作は要素を削除せずに取得するだけです。
int topElement = stack.top(); // トップ要素（10）を取得空であるかの確認（empty）
スタックが空であるかを確認するには、emptyメソッドを使用します。
bool isEmpty = stack.empty(); // スタックが空ならtrueを返す要素数の取得（size）
スタックの要素数を取得するには、sizeメソッドを使用します。
size_t size = stack.size(); // スタックの要素数を取得以上が、std::stackの基本的な使い方です。
std::stackの応用例
std::stackは、基本的な操作に加えて、さまざまな応用場面で活用できます。ここでは、代表的な応用例として、括弧のバランスチェックと深さ優先探索（DFS）を紹介します。
括弧のバランスチェック
括弧のバランスをチェックするプログラムは、std::stackを使うことで効率的に実装できます。入力文字列が正しい括弧のペアを持つかを確認します。
#include <iostream>
#include <stack>
#include <string>
bool isBalanced(const std::string& expression) {
std::stack<char> stack;
for (char ch : expression) {
if (ch == '(' || ch == '{' || ch == '[') {
stack.push(ch);
} else if (ch == ')' || ch == '}' || ch == ']') {
if (stack.empty()) return false;
char top = stack.top();
stack.pop();
if ((ch == ')' && top != '(') ||
(ch == '}' && top != '{') ||
(ch == ']' && top != '[')) {
return false;
}
}
}
return stack.empty();
}
int main() {
std::string expression = "{[()]}";
if (isBalanced(expression)) {
std::cout << "Balanced\n";
} else {
std::cout << "Not Balanced\n";
}
return 0;
}このプログラムは、std::stackを使って括弧のバランスを確認します。開く括弧がスタックに積まれ、対応する閉じる括弧が出現するたびにスタックから取り出してチェックします。
深さ優先探索（DFS）
深さ優先探索は、グラフやツリーの探索アルゴリズムの一つで、std::stackを使うことで非再帰的に実装できます。
#include <iostream>
#include <vector>
#include <stack>
void DFS(int start, const std::vector<std::vector<int>>& graph) {
std::vector<bool> visited(graph.size(), false);
std::stack<int> stack;
stack.push(start);
while (!stack.empty()) {
int node = stack.top();
stack.pop();
if (!visited[node]) {
visited[node] = true;
std::cout << node << " ";
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
stack.push(neighbor);
}
}
}
}
}
int main() {
std::vector<std::vector<int>> graph = {
{1, 2}, // 0
{0, 3, 4}, // 1
{0, 4}, // 2
{1, 5}, // 3
{1, 2}, // 4
{3} // 5
};
std::cout << "DFS starting from node 0: ";
DFS(0, graph);
std::cout << std::endl;
return 0;
}このプログラムでは、グラフを表す隣接リストを入力として、DFSをスタックを使って実装しています。各ノードを訪問し、訪問済みでない隣接ノードをスタックに積むことで探索を進めます。
std::queueの基本的な使い方
std::queueは、FIFO（First In, First Out）のデータ構造を実現するためのコンテナアダプタです。最も基本的な操作は、要素の追加（push）、要素の削除（pop）、および先頭要素へのアクセス（front）です。以下では、これらの基本操作について説明します。
std::queueのヘッダーファイル
std::queueを使用するためには、まず<queue>ヘッダーファイルをインクルードする必要があります。
#include <queue>std::queueの宣言と初期化
std::queueの宣言は、テンプレート引数としてデータ型を指定するだけです。また、初期化も通常のコンテナと同様に行えます。
std::queue<int> queue; // int型のキューを宣言要素の追加（push）
キューに要素を追加するには、pushメソッドを使用します。
queue.push(10); // 10をキューに追加
queue.push(20); // 20をキューに追加要素の削除（pop）
キューの先頭要素を削除するには、popメソッドを使用します。削除された要素は戻り値として取得されません。
queue.pop(); // 先頭要素（10）を削除先頭要素へのアクセス（front）
キューの先頭要素にアクセスするには、frontメソッドを使用します。この操作は要素を削除せずに取得するだけです。
int frontElement = queue.front(); // 先頭要素（20）を取得末尾要素へのアクセス（back）
キューの末尾要素にアクセスするには、backメソッドを使用します。この操作も要素を削除せずに取得するだけです。
int backElement = queue.back(); // 末尾要素（20）を取得空であるかの確認（empty）
キューが空であるかを確認するには、emptyメソッドを使用します。
bool isEmpty = queue.empty(); // キューが空ならtrueを返す要素数の取得（size）
キューの要素数を取得するには、sizeメソッドを使用します。
size_t size = queue.size(); // キューの要素数を取得以上が、std::queueの基本的な使い方です。
std::queueの応用例
std::queueは、基本的な操作に加えて、さまざまな応用場面で活用できます。ここでは、代表的な応用例として、幅優先探索（BFS）とタスクスケジューリングを紹介します。
幅優先探索（BFS）
幅優先探索は、グラフやツリーの探索アルゴリズムの一つで、std::queueを使うことで非再帰的に実装できます。
#include <iostream>
#include <vector>
#include <queue>
void BFS(int start, const std::vector<std::vector<int>>& graph) {
std::vector<bool> visited(graph.size(), false);
std::queue<int> queue;
queue.push(start);
visited[start] = true;
while (!queue.empty()) {
int node = queue.front();
queue.pop();
std::cout << node << " ";
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
queue.push(neighbor);
visited[neighbor] = true;
}
}
}
}
int main() {
std::vector<std::vector<int>> graph = {
{1, 2}, // 0
{0, 3, 4}, // 1
{0, 4}, // 2
{1, 5}, // 3
{1, 2}, // 4
{3} // 5
};
std::cout << "BFS starting from node 0: ";
BFS(0, graph);
std::cout << std::endl;
return 0;
}このプログラムでは、グラフを表す隣接リストを入力として、BFSをキューを使って実装しています。各ノードを訪問し、訪問済みでない隣接ノードをキューに積むことで探索を進めます。
タスクスケジューリング
std::queueを使ったタスクスケジューリングは、タスクを順番に処理する際に役立ちます。ここでは、シンプルなタスクスケジューラの例を示します。
#include <iostream>
#include <queue>
#include <string>
struct Task {
int id;
std::string description;
};
void processTasks(std::queue<Task>& taskQueue) {
while (!taskQueue.empty()) {
Task currentTask = taskQueue.front();
taskQueue.pop();
std::cout << "Processing Task ID: " << currentTask.id
<< " - " << currentTask.description << std::endl;
}
}
int main() {
std::queue<Task> taskQueue;
taskQueue.push({1, "Task 1: Process Data"});
taskQueue.push({2, "Task 2: Send Email"});
taskQueue.push({3, "Task 3: Generate Report"});
std::cout << "Starting Task Processing..." << std::endl;
processTasks(taskQueue);
return 0;
}このプログラムでは、タスクをstd::queueに追加し、先入れ先出しでタスクを処理しています。各タスクはキューの先頭から取り出され、順番に処理されます。
std::stackとstd::queueの違い
std::stackとstd::queueは、どちらもC++標準ライブラリで提供されるデータ構造ですが、その動作と用途には明確な違いがあります。ここでは、それぞれの特徴と使い分けについて説明します。
データ構造の特性
std::stackとstd::queueは、データの挿入と削除の方式が異なります。
std::stackの特性
- LIFO（Last In, First Out）: 最後に挿入された要素が最初に削除される。
- 主な操作:
push（要素の追加）、pop（要素の削除）、top（トップ要素の参照）。
#include <stack>
std::stack<int> stack;
stack.push(1);
stack.push(2);
stack.pop(); // 2が削除される
int topElement = stack.top(); // topElementは1std::queueの特性
- FIFO（First In, First Out）: 最初に挿入された要素が最初に削除される。
- 主な操作:
push（要素の追加）、pop（要素の削除）、front（先頭要素の参照）、back（末尾要素の参照）。
#include <queue>
std::queue<int> queue;
queue.push(1);
queue.push(2);
queue.pop(); // 1が削除される
int frontElement = queue.front(); // frontElementは2用途の違い
用途に応じて、適切なデータ構造を選択することが重要です。
std::stackの主な用途
- 関数呼び出しの管理: 再帰関数の呼び出し管理に使用される。
- 括弧のバランスチェック: 開括弧と閉括弧の対応を確認するために使用される。
- 深さ優先探索（DFS）: グラフ探索アルゴリズムで使用される。
std::queueの主な用途
- タスクスケジューリング: タスクを順序通りに処理するために使用される。
- 幅優先探索（BFS）: グラフ探索アルゴリズムで使用される。
- バッファリング: データストリームの一時的な保管に使用される。
選択基準
- LIFOが必要な場合:
std::stackを選択。 - FIFOが必要な場合:
std::queueを選択。
以上が、std::stackとstd::queueの違いと使い分けについての説明です。
std::priority_queueの使い方
std::priority_queueは、要素が優先度付きで管理されるデータ構造です。通常のキューとは異なり、要素は内部でソートされ、最も高い優先度の要素が常に先頭に来るようになっています。ここでは、std::priority_queueの基本的な使い方を解説します。
std::priority_queueのヘッダーファイル
std::priority_queueを使用するためには、まず<queue>ヘッダーファイルをインクルードする必要があります。
#include <queue>std::priority_queueの宣言と初期化
std::priority_queueの宣言は、テンプレート引数としてデータ型とコンテナ型、比較関数を指定します。デフォルトでは最大ヒープ（最大の要素がトップに来る）として機能します。
std::priority_queue<int> pq; // int型の優先度付きキューを宣言要素の追加（push）
優先度付きキューに要素を追加するには、pushメソッドを使用します。
pq.push(10); // 10を追加
pq.push(20); // 20を追加
pq.push(5); // 5を追加要素の削除（pop）
優先度付きキューのトップ要素を削除するには、popメソッドを使用します。削除された要素は戻り値として取得されません。
pq.pop(); // トップ要素（20）を削除トップ要素へのアクセス（top）
優先度付きキューのトップ要素にアクセスするには、topメソッドを使用します。この操作は要素を削除せずに取得するだけです。
int topElement = pq.top(); // トップ要素（10）を取得カスタム比較関数を使用したpriority_queue
std::priority_queueは、デフォルトの最大ヒープ以外にカスタム比較関数を使用して動作を変更できます。以下の例では、最小ヒープ（最小の要素がトップに来る）を作成します。
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
minHeap.push(10);
minHeap.push(20);
minHeap.push(5);
std::cout << "Top element: " << minHeap.top() << std::endl; // 出力: 5
minHeap.pop();
std::cout << "Top element after pop: " << minHeap.top() << std::endl; // 出力: 10
return 0;
}この例では、std::greater<int>を比較関数として使用することで、最小ヒープを実現しています。
空であるかの確認（empty）
優先度付きキューが空であるかを確認するには、emptyメソッドを使用します。
bool isEmpty = pq.empty(); // キューが空ならtrueを返す要素数の取得（size）
優先度付きキューの要素数を取得するには、sizeメソッドを使用します。
size_t size = pq.size(); // キューの要素数を取得以上が、std::priority_queueの基本的な使い方です。
データ構造の選択基準
C++の標準ライブラリには、さまざまなデータ構造が用意されています。それぞれのデータ構造には特定の用途があり、適切なものを選ぶことが重要です。ここでは、std::stack、std::queue、std::priority_queueの選択基準について説明します。
用途に応じたデータ構造の選択
std::stackを選ぶ場合
- 関数呼び出しの管理: 再帰的な関数呼び出しや関数の呼び出し履歴を管理する場合に適しています。
- 括弧のバランスチェック: 括弧の対応関係を確認するためのアルゴリズムに使用されます。
- 深さ優先探索（DFS）: グラフやツリーの探索において、スタックを利用して探索を行います。
#include <stack>
std::stack<int> stack;
stack.push(1);
stack.push(2);
stack.pop(); // 2が削除される
int topElement = stack.top(); // topElementは1std::queueを選ぶ場合
- タスクスケジューリング: タスクを順番に処理する際に、先入れ先出し（FIFO）の特性が有効です。
- 幅優先探索（BFS）: グラフやツリーの探索において、キューを利用してレベルごとに探索を行います。
- バッファリング: データの一時的な保管に適しています。データが順番に処理される場合に有効です。
#include <queue>
std::queue<int> queue;
queue.push(1);
queue.push(2);
queue.pop(); // 1が削除される
int frontElement = queue.front(); // frontElementは2std::priority_queueを選ぶ場合
- 優先度付きタスク管理: タスクの優先度に応じて処理順序を決定する場合に適しています。最も高い優先度のタスクを先に処理します。
- ダイクストラアルゴリズム: 最短経路を求めるアルゴリズムで、優先度付きキューが利用されます。
- ヒープソート: 優先度付きキューを使ったソートアルゴリズムです。
#include <queue>
std::priority_queue<int> pq;
pq.push(10);
pq.push(20);
pq.push(5);
pq.pop(); // トップ要素（20）が削除される
int topElement = pq.top(); // topElementは10選択基準のまとめ
- LIFOが必要な場合:
std::stack - FIFOが必要な場合:
std::queue - 優先度順が必要な場合:
std::priority_queue
これらのデータ構造の特性と用途を理解し、適切な場面で選択することで、効率的なプログラムの実装が可能になります。
演習問題
学んだ内容を実践し、理解を深めるための演習問題を以下に示します。これらの問題を解くことで、std::stack、std::queue、およびstd::priority_queueの使い方を復習できます。
演習問題1: 括弧のバランスチェック
括弧のバランスをチェックする関数を実装してください。入力は括弧のみを含む文字列とし、正しい括弧の対応関係を持つかどうかを判定する関数を作成します。
#include <iostream>
#include <stack>
#include <string>
bool isBalanced(const std::string& expression) {
std::stack<char> stack;
for (char ch : expression) {
if (ch == '(' || ch == '{' || ch == '[') {
stack.push(ch);
} else if (ch == ')' || ch == '}' || ch == ']') {
if (stack.empty()) return false;
char top = stack.top();
stack.pop();
if ((ch == ')' && top != '(') ||
(ch == '}' && top != '{') ||
(ch == ']' && top != '[')) {
return false;
}
}
}
return stack.empty();
}
int main() {
std::string expression = "{[()]}";
if (isBalanced(expression)) {
std::cout << "Balanced\n";
} else {
std::cout << "Not Balanced\n";
}
return 0;
}演習問題2: 幅優先探索（BFS）
与えられたグラフを幅優先探索（BFS）する関数を実装してください。グラフは隣接リストで表現されます。
#include <iostream>
#include <vector>
#include <queue>
void BFS(int start, const std::vector<std::vector<int>>& graph) {
std::vector<bool> visited(graph.size(), false);
std::queue<int> queue;
queue.push(start);
visited[start] = true;
while (!queue.empty()) {
int node = queue.front();
queue.pop();
std::cout << node << " ";
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
queue.push(neighbor);
visited[neighbor] = true;
}
}
}
}
int main() {
std::vector<std::vector<int>> graph = {
{1, 2}, // 0
{0, 3, 4}, // 1
{0, 4}, // 2
{1, 5}, // 3
{1, 2}, // 4
{3} // 5
};
std::cout << "BFS starting from node 0: ";
BFS(0, graph);
std::cout << std::endl;
return 0;
}演習問題3: 優先度付きタスク管理
優先度付きタスク管理をシミュレートするプログラムを作成してください。タスクは構造体で表現され、優先度付きキューを使って管理されます。
#include <iostream>
#include <queue>
#include <string>
struct Task {
int priority;
std::string description;
// 優先度が高いタスクが先に処理されるようにする
bool operator<(const Task& other) const {
return priority < other.priority;
}
};
void processTasks(std::priority_queue<Task>& taskQueue) {
while (!taskQueue.empty()) {
Task currentTask = taskQueue.top();
taskQueue.pop();
std::cout << "Processing Task: " << currentTask.description
<< " with priority " << currentTask.priority << std::endl;
}
}
int main() {
std::priority_queue<Task> taskQueue;
taskQueue.push({3, "Low priority task"});
taskQueue.push({1, "High priority task"});
taskQueue.push({2, "Medium priority task"});
std::cout << "Starting Task Processing..." << std::endl;
processTasks(taskQueue);
return 0;
}これらの演習問題に取り組むことで、std::stack、std::queue、およびstd::priority_queueの操作に慣れることができるでしょう。
まとめ
本記事では、C++の標準ライブラリに含まれるstd::stack、std::queue、およびstd::priority_queueについて、基本的な使い方から応用例まで詳しく解説しました。これらのデータ構造は、効率的なデータ管理と操作を可能にし、特定の用途に応じた選択が重要です。
std::stackはLIFO構造を提供し、関数呼び出しの管理や深さ優先探索に適しています。std::queueはFIFO構造を提供し、タスクスケジューリングや幅優先探索に適しています。std::priority_queueは要素の優先度に基づいた順序付けを行い、優先度付きタスク管理や最短経路探索に有効です。
さらに、各データ構造の具体的な使用例と演習問題を通じて、実際のコードを用いて理解を深めることができました。これらの知識を活用して、C++でのプログラミングをさらに効果的に行いましょう。
コメント