C++/標準ライブラリ/stack
標準ライブラリ<stack> ヘッダー
[編集]はじめに
[編集]スタックの概要
[編集]スタックは、LIFO（Last In, First Out）と呼ばれるデータ構造です。LIFOとは、「最後に追加されたものが最初に取り出される」という意味です。
スタックは、さまざまな用途に使用できます。例えば、
- 逆ポーランド記法の評価
- 再帰関数の呼び出し履歴の管理
- ブラウザの戻る/進む機能の実装
スタックの利点と用途
[編集]スタックには、以下のような利点があります。
- シンプルで理解しやすい
- 実装が簡単
- メモリ効率が良い
スタックは、以下のような用途に使用できます。
- 構文解析
- 式の評価
- 関数呼び出し
- システムログ
スタックの操作方法
[編集]スタックは以下の操作で操作できます。
push()- スタックに要素を追加する
pop()- スタックから要素を取り出す
top()- スタックのトップ要素を取得する
empty()- スタックが空かどうかを確認する
size()- スタックの要素数を取得する
スタックの定義
[編集]<stack>ヘッダーファイルの概要
[編集]<stack>ヘッダーファイルは、stackテンプレートクラスを宣言します。stackテンプレートクラスは、LIFOデータ構造を実装します。
stackテンプレートクラスの宣言
[編集]template <typename T> class stack;
この宣言は、stackテンプレートクラスが、要素型 T を持つことを意味します。
スタック要素型とコンテナー型
[編集]stackテンプレートクラスは、以下の要素型とコンテナー型をサポートします。
- 要素型
- 任意の型
- コンテナー型
- デフォルトは
vector、deque、listも指定可能
スタックのコンストラクタとデストラクタ
[編集]stackテンプレートクラスは以下のコンストラクタとデストラクタを定義します。
- デフォルトコンストラクタ
- 空のスタックを作成する
- コピーコンストラクタ
- 既存のスタックのコピーを作成する
- コピー代入演算子
- 既存のスタックを別のスタックにコピーする
- ムーブコンストラクタ
- 既存のスタックを別のスタックに移動する
- ムーブ代入演算子
- 既存のスタックを別のスタックに移動する
- デストラクタ
- スタックを破棄する
スタックの容量と空かどうかを確認するメンバ関数
[編集]stackテンプレートクラスは以下のメンバ関数を定義します。
empty()- スタックが空かどうかを確認する
size()- スタックの要素数を取得する
スタックの操作
[編集]push()メンバ関数: スタックに要素を追加する
[編集]push()メンバ関数は、スタックに要素を追加します。
stack<int> s; s.push(1); s.push(2); s.push(3);
このコードは、sというスタックに1、2、3という要素を追加します。
pop()メンバ関数: スタックから要素を取り出す
[編集]pop()メンバ関数は、スタックから要素を取り出します。
int i = s.pop();
このコードは、sというスタックからトップ要素を取り出し、iという変数に代入します。
top()メンバ関数: スタックのトップ要素を取得する
[編集]top()メンバ関数は、スタックのトップ要素を取得します。
int i = s.top();
このコードは、sというスタックのトップ要素を取得し、iという変数に代入します。
empty()メンバ関数: スタックが空かどうかを確認する
[編集]empty()メンバ関数は、スタックが空かどうかを確認します。
if (s.empty()) { // スタックが空の場合の処理 }
このコードは、sというスタックが空かどうかを確認し、空の場合は処理を行います。
size()メンバ関数: スタックの要素数を取得する
[編集]size()メンバ関数は、スタックの要素数を取得します。
int len = s.size();
このコードは、sというスタックの要素数を変数lenに残します。
スタックのイテレータ
[編集]stackイテレータの宣言
[編集]template <typename T> class stack::iterator { // ... };
この宣言は、stackテンプレートクラスのイテレータ型 iterator を宣言します。
イテレータのコンストラクタとデストラクタ
[編集]stackテンプレートクラスのイテレータは以下のコンストラクタとデストラクタを定義します。
- デフォルトコンストラクタ
- 初期化されていないイテレータを作成する
- コピーコンストラクタ
- 既存のイテレータのコピーを作成する
- コピー代入演算子
- 既存のイテレータを別のイテレータにコピーする
- デストラクタ
- イテレータを破棄する
イテレータのインクリメントとデクリメント
[編集]stackテンプレートクラスのイテレータは以下のインクリメントとデクリメント演算子を定義します。
++- イテレータを次の要素に移動する
--- イテレータを前の要素に移動する
イテレータの比較
[編集]stackテンプレートクラスのイテレータは以下の比較演算子を定義します。
==- 2つのイテレータが等しいかどうかを確認する
!=- 2つのイテレータが等しくないかどうかを確認する
<- 1つのイテレータが別のイテレータよりも小さいかどうかを確認する
<=- 1つのイテレータが別のイテレータ以下かどうかを確認する
>- 1つのイテレータが別のイテレータよりも大きいかどうかを確認する
>=- 1つのイテレータが別のイテレータ以上かどうかを確認する
イテレータの参照解除
[編集]stackテンプレートクラスのイテレータは以下の参照解除演算子を定義します。
*- イテレータが指している要素を取得する
スタックのアルゴリズム
[編集]std::swap()アルゴリズム: スタックを交換する
[編集]std::swap()アルゴリズムは、2つのスタックを交換します。
stack<int> s1, s2; // ... std::swap(s1, s2);
このコードは、s1とs2というスタックを交換します。
std::copy()アルゴリズム: スタックをコピーする
[編集]std::copy()アルゴリズムは、スタックを別のスタックにコピーします。
stack<int> s1, s2; // ... std::copy(s1.begin(), s1.end(), std::back_inserter(s2));
このコードは、s1というスタックの内容をs2というスタックにコピーします。
std::find()アルゴリズム: スタック内で要素を検索する
[編集]std::find()アルゴリズムは、スタック内で要素を検索します。
stack<int> s; // ... auto it = std::find(s.begin(), s.end(), 42); if (it != s.end()) { // 要素が見つかった場合の処理 }
このコードは、sというスタック内で42という要素を検索し、見つかった場合は処理を行います。
std::count()アルゴリズム: スタック内で要素の個数を数える
[編集]std::count()アルゴリズムは、スタック内で要素の個数を数えます。
stack<int> s; // ... int count = std::count(s.begin(), s.end(), 42);
このコードは、sというスタック内で42という要素の個数をカウントし、countという変数に代入します。
スタックの応用例
[編集]逆ポーランド記法の評価
[編集]逆ポーランド記法を評価するには、スタックを使用できます。
stack<int> s; for (const char* token : tokens) { if (isdigit(*token)) { s.push(std::stoi(token)); } else { int op2 = s.pop(); int op1 = s.pop(); switch (*token) { case '+': s.push(op1 + op2); break; case '-': s.push(op1 - op2); break; case '*': s.push(op1 * op2); break; case '/': s.push(op1 / op2); break; default: throw std::invalid_argument("invalid token"); } } } int result = s.top();
このコードは、逆ポーランド記法式を評価し、結果をresultという変数に代入します。
ブラウザの戻る/進む機能の実装
[編集]ブラウザの戻る/進む機能を実装するには、スタックを使用できます。
std::stack<std::string> history; void goBack() { if (history.empty()) { return; } history.pop(); // 前のページに移動 } void goForward() { if (history.empty()) { return; } history.pop(); // 次のページに移動 }
このコードは、ブラウザの戻る/進む機能を実装します。historyというスタックを使用して、閲覧したページの履歴を保存します。
まとめ
[編集]スタックの重要性と用途
[編集]スタックは、LIFOというデータ構造を実装するシンプルで効率的なデータ構造です。スタックは、逆ポーランド記法の評価、再帰関数の呼び出し履歴の管理、ブラウザの戻る/進む機能の実装など、さまざまな用途に使用できます。
スタックの使い方
[編集]スタックは、以下の操作で操作できます。
push()- スタックに要素を追加する
pop()- スタックから要素を取り出す
top()- スタックのトップ要素を取得する
empty()- スタックが空かどうかを確認する
size()- スタックの要素数を取得する
スタックの応用例
[編集]スタックは、以下のような応用例があります。
- 逆ポーランド記法の評価
- 再帰関数の呼び出し履歴の管理
- ブラウザの戻る/進む機能の実装
- 構文解析
- 式の評価
- 関数呼び出し
- システムログ
練習問題
[編集]スタックを使って逆ポーランド記法を評価するプログラムを書く
[編集]逆ポーランド記法式を入力とし、結果を出力するプログラムを書きます。
スタックを使って再帰関数を呼び出すプログラムを書く
[編集]nを引数とし、nから1までを順に出力する再帰関数を書きます。
スタックを使ってブラウザの戻る/進む機能を実装するプログラムを書く
[編集]ブラウザの戻る/進む機能を実装するプログラムを書きます。