[C++] stackから値を取得する方法

Q: スタックとキューの違いは何ですか？

スタックとキューは、どちらもデータを格納するためのデータ構造ですが、データの取り出し方に違いがあります。 スタック : LIFO(Last In, First Out)構造です。 最後に追加された要素が最初に取り出されます。 例として、皿を積み重ねるようなイメージです。 キュー : FIFO(First In, First Out)構造です。 最初に追加された要素が最初に取り出されます。 例として、列に並ぶようなイメージです。

Q: std::stackはスレッドセーフですか？

std::stackはスレッドセーフではありません。 複数のスレッドから同時にアクセスする場合、データ競合が発生する可能性があります。 スレッドセーフにするためには、std::mutexなどの同期機構を使用して、スタックへのアクセスを保護する必要があります。 例：std::mutex mtx; mtx.lock(); stack.push(1); mtx.unlock();

Q: スタックのサイズを動的に変更できますか？

std::stack自体はサイズを動的に変更するメソッドを提供していませんが、内部で使用するコンテナ(通常はstd::dequeやstd::vector)が動的にサイズを変更します。 要素をプッシュすることでスタックのサイズは増加し、ポップすることで減少します。 メモリが許す限り、スタックのサイズは動的に変更されます。

2024-08-202024-08-26

C++でスタックから値を取得するには、標準ライブラリのstd::stackを使用します。

スタックはLIFO（Last In, First Out）構造を持ち、最後に追加された要素が最初に取り出されます。

値を取得するには、top()メソッドを使用します。このメソッドはスタックの最上位の要素を返しますが、スタックからは削除しません。

要素を削除するにはpop()メソッドを使用します。

スタックが空でないか確認するためにはempty()メソッドを使用します。

この記事でわかること

top()、pop()、empty()メソッドを使ったスタックの基本操作
スタックのオーバーフローやアンダーフローに関する注意点
スタックを用いた関数呼び出しの管理方法
逆ポーランド記法を用いた数式の評価方法
深さ優先探索(DFS)におけるスタックの利用方法

目次から探す

スタックから値を取得する方法

C++の標準ライブラリには、LIFO(Last In, First Out)構造を持つデータ構造であるスタックが用意されています。

スタックから値を取得するための基本的なメソッドについて解説します。

top()メソッドの使い方

top()メソッドは、スタックの最上部にある要素を参照します。

このメソッドは、スタックが空でないことを前提に使用されます。

#include <iostream>
#include <stack>
int main() {
    std::stack<int> numbers;
    numbers.push(10);
    numbers.push(20);
    numbers.push(30);
    // スタックの最上部の要素を取得
    int topValue = numbers.top();
    std::cout << "スタックの最上部の値: " << topValue << std::endl;
    return 0;
}

スタックの最上部の値: 30

この例では、スタックに3つの整数をプッシュし、top()メソッドを使って最上部の値を取得しています。

スタックの最上部の値は30です。

pop()メソッドでの値の削除

pop()メソッドは、スタックの最上部にある要素を削除します。

このメソッドは、削除するだけで値を返しません。

削除する前にtop()メソッドで値を取得することが一般的です。

#include <iostream>
#include <stack>
int main() {
    std::stack<int> numbers;
    numbers.push(10);
    numbers.push(20);
    numbers.push(30);
    // スタックの最上部の要素を削除
    numbers.pop();
    // 削除後の最上部の要素を取得
    int topValue = numbers.top();
    std::cout << "削除後のスタックの最上部の値: " << topValue << std::endl;
    return 0;
}

削除後のスタックの最上部の値: 20

この例では、pop()メソッドを使って最上部の要素を削除した後、top()メソッドで新しい最上部の値を取得しています。

削除後の最上部の値は20です。

empty()メソッドでのスタックの確認

empty()メソッドは、スタックが空であるかどうかを確認するために使用されます。

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

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

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

この例では、最初にスタックが空であることを確認し、要素を追加した後に再度確認しています。

最初は空で、要素を追加した後は空ではなくなります。

スタックの操作における注意点

スタックを使用する際には、いくつかの注意点があります。

これらの注意点を理解しておくことで、プログラムの信頼性と効率性を向上させることができます。

スタックのオーバーフローとアンダーフロー

スタックのオーバーフローは、スタックが許容する最大容量を超えて要素をプッシュしようとしたときに発生します。

C++の標準ライブラリのstd::stackは、内部的にstd::dequeやstd::vectorを使用しているため、メモリが許す限りオーバーフローは発生しませんが、メモリ不足による例外が発生する可能性があります。

一方、スタックのアンダーフローは、空のスタックから要素をポップしようとしたときに発生します。

std::stackでは、アンダーフローを防ぐためにempty()メソッドを使用して、スタックが空でないことを確認してからpop()やtop()を呼び出すことが推奨されます。

