プログラミングのスタックとは？意味をわかりやすく解説

公開：2024年8月23日更新：2024年8月23日

スタックとは
スタックの実装と活用方法
配列を使用したスタックの実装
連結リストによるスタック構築
スタックを活用した括弧の対応チェック

スタックとは

スタックとはデータを積み重ねるように扱うデータ構造です。新しいデータは一番上に追加され、取り出すときは最後に追加したものから順に取り出すのが特徴。これを「後入れ先出し（LIFO: Last-In-First-Out）」といいます。プログラミングにおいてスタックは関数の呼び出しや、計算の順番を管理するために使われています。

スタックの主な操作は、プッシュ（push）とポップ（pop）の2つです。プッシュはスタックの一番上にデータを追加する操作で、ポップはスタックの一番上からデータを取り出す操作です。これらの操作により、データの追加と削除を効率的に行えるのがスタックの特徴だと言えます。

スタックはブラウザの履歴管理やテキストエディタの元に戻す機能など、さまざまなアプリケーションで利用されています。また、深さ優先探索（DFS）アルゴリズムの実装にも用いられることがあります。スタックの概念を理解することはプログラミングの基礎力を高める上で、非常に重要なポイントとなっています。

Python基礎・実践(Django)

企業・法人向けのPython研修では、基礎から応用まで体系的に学べます。

Python研修の詳細

DX社員研修

企業・法人向けのDX研修では、実務に繋がるリスキリングでITレベルを向上させます。

DX研修の詳細

Javaエンジニア育成研修

企業・法人向けのJavaエンジニア育成研修では、Javaの基礎から応用まで確実に習得できます。

Java研修の詳細

新卒・新入社員向け研修

企業・法人に新入社員・新卒社員に向けたプログラミング研修を提供しています。

新入社員研修の詳細

コードキャンプのIT研修を全て見る

スタックの実装と活用方法

スタックの実装と活用方法に関して、以下3つを簡単に解説します。

配列を使用したスタックの実装
連結リストによるスタック構築
スタックを活用した括弧の対応チェック

配列を使用したスタックの実装

配列を用いたスタックの実装は最も一般的で直感的な方法のひとつです。配列の末尾をスタックの先頭とみなし、要素の追加（プッシュ）と削除（ポップ）を行います。この方法はメモリ使用効率が良く、ランダムアクセスが可能だというメリットがあります。

class Stack {
    private:
        vector data;
    public:
        void push(int value) {
            data.push_back(value);
        }
        int pop() {
            if (isEmpty()) throw runtime_error("Stack is empty");
            int top = data.back();
            data.pop_back();
            return top;
        }
        bool isEmpty() {
            return data.empty();
        }
};

上記のコードはC++を使用して配列（ベクター）ベースのスタックを実装した例です。「push」メソッドでは要素を追加し、「pop」メソッドでは最後に追加された要素を取り出して削除しています。このような実装により効率的なスタック操作が可能になります。

配列を使用したスタックの実装は、固定サイズのメモリ割り当てが可能な場合に有効です。また、要素数が予測可能な場合や頻繁なリサイズが必要ない場合にも適しています。しかし大量のデータを扱う場合は、メモリ管理に注意が必要となるでしょう。

おすすめのPython研修一覧

Python研修を提供しているおすすめの企業・法人を一覧で掲載しております。

Python研修の一覧を見る

おすすめのDX研修一覧

DX研修を提供しているおすすめの企業・法人を一覧で掲載しております。

DX研修の一覧を見る

おすすめのJava研修一覧

Java研修を提供しているおすすめの企業・法人を一覧で掲載しております。

Java研修の一覧を見る

おすすめのJavaScript研修一覧

JavaScript研修を提供しているおすすめの企業・法人を一覧で掲載しております。

JavaScript研修の一覧を見る

連結リストによるスタック構築

連結リストを用いたスタックの実装は動的なメモリ割り当てが可能であり、サイズの制限がないというメリットがあります。各ノードが次のノードへのポインタを持つ構造で、新しい要素の追加や削除が容易に行えます。この方法は要素数が予測不可能な場合にぴったりです。

class Node {
public:
    int data;
    Node* next;
    Node(int value) : data(value), next(nullptr) {}
};

class Stack {
private:
    Node* top;
public:
    Stack() : top(nullptr) {}
    void push(int value) {
        Node* newNode = new Node(value);
        newNode->next = top;
        top = newNode;
    }
    int pop() {
        if (isEmpty()) throw runtime_error("Stack is empty");
        int value = top->data;
        Node* temp = top;
        top = top->next;
        delete temp;
        return value;
    }
    bool isEmpty() {
        return top == nullptr;
    }
};

このコードはC++で連結リストを使用してスタックを実装した例です。新しい要素をプッシュする際は、新しいノードを作成してリストの先頭に追加します。ポップ操作では先頭ノードのデータを取り出し、そのノードを削除しています。

連結リストによるスタックの実装はメモリの動的割り当てが可能なため、柔軟性が高いというのが特徴。ただしポインタの操作が必要となるため、配列ベースの実装と比べてやや複雑になる傾向があります。

スタックを活用した括弧の対応チェック

スタックは括弧の対応をチェックする問題を解決するのに最適です。文字列内の開き括弧をスタックにプッシュし、閉じ括弧が現れたらスタックからポップして対応を確認します。この方法によりネストされた括弧も正確にチェックできます。

bool isValidParentheses(string s) {
    stack st;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            if (c == ')' && st.top() != '(') return false;
            if (c == '}' && st.top() != '{') return false;
            if (c == ']' && st.top() != '[') return false;
            st.pop();
        }
    }
    return st.empty();
}

上記のコードはC++を使用して、括弧の対応をチェックする関数を実装しています。開き括弧はスタックにプッシュし、閉じ括弧が現れた時にスタックの先頭と比較しています。この方法により複雑な入れ子構造の括弧も正確にチェックすることが可能です。

スタックを活用した括弧のチェックは、プログラミング言語の構文解析やXMLドキュメントの検証などさまざまな場面で応用されています。この手法は時間複雑度O(n)で効率的に処理でき、大規模なデータセットに対しても高速に動作するという利点があります。

※上記コンテンツの内容やソースコードはAIで確認・デバッグしておりますが、間違いやエラー、脆弱性などがある場合は、コメントよりご報告いただけますと幸いです。