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

2023-06-152024-06-01

この記事では、C++の標準ライブラリに含まれるstd::stackについて詳しく解説します。

std::stackは、データを一時的に保存し、後で取り出すための便利なデータ構造です。

この記事を読むことで、以下のことがわかります：

std::stackの基本的な使い方
要素の追加や削除、参照などの基本操作
スタックの応用操作や内部実装
実際のプログラムでの使用例
使用する際の注意点とベストプラクティス

初心者の方でも理解しやすいように、具体的なコード例とともに解説しています。

目次から探す

std::stackとは

std::stackの概要

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

これは、最後に追加された要素が最初に取り出されるという特性を持っています。

std::stackは、内部的には他のコンテナ(デフォルトではstd::deque)を利用して実装されていますが、ユーザーはその内部構造を意識する必要はありません。

スタックの基本的な概念

スタックは、データを一時的に保存し、後で取り出すためのデータ構造です。

スタックの操作は主に以下の2つです：

push: 新しい要素をスタックの一番上に追加します。
pop: スタックの一番上の要素を取り出し、削除します。

これに加えて、スタックの一番上の要素を参照するtopや、スタックが空かどうかを確認するempty、スタックのサイズを取得するsizeといった操作も一般的です。

std::stackの用途と利点

std::stackは、特定のアルゴリズムやデータ処理において非常に便利です。

以下にその主な用途と利点を挙げます：

関数呼び出しの管理:

スタックは、関数呼び出しの管理に使われることが多いです。

関数が呼び出されるたびに、その情報がスタックに保存され、関数が終了するとその情報がスタックから取り出されます。

逆順処理:

スタックを使うことで、データを逆順に処理することが簡単にできます。

例えば、文字列を逆順に表示する場合などに利用されます。

深さ優先探索(DFS):

グラフやツリーの探索アルゴリズムである深さ優先探索は、スタックを利用して実装されることが多いです。

括弧のバランスチェック:

プログラムのソースコードや数式において、括弧が正しく対応しているかをチェックする際にスタックが利用されます。

以下に、std::stackの基本的な使い方を示す簡単なコード例を紹介します。

#include <iostream>
#include <stack>
int main() {
    std::stack<int> s;
    // 要素をスタックに追加
    s.push(1);
    s.push(2);
    s.push(3);
    // スタックのトップ要素を表示
    std::cout << "Top element: " << s.top() << std::endl;
    // 要素をスタックから削除
    s.pop();
    std::cout << "Top element after pop: " << s.top() << std::endl;
    return 0;
}

このコードでは、整数型のスタックを作成し、いくつかの要素を追加(push)し、トップ要素を表示(top)し、要素を削除(pop)しています。

実行結果は以下のようになります。

Top element: 3
Top element after pop: 2

このように、std::stackを使うことで、簡単にスタック操作を行うことができます。

std::stackの基本操作

std::stackのインクルードと宣言

std::stackを使用するためには、まずヘッダーファイルをインクルードする必要があります。

以下のように#include <stack>を記述します。

#include <stack>

次に、std::stackの宣言を行います。

std::stackはテンプレートクラスであり、スタックに格納する要素の型を指定する必要があります。

例えば、int型のスタックを宣言する場合は以下のように記述します。

std::stack<int> intStack;

要素の追加(push)

スタックに要素を追加するには、pushメソッドを使用します。

以下の例では、int型のスタックに要素を追加しています。

#include <iostream>
#include <stack>
int main() {
    std::stack<int> intStack;
    intStack.push(10);
    intStack.push(20);
    intStack.push(30);
    // スタックの内容を表示
    while (!intStack.empty()) {
        std::cout << intStack.top() << " ";
        intStack.pop();
    }
    return 0;
}

このコードを実行すると、スタックに追加された要素が逆順に表示されます。

30 20 10

要素の削除(pop)

スタックから要素を削除するには、popメソッドを使用します。

popメソッドはスタックの先頭要素を削除しますが、削除された要素の値は返しません。

以下の例では、スタックから要素を削除しています。

