解説 6月21日A

今回の学習項目です。


スタック(Stack)

教科書66ページから67ページまで読んでおいてください。

スタックとは次の条件を満たすデータ構造です:

「後に入った情報から先に出て行く」という性質から、LIFO(Last In First Out)とも呼ばれています。 スタックとしては、食堂にあるお盆置き場(図6.6)がぴったりあてはまります。お盆をおけるのはすでに積まれているお盆の上に限られ、お盆を取り出すのも上のお盆からとられます。つまり新たに載せられたお盆が最初に取り出される、という仕組みです。

スタックは、キューと同様、追加と取り出し方法が制限された「リスト構造」とみることもできます。

スタックについて学ぶことは次の3点です。

  1. どのようなデータ構造によってスタックが実現できるか。
  2. スタックに固有な操作にはどのようなものがあるか。
  3. スタックを用いた応用にはどのようなものがあるか。

スタックの実現方法

配列と変数を用いてスタックは実現できます。ここで配列はデータの記憶用です。 また変数を1つ用います。topという名前とします。 topによって配列における最新のデータの位置を記憶します。一番古いデータは恒に配列の先頭にあります。ですから、topの値がそのままスタックで記憶されている要素の数を表しています。 この変数以外にスタックで記憶できるデータの最大数を記憶するための変数(前をmaxとしておきます)を用いることもあります。

スタックに固有な操作

スタックを用いた応用

一つの例は、プログラミング言語において関数の呼び出しを処理するメカニズムです。関数の呼び出しでは、 (1)関数の処理が終わった時に戻る場所、(2)呼び出しに用いられた(仮)引数とその値、 (3)呼び出された関数の局所変数、を記憶するためにスタックが使われます。 そして関数呼び出しが終わったらこれらのデータはすべてポップされ、関数が呼び出された後の場所に処理が移ります。

もうひとつの例は、逆ポーランド記法で書かれた数式の処理です。逆ポーランド記法で書かれた数式の処理は 基本的には次のように行われます: 数式を順に読み込み、数ならスタックにプッシュする、演算子ならスタックから引数を2つポップし、その演算子を適用(計算)し、その結果をスタックにプッシュする。 これについては後の課題で扱います。

課題1-1

最初はスタックにはデータが入っていないものとします。 Rubyの配列にならって、この状態を[ ]で表すことにします。 また、スタックの先頭はインデックスの0の要素とします。 たとえばスタックの内容が[1,2,3]だったとすると、先頭の要素は1、 その後ろの要素は2、最後の要素は3であるようなスタックを表すこととします。

最初空っぽのスタックに対して次の操作を行ったときのスタックの状態を今の説明にしたがって表しなさい:

  1. 10をスタックに入れる
  2. 20をスタックに入れる
  3. 30をスタックに入れる
  4. スタックからデータを取り出す
  5. 40をスタックに入れる
  6. スタックからデータを取り出す
  7. スタックからデータを取り出す
  8. 50をスタックに入れる

課題1-2

変数sに空っぽのスタックを代入したものとします。 ここで、スタック(s)に対しデータ(x)を入れる操作pushを s.push(x) と表すこととします。また、スタック(s)からデータを取り出す操作 pop upを s.popup で表すこととします。 この記法を用いて課題1-1のそれぞれの操作を表しなさい。

Rubyを用いた実現

スタックをRubyのクラスとして定義してみましょう。初めの試みとして以下のように定義することを考えます。

class Stack
   def initialize()
       @data = []   # データの記憶用の配列
       @top = -1    # 先頭のデータの位置
       @max = 10    # 記録できるデータの最大個数
   end # initialize
   def push(x)
       @top += 1
       @data[@top] = x
   end  # def of push
   def popup
       ans = @data[@top]  
       @top -= 1
       return ans
   end  # def of popup
   def empty # スタックが空ならばtrueを返す
       if (@top >= 0)
          return false
       else
          return true
       end  # if
   end  # def of empty
   def show  # スタックの内容の表示
       return @data[0..@top]
   end # def of show
end # class
ここではメソッドとして initialize、push、popup、empty, そしてshowを用意しました。 initializeはクラスのインスタンスを作るための関数でした。 ですから、例えばs=Stack.newとすると、Stackクラスのインスタンスが一つ作られ、それがsの値としてセットされます。そしてインスタンス変数data, top, maxにはそれぞれの値がセットされます。

pushとpopupのメソッドはそれぞれスタックに要素を付け加える操作と、スタックからデータを取り出す操作です。それぞれのメソッドを実行すると topの値が変化することに注意しましょう(もちろんdataの値も変わります)。 最後にshowはスタックの状態を表示するためのもので、配列として要素が表示されます。

課題1-3

このクラスの定義を用いて、課題1-2を実行しなさい。またそれぞれの操作の後、 スタックに記憶されている要素がどのように変化するかも表示しなさい(ヒント: showメソッドを使う)。

課題1-4

逆ポーランド記法で書かれた数式の処理をスタックを用いておこなってみましょう。 逆ポーランド記法で書かれた数式の処理は基本的には次のように行われます: 数式 30 5 / 6 - を例とします。その処理は以下のように行われます:
  1. 最初の記号、30を読み込みます。これは数なのでスタックにプッシュします。 (スタックの中身は[ 30 ]です)
  2. 次の記号、5を読み込みます。これも数なのでスタックにプッシュします。 (スタックの中身は[30, 5]です)
  3. 次の記号 / を読み込みます。これも演算子なので、スタックから2つポップアップします。 初めにポップされた数は5、次が30なので、30 / 5(この順番に注意!)を計算し、その結果である6をスタックにプッシュします。(スタックの中身は[6]です)
  4. 次の記号6を読み込みます。これも数なのでスタックにプッシュします。 (スタックの中身は[6, 6]です)
  5. 次の記号 - を読み込みます。これも演算子なので、スタックから2つポップアップします。 初めにポップされた数は6、次も6なので、6 - 6(この順番に注意!)を計算し、その結果である0をスタックにプッシュします。(スタックの中身は[0]です)
  6. もう読み込むものがないので、スタックからポップした数0を返して終了します。
次の逆ポーランド記法で書かれた数式 1 2 3 + + 5 * 10 / を計算しなさい。 なお、この例にならって、その途中経過を書くこと。

課題1-5

(時間がない場合はやらなくてもよい)
逆ポーランド記法の数式をRubyの配列として表すとする。例えば、 1 2 3 + + 5 * 10 /[1,2,3,"+","+",5,"*",10,"/"]とする。 これを引数とし、課題1-4の方法によりスタックを使って計算するRubyのプログラムを書きなさい。 そしてこのプログラムの結果と課題1-4の計算結果とを比較しなさい。

「アルゴリズムとデータ構造」のホームに戻る