span

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までを順に出力する再帰関数を書きます。

スタックを使ってブラウザの戻る/進む機能を実装するプログラムを書く[編集]

ブラウザの戻る/進む機能を実装するプログラムを書きます。

span

C++
stack

stacktrace