#include <iostream>
#include <stack>
int main() {
    std::stack<int> intStack;
    intStack.push(10);
    intStack.push(20);
    intStack.push(30);
    // 先頭要素を削除
    intStack.pop();
    // スタックの内容を表示
    while (!intStack.empty()) {
        std::cout << intStack.top() << " ";
        intStack.pop();
    }
    return 0;
}

このコードを実行すると、先頭要素が削除された後のスタックの内容が表示されます。

20 10

先頭要素の参照(top)

スタックの先頭要素を参照するには、topメソッドを使用します。

topメソッドはスタックの先頭要素を返しますが、スタックから削除はしません。

以下の例では、スタックの先頭要素を参照しています。

#include <iostream>
#include <stack>
int main() {
    std::stack<int> intStack;
    intStack.push(10);
    intStack.push(20);
    intStack.push(30);
    // 先頭要素を参照
    std::cout << "先頭要素: " << intStack.top() << std::endl;
    return 0;
}

このコードを実行すると、スタックの先頭要素が表示されます。

先頭要素: 30

スタックのサイズを取得(size)

スタックのサイズを取得するには、sizeメソッドを使用します。

sizeメソッドはスタックに格納されている要素の数を返します。

以下の例では、スタックのサイズを取得しています。

#include <iostream>
#include <stack>
int main() {
    std::stack<int> intStack;
    intStack.push(10);
    intStack.push(20);
    intStack.push(30);
    // スタックのサイズを取得
    std::cout << "スタックのサイズ: " << intStack.size() << std::endl;
    return 0;
}

このコードを実行すると、スタックのサイズが表示されます。

スタックのサイズ: 3

スタックが空かどうかの確認(empty)

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

emptyメソッドはスタックが空の場合にtrueを返し、そうでない場合はfalseを返します。

以下の例では、スタックが空かどうかを確認しています。

#include <iostream>
#include <stack>
int main() {
    std::stack<int> intStack;
    intStack.push(10);
    intStack.push(20);
    intStack.push(30);
    // スタックが空かどうかを確認
    if (intStack.empty()) {
        std::cout << "スタックは空です" << std::endl;
    } else {
        std::cout << "スタックには要素があります" << std::endl;
    }
    return 0;
}

このコードを実行すると、スタックが空かどうかの結果が表示されます。

スタックには要素があります

以上が、std::stackの基本操作に関する解説です。

これらの基本操作を理解することで、スタックを効果的に利用することができます。

std::stackの応用操作

スタックの初期化

std::stackの初期化は、他のSTLコンテナと同様に簡単に行えます。

以下の例では、整数型のスタックを初期化しています。

#include <iostream>
#include <stack>
int main() {
    std::stack<int> stack1; // 空のスタックを初期化
    std::stack<int> stack2({1, 2, 3, 4, 5}); // 初期値を持つスタックを初期化
    // スタックに要素を追加
    stack1.push(10);
    stack1.push(20);
    // スタックの内容を表示
    while (!stack1.empty()) {
        std::cout << stack1.top() << " ";
        stack1.pop();
    }
    return 0;
}

このコードでは、stack1は空のスタックとして初期化され、stack2は初期値を持つスタックとして初期化されています。

スタックのコピーと代入

std::stackはコピーコンストラクタと代入演算子をサポートしています。

これにより、スタックの内容を別のスタックにコピーすることができます。

#include <iostream>
#include <stack>
int main() {
    std::stack<int> stack1;
    stack1.push(10);
    stack1.push(20);
    // コピーコンストラクタを使用してスタックをコピー
    std::stack<int> stack2(stack1);
    // 代入演算子を使用してスタックをコピー
    std::stack<int> stack3;
    stack3 = stack1;
    // stack2の内容を表示
    while (!stack2.empty()) {
        std::cout << stack2.top() << " ";
        stack2.pop();
    }
    std::cout << std::endl;
    // stack3の内容を表示
    while (!stack3.empty()) {
        std::cout << stack3.top() << " ";
        stack3.pop();
    }
    return 0;
}

このコードでは、stack1の内容がstack2とstack3にコピーされています。

スタックのスワップ(swap)

std::stackはswapメソッドをサポートしており、2つのスタックの内容を効率的に交換することができます。

