stack

[C++] std::stackの使い方について詳しく解説

C++のstd::stackは、LIFO(Last In, First Out)構造を提供するコンテナアダプタです。

#include <stack>をインクルードして使用します。

主な操作として、pushで要素を追加し、popで削除、topで最上位の要素を参照します。

emptyはスタックが空かを確認し、sizeで要素数を取得可能です。

内部コンテナにはデフォルトでstd::dequeが使用されますが、std::vectorやstd::listも指定可能です。

目次から探す

std::stackとは

std::stackは、C++の標準ライブラリに含まれるコンテナアダプタの一つで、LIFO(Last In, First Out)構造を持つデータ構造です。

これは、最後に追加された要素が最初に取り出されることを意味します。

スタックは、主に関数の呼び出し履歴や、逆ポーランド記法の計算など、特定のアルゴリズムやデータ処理において非常に便利です。

特徴

LIFO構造: 最後に追加された要素が最初に取り出される。
簡単なインターフェース: プッシュ、ポップ、トップの操作が簡単に行える。
メモリ管理: 自動的にメモリを管理し、必要に応じてサイズを変更する。

以下は、std::stackを使用した基本的な例です。

#include <iostream>
#include <stack>
int main() {
    std::stack<int> myStack; // 整数型のスタックを作成
    // 要素をスタックに追加
    myStack.push(1); // 1を追加
    myStack.push(2); // 2を追加
    myStack.push(3); // 3を追加
    // スタックのトップ要素を表示
    std::cout << "スタックのトップ要素: " << myStack.top() << std::endl; // 3が表示される
    // スタックから要素を取り出す
    myStack.pop(); // 3を取り出す
    std::cout << "スタックの新しいトップ要素: " << myStack.top() << std::endl; // 2が表示される
    return 0;
}

スタックのトップ要素: 3
スタックの新しいトップ要素: 2

この例では、整数型のスタックを作成し、要素を追加したり、トップ要素を表示したり、要素を取り出したりしています。

std::stackは、シンプルで使いやすいデータ構造であり、さまざまな場面で活用できます。

std::stackの基本操作

std::stackには、基本的な操作がいくつか用意されています。

これらの操作を理解することで、スタックを効果的に利用できるようになります。

以下に、主要な操作を紹介します。

主な操作一覧

操作名	説明
`push`	スタックのトップに要素を追加する。
`pop`	スタックのトップの要素を削除する。
`top`	スタックのトップの要素を取得する。
`empty`	スタックが空かどうかを確認する。
`size`	スタックに含まれる要素の数を取得する。

各操作の詳細

push

pushメソッドは、指定した要素をスタックのトップに追加します。

スタックのサイズが1増加します。

myStack.push(10); // 10をスタックに追加

pop

popメソッドは、スタックのトップにある要素を削除します。

この操作は、削除された要素を返しません。

スタックのサイズが1減少します。

myStack.pop(); // トップの要素を削除

top

topメソッドは、スタックのトップにある要素を返しますが、スタックからは削除しません。

スタックが空の場合、このメソッドを呼び出すと未定義の動作になります。

int topElement = myStack.top(); // トップの要素を取得

empty

emptyメソッドは、スタックが空であるかどうかを確認します。

空であればtrue、そうでなければfalseを返します。

if (myStack.empty()) {
    std::cout << "スタックは空です。" << std::endl;
}

size

sizeメソッドは、スタックに含まれる要素の数を返します。

std::cout << "スタックのサイズ: " << myStack.size() << std::endl; // スタックのサイズを表示

以下は、これらの基本操作をすべて含むサンプルコードです。

#include <iostream>
#include <stack>
int main() {
    std::stack<int> myStack; // 整数型のスタックを作成
    // 要素を追加
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);
    // スタックのサイズを表示
    std::cout << "スタックのサイズ: " << myStack.size() << std::endl; // 3が表示される
    // トップ要素を表示
    std::cout << "スタックのトップ要素: " << myStack.top() << std::endl; // 3が表示される
    // トップ要素を削除
    myStack.pop();
    // 新しいトップ要素を表示
    std::cout << "スタックの新しいトップ要素: " << myStack.top() << std::endl; // 2が表示される
    // スタックが空かどうかを確認
    if (!myStack.empty()) {
        std::cout << "スタックは空ではありません。" << std::endl;
    }
    return 0;
}

スタックのサイズ: 3
スタックのトップ要素: 3
スタックの新しいトップ要素: 2
スタックは空ではありません。

このサンプルコードでは、std::stackの基本操作を実際に行い、その結果を表示しています。

これにより、スタックの使い方を具体的に理解することができます。

std::stackの活用例

std::stackは、さまざまな場面で活用されるデータ構造です。

ここでは、いくつかの具体的な活用例を紹介します。

これにより、スタックの実用性を理解し、実際のプログラミングに役立てることができます。

1. 関数の呼び出し履歴管理

