C++のSTLでスタックを実装するサンプルプログラム【初心者向け解説】

スタック(Stack)は、操作を行う順序があらかじめ決まっている線形データ構造です。この順序は「LIFO(Last In First Out:後入れ先出し)」または「FILO(First In Last Out:先入れ後出し)」と呼ばれ、最後に追加した要素が最初に取り出されるという特徴を持ちます。本記事では、C++の標準テンプレートライブラリ(STL)に含まれる stack を使って、スタックの基本操作を実装するサンプルプログラムを紹介します。

アルゴリズム

このプログラムでは、STLのstackオブジェクトを宣言し、ユーザーが選択した番号に応じてswitch文で各操作を呼び出します。使用する主なメンバ関数は以下の通りです。

• s.size():スタックのサイズ(現在の要素数)を返します。
• s.push():スタックの末尾に要素を挿入します。
• s.pop():スタックの最上位(最後に挿入された)要素を取り除きます。
• s.top():スタックの最上位要素への参照を返します。

サンプルコード

以下は、メニュー形式でスタック操作を試せるC++プログラムです。なお、元のコードでは空チェックの前にtop()を呼び出していましたが、空のスタックに対するtop()やpop()は未定義動作となるため、ここではempty()による空チェックを先に行うよう修正しています。

#include <iostream>
#include <stack>
#include <string>
#include <cstdlib>
using namespace std;

int main() {
    stack<int> s;   // int型のスタックを宣言
    int c, i;
    while (1) {
        cout<<"1.Size of the Stack"<<endl;
        cout<<"2.Insert Element into the Stack"<<endl;
        cout<<"3.Delete Element from the Stack"<<endl;
        cout<<"4.Top Element of the Stack"<<endl;
        cout<<"5.Exit"<<endl;
        cout<<"Enter your Choice: ";
        cin>>c;
        switch (c) {
            case 1:
                cout<<"Size of the stack: ";
                cout<<s.size()<<endl;
                break;
            case 2:
                cout<<"Enter value to be inserted: ";
                cin>>i;
                s.push(i);              // 要素を挿入
                break;
            case 3:
                if (!s.empty()) {       // 空チェックを先に行う
                    i = s.top();
                    s.pop();            // 最上位の要素を削除
                    cout<<i<<" Deleted"<<endl;
                } else {
                    cout<<"Stack is Empty"<<endl;
                }
                break;
            case 4:
                cout<<"Top Element of the Stack: ";
                cout<<s.top()<<endl;    // 最上位の要素を表示
                break;
            case 5:
                exit(1);                // プログラムを終了
            default:
                cout<<"Wrong Choice"<<endl;
        }
    }
    return 0;
}

実行結果

(メニュー部分は操作のたびに繰り返し表示されるため、以下では省略しています)

Enter your Choice: 1
Size of the stack: 0

Enter your Choice: 2
Enter value to be inserted: 1

Enter your Choice: 2
Enter value to be inserted: 7

Enter your Choice: 2
Enter value to be inserted: 6

Enter your Choice: 2
Enter value to be inserted: 10

Enter your Choice: 2
Enter value to be inserted: 4

Enter your Choice: 1
Size of the stack: 5

Enter your Choice: 3
4 Deleted

Enter your Choice: 4
Top Element of the Stack: 10

Enter your Choice: 5

Exit code: 1

実行例を見てみましょう。最初にサイズを確認すると「0」です。続いて1→7→6→10→4の順に5つの要素を挿入すると、サイズは「5」と表示されます。次に削除操作を選ぶと、最後に挿入した「4」が取り除かれ(4 Deleted)、その直後にトップ要素を参照すると「10」が返ります。これは、最後に入れた要素が最初に出てくるというスタックのLIFO特性そのものです。

コードのポイント

• stack<int> s;:STLのstackはクラステンプレートであり、デフォルトではdequeを内部コンテナとして利用します。
• s.empty():スタックが空の場合にtrueを返します。空のスタックに対してtop()やpop()を呼び出すと未定義動作になるため、操作前に必ずチェックしましょう。
• exit(1):<cstdlib>ヘッダで提供される関数で、プログラムを即座に終了させます。

このように、STLのstackを使えば、わずかなコード量で安全かつ効率的なスタックを実装できます。競技プログラミングや実務でのデータ管理など幅広い場面で活用できる基本テクニックなので、ぜひ実際に手を動かして動作を確かめてみてください。