#include <iostream>
#include <stack>
int main() {
    std::stack<int> stack1;
    stack1.push(10);
    stack1.push(20);
    std::stack<int> stack2;
    stack2.push(30);
    stack2.push(40);
    // スタックの内容をスワップ
    stack1.swap(stack2);
    // stack1の内容を表示
    while (!stack1.empty()) {
        std::cout << stack1.top() << " ";
        stack1.pop();
    }
    std::cout << std::endl;
    // stack2の内容を表示
    while (!stack2.empty()) {
        std::cout << stack2.top() << " ";
        stack2.pop();
    }
    return 0;
}

このコードでは、stack1とstack2の内容がスワップされています。

スタックの比較(==, !=, <, <=, >, >=)

std::stackは比較演算子をサポートしており、スタック同士の内容を比較することができます。

#include <iostream>
#include <stack>
int main() {
    std::stack<int> stack1;
    stack1.push(10);
    stack1.push(20);
    std::stack<int> stack2;
    stack2.push(10);
    stack2.push(20);
    std::stack<int> stack3;
    stack3.push(30);
    stack3.push(40);
    // スタックの比較
    if (stack1 == stack2) {
        std::cout << "stack1 and stack2 are equal" << std::endl;
    } else {
        std::cout << "stack1 and stack2 are not equal" << std::endl;
    }
    if (stack1 != stack3) {
        std::cout << "stack1 and stack3 are not equal" << std::endl;
    }
    if (stack1 < stack3) {
        std::cout << "stack1 is less than stack3" << std::endl;
    }
    return 0;
}

このコードでは、stack1とstack2が等しいかどうか、stack1とstack3が等しくないかどうか、stack1がstack3より小さいかどうかを比較しています。

以上が、std::stackの応用操作に関する解説です。

これらの操作を理解することで、std::stackをより効果的に利用できるようになります。

std::stackの内部実装

デフォルトコンテナ(std::deque)

std::stackはデフォルトでstd::deque(デック)を内部コンテナとして使用します。

std::dequeは両端からの高速な挿入と削除が可能なコンテナで、スタックの操作に非常に適しています。

以下は、std::dequeを使用したstd::stackの例です。

#include <iostream>
#include <stack>
#include <deque>
int main() {
    std::stack<int, std::deque<int>> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    return 0;
}

このコードは、スタックに1, 2, 3を順に追加し、最後にそれらを取り出して表示します。

出力は以下のようになります。

3 2 1

std::vectorを使ったスタック

std::stackはstd::vectorを内部コンテナとして使用することもできます。

std::vectorは動的配列であり、末尾からの挿入と削除が高速です。

以下は、std::vectorを使用したstd::stackの例です。

#include <iostream>
#include <stack>
#include <vector>
int main() {
    std::stack<int, std::vector<int>> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    return 0;
}

このコードも同様に、スタックに1, 2, 3を順に追加し、最後にそれらを取り出して表示します。

出力は以下のようになります。

3 2 1

std::listを使ったスタック

std::stackはstd::listを内部コンテナとして使用することもできます。

std::listは双方向リストであり、任意の位置からの挿入と削除が高速です。

以下は、std::listを使用したstd::stackの例です。

#include <iostream>
#include <stack>
#include <list>
int main() {
    std::stack<int, std::list<int>> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    return 0;
}

このコードも同様に、スタックに1, 2, 3を順に追加し、最後にそれらを取り出して表示します。

出力は以下のようになります。

3 2 1

カスタムコンテナの使用

std::stackはカスタムコンテナを使用することもできます。

カスタムコンテナは、スタックの操作に必要なメソッド(push_back, pop_back, back, empty, size)を提供する必要があります。

以下は、カスタムコンテナを使用したstd::stackの例です。

#include <iostream>
#include <stack>
#include <deque>
template <typename T>
class CustomContainer {
public:
    void push_back(const T& value) {
        data.push_back(value);
    }
    void pop_back() {
        data.pop_back();
    }
    T& back() {
        return data.back();
    }
    const T& back() const {
        return data.back();
    }
    bool empty() const {
        return data.empty();
    }
    std::size_t size() const {
        return data.size();
    }
private:
    std::deque<T> data;
};
int main() {
    std::stack<int, CustomContainer<int>> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    return 0;
}