スタックは、関数の呼び出し履歴を管理するのに適しています。

関数が呼び出されるたびに、その関数の情報をスタックにプッシュし、戻る際にはポップすることで、呼び出し元に戻ることができます。

#include <iostream>
#include <stack>
#include <string>
int main() {
    std::stack<std::string> callStack; // 関数呼び出し履歴を管理するスタック
    // 関数呼び出しをシミュレート
    callStack.push("main");
    callStack.push("functionA");
    callStack.push("functionB");
    // 現在の関数を表示
    std::cout << "現在の関数: " << callStack.top() << std::endl; // functionBが表示される
    // 戻る
    callStack.pop(); // functionBから戻る
    std::cout << "戻った関数: " << callStack.top() << std::endl; // functionAが表示される
    return 0;
}

現在の関数: functionB
戻った関数: functionA

2. 逆ポーランド記法の計算

スタックは、逆ポーランド記法(RPN)を用いた計算に非常に便利です。

数値をスタックにプッシュし、演算子が現れたらスタックから必要な数値をポップして計算を行います。

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
int evaluateRPN(const std::string& expression) {
    std::stack<int> myStack;
    std::istringstream iss(expression);
    std::string token;
    while (iss >> token) {
        if (isdigit(token[0])) {
            myStack.push(std::stoi(token)); // 数値をスタックに追加
        } else {
            int b = myStack.top(); myStack.pop(); // 2つの数値を取り出す
            int a = myStack.top(); myStack.pop();
            switch (token[0]) {
                case '+': myStack.push(a + b); break;
                case '-': myStack.push(a - b); break;
                case '*': myStack.push(a * b); break;
                case '/': myStack.push(a / b); break;
            }
        }
    }
    return myStack.top(); // 最終結果を返す
}
int main() {
    std::string expression = "3 4 + 2 * 7 /"; // (3 + 4) * 2 / 7
    std::cout << "計算結果: " << evaluateRPN(expression) << std::endl; // 2が表示される
    return 0;
}

計算結果: 2

3. バランスの取れた括弧の検証

スタックは、括弧のバランスを検証するのにも役立ちます。

開き括弧をスタックにプッシュし、閉じ括弧が現れたときにスタックからポップして対応を確認します。

#include <iostream>
#include <stack>
#include <string>
bool isBalanced(const std::string& expression) {
    std::stack<char> myStack;
    for (char ch : expression) {
        if (ch == '(') {
            myStack.push(ch); // 開き括弧を追加
        } else if (ch == ')') {
            if (myStack.empty()) return false; // 閉じ括弧が多い
            myStack.pop(); // 対応する開き括弧を削除
        }
    }
    return myStack.empty(); // スタックが空ならバランスが取れている
}
int main() {
    std::string expression = "(a + b) * (c - d)"; // バランスの取れた式
    std::cout << "括弧のバランス: " << (isBalanced(expression) ? "正しい" : "間違っている") << std::endl; // 正しいが表示される
    return 0;
}

括弧のバランス: 正しい

これらの例から、std::stackがどのように実用的な問題を解決するために使用されるかがわかります。

スタックは、特定のデータ処理やアルゴリズムにおいて非常に強力なツールです。

std::stackの注意点と制限

std::stackは非常に便利なデータ構造ですが、使用する際にはいくつかの注意点や制限があります。

これらを理解しておくことで、より効果的にスタックを活用できるようになります。

1. スタックのサイズ制限

std::stackは、内部で他のコンテナ(通常はstd::dequeやstd::vector)を使用して要素を管理します。

そのため、スタックのサイズは使用しているコンテナのサイズ制限に依存します。

大量のデータを扱う場合、メモリ不足に陥る可能性があります。

2. 空のスタックに対する操作

空のスタックに対してtopやpopを呼び出すと、未定義の動作が発生します。

これを避けるためには、emptyメソッドを使用してスタックが空でないことを確認する必要があります。

if (!myStack.empty()) {
    myStack.pop(); // スタックが空でない場合のみポップ
}

3. スタックの要素への直接アクセス不可

std::stackは、LIFO構造を持つため、要素への直接アクセスはできません。

スタックの要素を取得するには、必ずtopメソッドを使用する必要があります。

このため、特定の要素を検索する場合は、他のデータ構造を使用する方が適切です。

4. スタックの要素の順序

スタックはLIFO構造であるため、要素の順序が逆になります。

これは、特定のアルゴリズムやデータ処理においては便利ですが、順序が重要な場合には注意が必要です。

5. スタックのコピーと移動

std::stackは、デフォルトでコピーコンストラクタと代入演算子を持っていますが、内部のコンテナの特性に依存します。

特に、スタックをコピーする際には、内部のコンテナが正しくコピーされることを確認する必要があります。

移動セマンティクスを使用する場合も同様です。

6. スタックのパフォーマンス

