スタック

スタックについて

　ここでは，スタックについて簡単に説明します。

　スタック（stack）は棚と言った意味ですが，コンピュータではスタックとは，後入れ先出し（LIFO：Last Input First Output）のデータの型を意味します。

　これは，棚に荷物を積んでいく状況と同様なものです。１つの棚にA，B，Cと順に荷物を積んだとします。荷物は下から順に積まれますから，下図の様になります。

　この荷物を取り出そうとすると，最初にC，次にB，そして最後にAになり，積んだ順序と逆の順序で取り出すことになります。つまり，後で入れたデータが先に出されることになります。このようなことを

後入れ先出し（Last Input First Output：LIFO）

と言います。そしてこれを実現するデータの型をスタックと言います。スタックはコンピュータ処理の色々な場面で表れる基本的な型の１つです。

　ここではこのスタックの実現方法とその使い方について説明します。

スタックの構成要素

　スタックで使われる基本操作は

荷物を積む
荷物を取り出す

です。そしてそれを行うための基本的情報として，

積んである荷物の個数

があります。これらをそれぞれ

荷物を積む（push）
荷物を取り出す（pop）
積んである荷物の個数（スタックトップ，あるいはスタックポインタ）

と言います。 push はSub プログラムとして実現し，pop は関数として実現します。

　

スタックの実現方法

　スタックは，配列変数を使うことで，比較的簡単に実現できます。

　スタックに積むデータを何にするかによって，色々なスタックが出来ますが，その作り方は基本的には大体同じですので，ここでは数値スタックを作成してみます。

　まず，スタックデータを格納するための配列とスタックトップを宣言します。例えば

Public NStk(100), NumTop, MaxStack

としましょう。これはスタックに最大100個の数値を積むために NStk という配列変数，および NumTop というスタックトップ，およびスタックの最大値MaxStackを宣言しています。サブプログラムや関数の中でも使えるよう Public 宣言をしています。

　実現の方法は，配列変数が下図のように配置されていると見ると分かりやすいでしょう。

...

NStk(4)

NStk(3)

NStk(2)

NStk(1)

NumTop

NumTop には現在スタックに積まれているデータの個数を格納しておきます。ですからNumTop の初期値（データが積まれていない状態）は０になります。更に今の場合，MaxStack = 100 として置きます。

push の実現

　push はサブプログラムを使います。数値スタックなので，　PushN と名付けます。勿論これ以外の名前でも構いません。プログラムは例えば次のようになります。説明のため行番号を付けています。

01 Sub PushN(A):'A の数値を スタックに積む
02    If NumTop >= MaxStack then
03       print "Stack over flow"
04    Else 
05       NumTop = NumTop + 1
06       NStk(NumTop)= A
07    End If
08 End Sub

　２行で新たにデータを積むことが出来るか判定しています。 NTop >= MaxStack の場合はデータが既に一杯でこれ以上積むことは出来ません。

　そうでない場合，５行で，NumTop （積んでいるデータの個数）を１つ加え，６行でその NumTop 番目の NStk の位置にデータ A を格納します。

　４行のエラー表示は，必要に応じて色々な方法が考えられます。ここでは，実行画面にその旨の表示をするようにしていますが，変数に値を返すことや，全く何もしないことなども考えられます。

pop の実現

　pop は関数を使います。数値スタックなので， PopN と名付けます。

01 Function PopN() :'スッタックから数値を取り出す。
02    If NumTop <= 0 then
03       print "Stack under flow"
04    Else
05       PopN = NStk(NumTop)
06       NumTop = NumTop - 1
07    end If
08 End Function

　２行でデータを取り出すことが出来るか判定しています。 NTop <= 0 の場合はデータが既にありませんから，取り出すことは出来ません。

　そうでない場合，５行で，NumTop （積んでいるデータの個数）番目のデータを取り出し，６行でその NumTop の個数を１つ減らします。

　以上を纏めると，以下のようになります。

Public NStk(100), NumTop, MaxStack
MaxStack = 100
'------------------------------------------
Sub PushN(A) :'A の数値を スタックに積む
   If NumTop >= MaxStack then
      print "Stack over flow"
   Else 
      NumTop = NumTop + 1
      NStk(NumTop)= A
      Print "   push : ";A
   end If
End Sub 
'------------------------------------------
Function PopN() :'スッタックから数値を取り出す。
   If NumTop <= 0 then
      print "Stack under flow"
   Else
      PopN = NStk(NumTop)
      NumTop = NumTop - 1
   end If
End Function
'------------------------------------------

　これだけのプログラムで，数値スタックが使えるようになります。

スタックの使い方

　スタックを使う場合，行う操作は，push, pop 及び，スタックトップの参照だけです。ですから，いまの場合

A を push する場合は

call PushN(A)

とし，pop してその値を A に入れるには

A = Pop()

とすれば良いわけです。

　例えば，

For i=1 to 10
   Call PushN(i)
Next i
For i=1 to 10
   Print PopN()
Next i

　とすると，実行画面に

10
9
8
...
2
1

と表示されます。

まとめ

　スタックを使った例としてはSample にある OnedigitCalc.tbt とスタック電卓があります。それらのプログラムで実際の使い方を見て下さい。