スタック
データ構造
スタックはデータを配列に入れたり、配列から出したりするときの、やり方の１つです。
キューとかリストというお友達もいます。それぞれの違いは、
| スタック | 最初の入れたデータが最後に出る |
| キュー | 最初の入れたデータが最初に出る |
| リスト | データを自由に並べ替えできる |
前回やった自己参照構造体はまさにリストです。
A→B→C→DをA→D→B→Cというように並べ替えるには、ポインタを変更することで簡単にできます。
スタック
スタックは、データを入れるpush関数と取り出すpop関数とで実現できます。
プログラムを作ってみたので見てください。エラー処理等はしていません。
アセンブラみたいになってしまいました。すいません。
#console
#include<vcrt71.sbp>
Dim stack[10] As Long
Dim sp As Long'スタックポインタ、スタックの位置を保存
'スタックにデータを入れる
Sub push(x As Long)
stack[sp] = x
sp = sp + 1
End Sub
'スタックからデータ取り出し
Function pop() As Long
sp = sp - 1
pop = stack[sp]
End Function
'------------------------------
'スタックを使った四則計算関数
Sub add()'足し算
push(pop() + pop())
End Sub
Sub subt()'引き算
push(pop() - pop())
End Sub
Sub mul()'掛け算
push(pop() * pop())
End Sub
Sub divi()'割り算
push(pop() / pop())
End Sub
'-------------------------------------------
push(20)
push(10)
push(90)
push(10)
add() '10 + 90
divi() '100 / 10
mul() '10 * 20
printf(Ex"%d\n" , pop())
図にするとこうなります。処理とその結果です。
push(20) push(10) push(90) push(10)
+------+ +------+ +------+ +------+
| | | | | | sp| 10 |
+------+ +------+ +------+ +------+
| | | | sp| 90 | | 90 |
+------+ +------+ +------+ +------+
| | sp| 10 | | 10 | | 10 |
+------+ +------+ +------+ +------+
sp| 20 | | 20 | | 20 | | 20 |
+------+ +------+ +------+ +------+
add() divi() mul() pop()
+------+ +------+ +------+ +------+
| | | | | | | |
+------+ +------+ +------+ +------+
sp| 100 | | | | | | |
+------+ +------+ +------+ +------+
| 10 | sp| 10 | | | | |
+------+ +------+ +------+ +------+
| 20 | | 20 | sp| 200 | | |
+------+ +------+ +------+ +------+
sp