std::stackの操作は、一般的にO(1)の時間計算量で実行されますが、内部のコンテナによっては、メモリの再割り当てが発生することがあります。

これにより、パフォーマンスが低下する可能性があるため、大量のデータを扱う場合は注意が必要です。

7. スタックのスレッドセーフではない

std::stackは、スレッドセーフではありません。

複数のスレッドから同時にアクセスする場合は、適切なロック機構を使用して、データ競合を防ぐ必要があります。

これらの注意点と制限を理解することで、std::stackをより効果的に活用し、潜在的な問題を回避することができます。

スタックは強力なデータ構造ですが、適切な使用方法を知っておくことが重要です。

std::stackを使った応用テクニック

std::stackは、基本的なデータ構造としてだけでなく、さまざまな応用テクニックにも利用できます。

ここでは、std::stackを使ったいくつかの応用テクニックを紹介します。

これにより、スタックの活用方法をさらに広げることができます。

1. 深さ優先探索(DFS)

スタックは、グラフや木構造の深さ優先探索(DFS)アルゴリズムに非常に適しています。

ノードをスタックにプッシュし、訪問したノードをポップすることで、探索を行います。

#include <iostream>
#include <stack>
#include <vector>
void depthFirstSearch(int start, const std::vector<std::vector<int>>& graph) {
    std::stack<int> myStack;
    std::vector<bool> visited(graph.size(), false);
    myStack.push(start); // 開始ノードをスタックに追加
    while (!myStack.empty()) {
        int node = myStack.top(); // スタックのトップを取得
        myStack.pop(); // トップを削除
        if (!visited[node]) {
            visited[node] = true; // ノードを訪問済みにする
            std::cout << "訪問ノード: " << node << std::endl;
            // 隣接ノードをスタックに追加
            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    myStack.push(neighbor);
                }
            }
        }
    }
}
int main() {
    // グラフの隣接リスト表現
    std::vector<std::vector<int>> graph = {
        {1, 2},    // ノード0の隣接ノード
        {0, 3, 4}, // ノード1の隣接ノード
        {0},       // ノード2の隣接ノード
        {1},       // ノード3の隣接ノード
        {1}        // ノード4の隣接ノード
    };
    std::cout << "深さ優先探索の結果:" << std::endl;
    depthFirstSearch(0, graph); // ノード0から探索開始
    return 0;
}

深さ優先探索の結果:
訪問ノード: 0
訪問ノード: 2
訪問ノード: 1
訪問ノード: 4
訪問ノード: 3

2. 逆文字列の生成

スタックを使用して文字列を逆にすることができます。

文字をスタックにプッシュし、ポップすることで逆順に取り出すことができます。

#include <iostream>
#include <stack>
#include <string>
std::string reverseString(const std::string& str) {
    std::stack<char> myStack;
    
    // 文字をスタックに追加
    for (char ch : str) {
        myStack.push(ch);
    }
    std::string reversed;
    // スタックから文字を取り出して逆順にする
    while (!myStack.empty()) {
        reversed += myStack.top();
        myStack.pop();
    }
    return reversed;
}
int main() {
    std::string original = "Hello, World!";
    std::string reversed = reverseString(original);
    std::cout << "逆順の文字列: " << reversed << std::endl; // !dlroW ,olleHが表示される
    return 0;
}

逆順の文字列: !dlroW ,olleH

3. 中置表現から後置表現への変換

スタックを使用して、中置表現の数式を後置表現(逆ポーランド記法)に変換することができます。

演算子の優先順位を考慮しながら、スタックを使って変換を行います。

#include <iostream>
#include <stack>
#include <string>
#include <cctype>
int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}
std::string infixToPostfix(const std::string& expression) {
    std::stack<char> myStack;
    std::string postfix;
    for (char ch : expression) {
        if (std::isalnum(ch)) {
            postfix += ch; // オペランドを後置表現に追加
        } else if (ch == '(') {
            myStack.push(ch); // 開き括弧をスタックに追加
        } else if (ch == ')') {
            while (!myStack.empty() && myStack.top() != '(') {
                postfix += myStack.top(); // スタックから演算子を取り出す
                myStack.pop();
            }
            myStack.pop(); // 開き括弧を削除
        } else { // 演算子
            while (!myStack.empty() && precedence(myStack.top()) >= precedence(ch)) {
                postfix += myStack.top(); // スタックから演算子を取り出す
                myStack.pop();
            }
            myStack.push(ch); // 演算子をスタックに追加
        }
    }
    // 残っている演算子を後置表現に追加
    while (!myStack.empty()) {
        postfix += myStack.top();
        myStack.pop();
    }
    return postfix;
}
int main() {
    std::string expression = "A+B*(C^D-E)^(F+G*H)"; // 中置表現
    std::string postfix = infixToPostfix(expression);
    std::cout << "後置表現: " << postfix << std::endl; // AB+CD^E-FGH*+^*が表示される
    return 0;
}