create every day - 福野泰介の一日一創

IchigoJamで学ぶデータ構造「スタック」 / Stack on IchigoJam

2017/06/20 23:55:00
#IchigoJam 

プログラミングにおける基本的なデータ構造のひとつ「スタック」。入れることをPUSH(プッシュ)、出すことをPOP(ポップ)と呼ぶ。
"Stack" is an important data structures in the computer. PUSH to put in to the stack, POP to get from the stack.

"Stack / スタック" from Wikipedia

IchigoJamにある102コの配列を使って、PUSH/POPを実現する。
Use 102 sizes array on IchigoJam to PUSH and POP.

S=0 OK [S]=1:S=S+1 OK [S]=2:S=S+1 OK [S]=3:S=S+1 OK [S]=4:S=S+1 OK [S]=5:S=S+1 OK [S]=6:S=S+1 OK ?S 6

1から6をPUSHしたので、配列の0から5までが使われ、次入れる位置が6になっている。この位置のことをスタックポインタと呼ぶ。
PUSH 1 to 6, so using the array from 0 to 5, stack pointer became 6.

S=S-1:?[S] 6 S=S-1:?[S] 5 S=S-1:?[S] 4 S=S-1:?[S] 3 S=S-1:?[S] 2 S=S-1:?[S] 1 S=S-1:?[S] Index out of range

最後に入れたものから、6から1までが取り出せた(POP)。更に取り出そうとすると配列の限界を超えるのでエラーとなる。
You can get 6 to 1 (POP). It will be an error if you get more.

多重ループ、多段に使われるGOSUB、スタックはマシン語における変数の一時記憶など、コンピューターではよく使われるテクニック。
Stack uses loops, GOSUBs, temporaly memory storage with the machine language and etc...

簡単に演算の優先度付きの計算機をつくるサンプルがこちら。(逆ポーランド計算機より)
This is a sample of calculator with Stack.

1 'R-POLISH CALC 10 S=0 20 CLS:IF S FOR I=0 TO S-1:LC0,23-I:?"[";I;"]=";[I];:NEXT 30 LC0,0:INPUT N 40 IF N=0 C=SCR(1,0):IF C!=ASC("0") GOSUB 70:GOTO20 50 [S]=N:S=S+1 60 GOTO 20 70 IF C=ASC("+") [S-2]=[S-2]+[S-1]:S=S-1 80 IF C=ASC("-") [S-2]=[S-2]-[S-1]:S=S-1 90 IF C=ASC("*") [S-2]=[S-2]*[S-1]:S=S-1 100 IF C=ASC("/") [S-2]=[S-2]/[S-1]:S=S-1 110 IF C=0 S=S-1 120 RETURN

3 エンター、5 エンター、+ エンターで、8と計算できる。
3 enter, 5 enter, + enter, you'll get 8.

5 エンター、2 エンター、10 エンター、* エンター、+ エンターで、5+2*10=25 と計算できる。
5 enter, 2 enter, 10 enter, * enter, + enter, you'll get 5+2*10=25.

IchigoJam web で、試してみよう!(長いプログラムのimportに対応!)
"http://fukuno.jig.jp/app/IchigoJam/#1%20'R-POLISH%20CALC%0A10..."
Try on the web also!

通常の配列と同居させるため、配列の最後からスタックポインタを減らすように実装するのもOK!
If you want to use the array normally, you can start the stack pointer as 101 (last) also.

links
- 楽しさ広がるマルチバイトメモリアクセスとスタック - IchigoJamではじめるARMマシン語その5
- ものづくり好き x 学べるという気づき - IchigoJamで逆ポーランド計算機づくり

Tweet
クリエイティブ・コモンズ・ライセンス
この作品は「Creative Commons — CC BY 4.0」の下に提供されています。
CC BY 福野泰介 - Taisuke Fukuno / @taisukef / high-res profile image