このコードも同様に、スタックに1, 2, 3を順に追加し、最後にそれらを取り出して表示します。

出力は以下のようになります。

3 2 1

このように、std::stackはデフォルトのstd::deque以外にも、std::vectorやstd::list、さらにはカスタムコンテナを使用することができます。

これにより、用途に応じた柔軟なスタックの実装が可能となります。

std::stackの実践例

ここでは、std::stackを使った具体的な例をいくつか紹介します。

これらの例を通じて、std::stackの実用的な使い方を理解しましょう。

数値の逆順表示

数値を逆順に表示するためには、std::stackが非常に便利です。

以下の例では、整数の配列をスタックにプッシュし、スタックからポップすることで逆順に表示します。

#include <iostream>
#include <stack>
#include <vector>
int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    std::stack<int> stack;
    // 数値をスタックにプッシュ
    for (int num : numbers) {
        stack.push(num);
    }
    // スタックからポップして逆順に表示
    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    return 0;
}

5 4 3 2 1

括弧のバランスチェック

括弧のバランスをチェックする問題は、スタックを使って簡単に解決できます。

以下の例では、与えられた文字列の括弧が正しく閉じているかどうかをチェックします。

#include <iostream>
#include <stack>
#include <string>
bool isBalanced(const std::string& str) {
    std::stack<char> stack;
    for (char ch : str) {
        if (ch == '(') {
            stack.push(ch);
        } else if (ch == ')') {
            if (stack.empty()) {
                return false;
            }
            stack.pop();
        }
    }
    return stack.empty();
}
int main() {
    std::string expression = "(1 + (2 * 3) + (4 / 2))";
    if (isBalanced(expression)) {
        std::cout << "括弧はバランスしています。" << std::endl;
    } else {
        std::cout << "括弧はバランスしていません。" << std::endl;
    }
    return 0;
}

括弧はバランスしています。

深さ優先探索(DFS)

深さ優先探索(DFS)は、グラフやツリーの探索アルゴリズムの一つです。

スタックを使って実装することができます。

以下の例では、グラフをDFSで探索します。

#include <iostream>
#include <stack>
#include <vector>
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]) {
            std::cout << node << " ";
            visited[node] = true;
            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, 5}, // 4
        {3, 4}     // 5
    };
    std::cout << "DFSの結果: ";
    DFS(0, graph);
    return 0;
}

DFSの結果: 0 2 4 5 3 1

関数呼び出しのシミュレーション

スタックは関数呼び出しのシミュレーションにも使えます。

以下の例では、再帰的な関数呼び出しをスタックを使ってシミュレートします。

#include <iostream>
#include <stack>
void simulateFunctionCalls(int n) {
    std::stack<int> stack;
    stack.push(n);
    while (!stack.empty()) {
        int current = stack.top();
        stack.pop();
        if (current <= 0) {
            std::cout << "Base case reached with " << current << std::endl;
        } else {
            std::cout << "Calling function with " << current - 1 << std::endl;
            stack.push(current - 1);
        }
    }
}
int main() {
    int n = 5;
    std::cout << "Simulating function calls with n = " << n << std::endl;
    simulateFunctionCalls(n);
    return 0;
}

Simulating function calls with n = 5
Calling function with 4
Calling function with 3
Calling function with 2
Calling function with 1
Calling function with 0
Base case reached with 0

これらの例を通じて、std::stackがどのように使われるかを理解できたでしょう。

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

std::stackの注意点とベストプラクティス

メモリ管理の注意点

std::stackは内部的にコンテナアダプタを使用しており、デフォルトではstd::dequeが使われます。

メモリ管理に関しては、以下の点に注意が必要です。

メモリの確保と解放:

std::stackは動的にメモリを確保します。

要素を追加するたびにメモリが確保され、要素を削除するたびにメモリが解放されます。

大量の要素を扱う場合、メモリの確保と解放が頻繁に行われるため、パフォーマンスに影響を与えることがあります。

メモリリークの防止:

