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

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

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