C++で連結リスト（リンクリスト）を使ってスタックを実装する方法【サンプルコード付き解説】

スタック（Stack）は、要素の集合を管理するための抽象データ構造の一つです。スタックはLIFO（Last In First Out：後入れ先出し）という仕組みに基づいて動作し、最後に追加した要素が最初に取り出されます。スタックにおける主な操作は以下の通りです。

• Push（プッシュ）：スタックの先頭にデータ値を追加します。
• Pop（ポップ）：スタックの先頭にあるデータ値を削除します。
• Peek（ピーク）：スタックの先頭にあるデータ値を参照します（削除は行いません）。

本記事では、連結リスト（リンクリスト）を使用してスタックを実装するC++プログラムを紹介し、その動作の仕組みを詳しく解説します。

連結リストによるスタックの実装例（C++）

#include <iostream>
using namespace std;
struct Node {
    int data;
    struct Node *next;
};
struct Node* top = NULL;
void push(int val) {
    struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
    newnode->data = val;
    newnode->next = top;
    top = newnode;
}
void pop() {
    if(top==NULL)
        cout<<"Stack Underflow"<<endl;
    else {
        cout<<"The popped element is "<< top->data <<endl;
        top = top->next;
    }
}
void display() {
    struct Node* ptr;
    if(top==NULL)
        cout<<"stack is empty";
    else {
        ptr = top;
        cout<<"Stack elements are: ";
        while (ptr != NULL) {
            cout<< ptr->data <<" ";
            ptr = ptr->next;
        }
    }
    cout<<endl;
}
int main() {
    int ch, val;
    cout<<"1) Push in stack"<<endl;
    cout<<"2) Pop from stack"<<endl;
    cout<<"3) Display stack"<<endl;
    cout<<"4) Exit"<<endl;
    do {
        cout<<"Enter choice: "<<endl;
        cin>>ch;
        switch(ch) {
            case 1: {
                cout<<"Enter value to be pushed:"<<endl;
                cin>>val;
                push(val);
                break;
            }
            case 2: {
                pop();
                break;
            }
            case 3: {
                display();
                break;
            }
            case 4: {
                cout<<"Exit"<<endl;
                break;
            }
            default: {
                cout<<"Invalid Choice"<<endl;
            }
        }
    }while(ch!=4);
    return 0;
}

実行結果

1) Push in stack
2) Pop from stack
3) Display stack
4) Exit

Enter choice: 1
Enter value to be pushed: 2
Enter choice: 1
Enter value to be pushed: 6
Enter choice: 1
Enter value to be pushed: 8
Enter choice: 1
Enter value to be pushed: 7
Enter choice: 2
The popped element is 7
Enter choice: 3
Stack elements are:8 6 2
Enter choice: 5
Invalid Choice
Enter choice: 4
Exit

プログラムの解説

① ノード構造体の定義

このプログラムでは、Node構造体を使って連結リストを構築し、それをスタックとして実装しています。各ノードは整数型のdataと、次のノードを指すポインタnextを持っています。

struct Node {
    int data;
    struct Node *next;
};

② push()関数 ― データの追加

push()関数は、引数valとして受け取った値をスタックに挿入します。まずmalloc()で新しいノードを確保し、そのdata部分にvalを代入します。続いて、新しいノードのnextに現在のtopを設定してリストの先頭に連結し、topを新しいノードへ更新します。これにより、常に最新の要素がスタックの先頭に置かれます。

void push(int val) {
    struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
    newnode->data = val;
    newnode->next = top;
    top = newnode;
}

③ pop()関数 ― データの削除

pop()関数は、スタックに値が存在すればその最上位（先頭）の値を取り出して表示します。スタックが空の場合（topがNULLの場合）は「Stack Underflow」と表示され、アンダーフローであることを通知します。

void pop() {
    if(top==NULL)
        cout<<"Stack Underflow"<<endl;
    else {
        cout<<"The popped element is "<< top->data <<endl;
        top = top->next;
    }
}

④ display()関数 ― スタック内容の表示

display()関数は、スタック内のすべての要素を表示します。まずptrをtopにセットし、ptrがNULLになるまで（リストの末尾まで）順にたどりながら、各ノードのdataの値を出力します。スタックが空の場合は「stack is empty」と表示されます。

void display() {
    struct Node* ptr;
    if(top==NULL)
        cout<<"stack is empty";
    else {
        ptr = top;
        cout<<"Stack elements are: ";
        while (ptr != NULL) {
            cout<< ptr->data <<" ";
            ptr = ptr->next;
        }
    }
    cout<<endl;
}

⑤ main()関数 ― メニュー操作

main()関数では、ユーザーに「Push（追加）」「Pop（削除）」「Display（表示）」「終了」のいずれかを選択させるメニューを提供します。入力された選択肢に応じてswitch文で対応する関数を呼び出し、1〜4以外の値が入力された場合は「Invalid Choice」と表示します。do-whileループにより、ユーザーが4（終了）を選ぶまで処理が繰り返されます。main()関数の完全なコードは、冒頭の実装例を参照してください。

まとめ

連結リストを用いたスタック実装では、push・popともに先頭ノードだけを操作するため、どちらもO(1)の計算量で実行できるのが大きな特徴です。また、配列を使う実装と異なり、あらかじめ最大サイズを決めておく必要がない点もメリットといえます。一方で、C++ではmalloc()の代わりにnew演算子やスマートポインタを利用することで、より安全なメモリ管理が可能になります。なお、実務開発では標準ライブラリのstd::stackを使えば同様の機能を簡単に実現できるため、学習目的以外ではそちらの活用も検討するとよいでしょう。