std::stack自体はメモリリークを引き起こすことはありませんが、スタックに格納するオブジェクトが動的にメモリを確保している場合、そのオブジェクトのメモリ管理に注意が必要です。

特に、ポインタをスタックに格納する場合は、適切にメモリを解放するようにしましょう。

パフォーマンスの考慮

std::stackのパフォーマンスは、内部で使用するコンテナによって異なります。

デフォルトのstd::dequeは、要素の追加と削除が高速ですが、特定の用途に応じて他のコンテナを使用することも検討できます。

std::vector:

std::vectorを使用すると、メモリの再確保が発生することがありますが、連続したメモリ領域を使用するため、キャッシュ効率が良くなります。

大量の要素を扱う場合や、メモリの再確保が少ない場合に適しています。

std::list:

std::listは双方向リストであり、要素の追加と削除が一定時間で行えます。

ただし、メモリのオーバーヘッドが大きく、キャッシュ効率が悪いため、特定の用途に限られます。

スタックオーバーフローの回避

スタックオーバーフローは、スタックに過剰な量のデータを追加することで発生します。

特に再帰的な関数呼び出しでスタックを使用する場合、スタックオーバーフローに注意が必要です。

再帰の深さを制限する:

再帰的なアルゴリズムを使用する場合、再帰の深さを制限することでスタックオーバーフローを防ぐことができます。

必要に応じて、再帰をループに置き換えることも検討しましょう。

スタックのサイズを監視する:

スタックのサイズを定期的に監視し、一定のサイズを超えた場合に警告を出すようにすることで、スタックオーバーフローを未然に防ぐことができます。

適切なコンテナの選択

std::stackは内部で使用するコンテナをカスタマイズできます。

用途に応じて適切なコンテナを選択することが重要です。

std::deque:

デフォルトのコンテナであり、要素の追加と削除が高速です。

一般的な用途に適しています。

std::vector:

メモリの再確保が発生することがありますが、連続したメモリ領域を使用するため、キャッシュ効率が良くなります。

大量の要素を扱う場合に適しています。

std::list:

双方向リストであり、要素の追加と削除が一定時間で行えます。

特定の用途に限られますが、特定のシナリオでは有効です。

以下に、std::stackでstd::vectorを使用する例を示します。

#include <iostream>
#include <stack>
#include <vector>
int main() {
    // std::vectorを使用したstd::stackの宣言
    std::stack<int, std::vector<int>> stack;
    // 要素の追加
    stack.push(1);
    stack.push(2);
    stack.push(3);
    // 先頭要素の参照と削除
    while (!stack.empty()) {
        std::cout << stack.top() << std::endl; // 3, 2, 1の順に出力
        stack.pop();
    }
    return 0;
}

このように、用途に応じて適切なコンテナを選択することで、std::stackのパフォーマンスを最適化することができます。

まとめ

この記事では、C++の標準ライブラリに含まれるstd::stackについて詳しく解説しました。

基本操作から応用操作、内部実装、実践例、注意点まで幅広く理解することで、より効率的で効果的なプログラムを作成できるようになります。

この記事が、std::stackの理解と活用に役立つことを願っています。

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

std::stackとは

std::stackの概要

スタックの基本的な概念

std::stackの用途と利点

std::stackの基本操作

std::stackのインクルードと宣言

要素の追加(push)

要素の削除(pop)

先頭要素の参照(top)

スタックのサイズを取得(size)

スタックが空かどうかの確認(empty)

std::stackの応用操作

スタックの初期化

スタックのコピーと代入

スタックのスワップ(swap)

スタックの比較(==, !=, <, <=, >, >=)

std::stackの内部実装

デフォルトコンテナ(std::deque)

std::vectorを使ったスタック

std::listを使ったスタック

カスタムコンテナの使用

std::stackの実践例

数値の逆順表示

括弧のバランスチェック

深さ優先探索(DFS)

関数呼び出しのシミュレーション

std::stackの注意点とベストプラクティス

メモリ管理の注意点

パフォーマンスの考慮

スタックオーバーフローの回避

適切なコンテナの選択

まとめ

キーワードから探す

関連記事