スタックのサイズ制限

std::stack自体にはサイズ制限はありませんが、使用するコンテナstd::dequeやstd::vectorのサイズに依存します。

メモリの制約により、スタックのサイズが制限されることがあります。

特に、再帰的な関数呼び出しでスタックを使用する場合、スタックサイズが大きくなりすぎないように注意が必要です。

以下は、スタックのサイズを確認する例です。

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

スタックのサイズ: 3

この例では、スタックに3つの要素をプッシュし、size()メソッドを使ってスタックのサイズを確認しています。

スタックの例外処理

スタック操作中に発生する可能性のある例外を適切に処理することは重要です。

特に、メモリ不足による例外や、空のスタックに対する操作による例外を考慮する必要があります。

例外処理を行う際には、tryブロックとcatchブロックを使用して、例外が発生した場合の処理を記述します。

以下は、スタック操作中の例外処理の例です。

#include <iostream>
#include <stack>
#include <stdexcept>
int main() {
    std::stack<int> numbers;
    try {
        // 空のスタックから要素を取得しようとする
        int topValue = numbers.top();
    } catch (const std::exception& e) {
        std::cerr << "例外が発生しました: " << e.what() << std::endl;
    }
    return 0;
}

例外が発生しました: スタックが空です

この例では、空のスタックからtop()を呼び出そうとした際に例外が発生し、それをキャッチしてエラーメッセージを表示しています。

例外処理を適切に行うことで、プログラムの安定性を向上させることができます。

スタックの応用例

スタックは、その特性を活かしてさまざまな場面で応用されています。

ここでは、スタックの代表的な応用例をいくつか紹介します。

関数呼び出しの管理

プログラムの実行中、関数呼び出しはスタックを使って管理されます。

関数が呼び出されるたびに、関数の戻り先アドレスやローカル変数がスタックにプッシュされ、関数が終了するとポップされます。

この仕組みにより、再帰的な関数呼び出しも適切に処理されます。

以下は、再帰的な関数呼び出しの例です。

#include <iostream>
// 再帰的に階乗を計算する関数
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}
int main() {
    int number = 5;
    std::cout << number << "の階乗は: " << factorial(number) << std::endl;
    return 0;
}

5の階乗は: 120

この例では、factorial関数が再帰的に呼び出され、スタックを使って呼び出しの管理が行われています。

数式の評価

スタックは、数式の評価にも利用されます。

特に、逆ポーランド記法(RPN)で表現された数式の評価において、スタックは非常に便利です。

RPNでは、演算子がオペランドの後に来るため、スタックを使ってオペランドを管理し、演算子が現れたときに計算を行います。

以下は、RPNを使った数式の評価の例です。

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
// 逆ポーランド記法の数式を評価する関数
int evaluateRPN(const std::string& expression) {
    std::stack<int> stack;
    std::istringstream tokens(expression);
    std::string token;
    while (tokens >> token) {
        if (isdigit(token[0])) {
            stack.push(std::stoi(token));
        } else {
            int b = stack.top(); stack.pop();
            int a = stack.top(); stack.pop();
            if (token == "+") stack.push(a + b);
            else if (token == "-") stack.push(a - b);
            else if (token == "*") stack.push(a * b);
            else if (token == "/") stack.push(a / b);
        }
    }
    return stack.top();
}
int main() {
    std::string expression = "3 4 + 2 * 7 /";
    std::cout << "数式の評価結果: " << evaluateRPN(expression) << std::endl;
    return 0;
}

数式の評価結果: 2

この例では、RPNで表現された数式をスタックを使って評価しています。

深さ優先探索(DFS)

深さ優先探索(DFS)は、グラフやツリーの探索アルゴリズムの一つで、スタックを使って実装されます。

DFSでは、訪問したノードをスタックにプッシュし、次に訪問するノードをスタックからポップして探索を続けます。

以下は、DFSを使ったグラフ探索の例です。

#include <iostream>
#include <vector>
#include <stack>
// グラフを表現するクラス
class Graph {
public:
    Graph(int vertices) : adjList(vertices) {}
    void addEdge(int v, int w) {
        adjList[v].push_back(w);
    }
    void DFS(int start) {
        std::vector<bool> visited(adjList.size(), false);
        std::stack<int> stack;
        stack.push(start);
        while (!stack.empty()) {
            int v = stack.top();
            stack.pop();
            if (!visited[v]) {
                std::cout << v << " ";
                visited[v] = true;
            }
            for (int w : adjList[v]) {
                if (!visited[w]) {
                    stack.push(w);
                }
            }
        }
    }
private:
    std::vector<std::vector<int>> adjList;
};
int main() {
    Graph graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    std::cout << "DFSの訪問順序: ";
    graph.DFS(0);
    std::cout << std::endl;
    return 0;
}