ALDS1_3_A:

スタック

逆ポーランド記法で記述された数式は、スタックを用いて計算を行うことができます。式を評価するには、下図のように数式の先頭からひとつずつ順番に文字列を読み込み、文字列がオペランド（数字）であればスタックに値を積み、演算子（+, -, *）であればスタックから値を2つ取り出して演算結果をスタックに積む、という操作を繰り返します。最 後にスタックの中に残った値が答えとなります。

スタックの操作と制約

• push(x): スタックの先頭（頂点）に要素 x を追加します。
• pop( ): スタックの先頭（頂点）から要素を取り出します。
• isEmpty( ): スタックが空かどうかを調べます。
• isFull( ): スタックが満杯かどうかを調べます。
  ※これらの他にも、スタックの先頭の要素を参照したり、スタックの中に指定されたデータが含まれているかを調べたりする操作も含みます。

データの中で最後に入ったものが最初に取り出されます。pop( ) によって取り出される要素は、最後に push された要素です（push されてからの時間が最も短い要素）。

スタックの実装

スタックやその他のデータ構造の実装には配列やリストを使ったものなどいくつかの方法があります。ここでは、データ構造の操作と制約の理解に焦点をおき、整数型のデータが格納されるスタックを配列を用いて実装します。

スタックの実装に必要な主な変数と関数は以下のとおりです。

データを格納するための整数型 1 次元配列： S
配列 S の各要素に push されたデータを格納していきます。問題に応じた十分な記憶領域を確保することが必要です。また、ここで紹介する実装ではS[0]には常に何も入れないようにします。図では、容量が5のスタックに既に3つの要素が格納されている様子を表しています。

スタックポインタを表す整数型変数： top
スタックの頂点（トップ）の要素（一番最後に追加された要素）を指し示す整数型の変数です。top は最後の要素が格納されている場所を指します。この変数をスタックポインタと言います。また top の値はスタックの要素数に等しくなります。

スタックに要素 x を追加する関数 push(x)
top を 1 つ増やし、S[top] に x を代入します。

スタックのトップから要素を取り出す関数 pop( )
S[top] の値を返し、top を１つ減らします。

実際にスタックのデータ構造を操作する様子を見てみましょう。次の図は、配列によるスタックに適当な値を適当に出し入れしている様子を表しています。データ構造の操作は動的に発生するものなので、スタックの要素は変動していきます。

push(x) で渡された要素は、top を１つ増やした位置に挿入されます。一方、pop は top が指す要素を返し、top を１つ減らします。

配列によるスタックは次のように実装することができます。

1 initialize()
2   top = 0
3
4 isEmpty()
5   return top == 0
6
7 isFull()
8   return top >= MAX - 1
9
10 push(x)
11   if isFull()
12     エラー（オーバーフロー）
13   top++
14   S[top] = x
15
16 pop()
17   if isEmpty()
18     エラー（アンダーフロー）
19   top--
20   return S[top+1]

initialize 関数は top を 0 とすることでスタックを空にします。このとき配列（メモリ）の中に要素は残ったままですが、以降の push 操作によって上書きされます。isEmpty 関数は top が 0 かどうかを調べスタックが空かどうかを判定します。

isFull 関数はスタックが満杯かどうかを判定します。例えば、配列が 0 オリジンで容量が MAX で定義されている場合は、top が MAX-1 以上のときにスタックが満杯の状態になります。

push 関数では top を1 つ増やし、その場所に x を追加します。ただし、スタックが満杯の場合はなんらかのエラー処理を行います。

pop 関数では、top が指す要素、つまりスタックの頂点の要素を返しつつ、top の値を１つ減らすことで、頂点の要素を削除します。ただし、スタックが空の場合はなんらかのエラー処理を行います。

データ構造の設計・実装においては、それらに対する各操作にかかる計算量を見積もります。ここで紹介した配列によるスタックの操作の計算量は、pop、push ともにスタックポインタの加算・減算と代入演算を考慮して、$O(1)$ となります。

一般的にデータ構造は、構造体やクラスとして実装されます。クラスとして実装しておけば、複数のデータ構造を管理することができ、プログラムの中のデータとして扱いやすくなります。

Reference

---