スタック Stack

スタックは一時的にデータを退避したいときに有効なデータ構造で、データの中で最後に 入ったものが最初に取り出される後入れ先出し（LIFO: Last In First Out）のルールに従いデー タを管理します。例えば、以下の何気ない日常の行動が、スタックのデータ構造をうまく表 現してくれます。

テストの勉強中で以下のような一連の行動をとった場面があるかもしれません。

• １. 英語の教科書を読む
• ２. 分からない単語があったので、辞書を引く
• ３. 辞書を引いている途中で、友達からメールがｷﾀのでメールを書く
• ４. メールの返信が終わったので、辞書を引きなおす
• ５. 単語を理解したので、教科書の続きを読む
• ６. 教科書を読み終える

この行動の流れをスタックで表わすと以下のようになります：



積み木のように「行動」が順番に重なっていきます。積み木の最上部が進行中の行動で、そ の下にあるもの全てが中断されている行動になります。この例での重要なポイントは、例え ばステップ4 でメールを返信した後に教科書を読むのではなく、メールの対応によって中 断されていた「辞書を引く」ことに戻るということです。

このように、コンピュータにおいても処理していたことを一時的に退避させ、適時それを取 り出して正しい順番で続行しなければならない場面は多くあります。この例では、もし順番 が乱れて単語の意味を理解しないまま教科書を読もうとしてもつまづいてしまいます。この ような行動をコンピュータにおけるデータや処理と置き換えたものが、スタックのデータ構 造です。

スタックの操作

• push(x): スタックの先頭（頂点）に要素 x を追加します。
• pop(): スタックの先頭（頂点）から要素を取り出します。
• isEmpty(): スタックが空かどうかを調べます。
• isFull(): スタックが満杯かどうかを調べます。

スタックの制約

• データの中で最後に入ったものが最初に取り出されます。

スタックやその他のデータ構造の実装には配列やリストを使ったものなどいくつかの方法があります。ここでは、データ構造の操作と制約の理解に重点をおきますので、簡単な例を通して１つの実装方法を示します。整数型のデータが格納されるスタックを配列を用いて実装します。以下に、実装に必要なものを示します(下図参照)。

データを格納するための整数型1次元配列： buffer
配列bufferの各要素にプッシュされたデータを格納していきます。問題に応じた十分な記憶領域を確保することが必要です。また、便宜上 0 番目には常に何も入れないようにします。Fig. 4.2-2は、容量が7のスタックに既に5つの要素が格納されている様子を表しています。


スタックポインタである整数型変数： top
スタックの頂点の要素（一番最後に追加された要素）を指し示す整数型の変数です。この変数をスタックポインタといいます。またtop の値はスタックの要素数をも示します。

実際にスタックのデータ構造を操作する様子を見てみましょう。Fig. 4.2-3は、実際にスタックに適当な値を適当に出し入れしている様子を示しています。データ構造の操作は動的に発生するものなので、スタックの要素は変動していきます。

初期化: top = 0としてスタックを空にします。 push(x): top を1増やし、topが指す場所にxを追加します （例: x = 3 ）。 push(x): top を1増やし、topが指す場所にxを追加します （例: x = 12 ）。 push(x): top を1増やし、topが指す場所にxを追加します （例: x = 1 ）。 pop: topが指している要素を取り出し、topを1減らします （例: 1を取り出す）。 pop: topが指している要素を取り出し、topを1減らします （例: 12を取り出す）。 push(x): top を1増やし、topが指す場所にxを追加します （例: x = 5 ）

以下のプログラムは配列によってスタックを実現し、スタックへのデータの追加・取り出しをシミュレーションします。プログラムは、”push x” （xは整数）とキーボードから入力されると、スタックにxを追加し、”pop” と入力されると、スタックの頂点の要素を取り出しそれを出力します。これら以外の形式が入力されたときプログラムが終了します。
スタックのデータ構造はクラスとして実装されています。クラスとしてデータ構造を実装しておけば、それらを部品として使えるので、プログラムで複数の異なるスタックを使いたい場合などに便利になります。

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

#define MAX 5

class Stack{
    private:
    int buffer[MAX];
    int top;

    public:
    Stack(){
        initialize();
    }

    void initialize(){
        top = 0;
    }

    bool isEmpty(){
        return ( top == 0 );
    }

    bool isFull(){
        return  ( top >= MAX );
    }

    void push( int x ){
        if ( isFull() ){
            cout << "overflow" << endl;
        } else {
            top++;
            buffer[top] = x;
        }
    }

    int pop(){
        if ( isEmpty() ) {
            cout << "underflow" << endl;
        } else {
            int x = buffer[top];
            top--;
            return x;
        }
    }
};

int main(void){
    Stack stack;
    int x;
    string command;

    while (1){
        cin >> command;
        if ( command == "push" ) {
            cin >> x;
            stack.push(x);
        } else if ( command == "pop" ){
            cout << stack.pop() << endl;
        } else break;
    }

    return 0;
}

main 関数
スタックのオブジェクト（※ 1）stack を操作します。無限ループによってキーボードから コマンドcommand の入力を待ち続けます。command がpush であればx を読み込みそれ をstack に追加します。command がpop であればstack からデータを取り出し、それを出 力します。それ以外のcommand が入力されたときループから抜けプログラムが終了します。

initialize
stack を空にします。stack が空のときはtop が0 を指します。

isEmpty
stack が空の場合真を返します。top が0 のときstack が空の状態になります。

isFull
stack が満杯の場合真を返します。プログラムではbuffer の容量がMAX で定義されています。 top がMAX 以上のときにstack が満杯の状態になります。

push(x)
stack が満杯の場合は”overflow” と出力します。そうでなければ、top を1 つ増やし、その 場所にx を追加します。

pop
stack が空の場合は”underflow” と出力します。そうでなければ、stack の頂点の要素を変数 x に一時記録し、top を1 減らしてからx を返します。



普通は、以下のように便利なライブラリを使います。

#include<stack>

using namespace std;

main(){
    stack<int> st;
    st.push(1);
    st.push(7);
    st.push(3);
    cout << st.top() << endl; st.pop();
    cout << st.top() << endl; st.pop();
    st.push(5);
    cout << st.top() << endl; st.pop();
    cout << st.top() << endl; st.pop();
}

練習問題１

see-try-see