上に戻る
2.スタックって?
概要
 スタックというものを説明してみます。と、言っても、自分はスタックの厳密な定義とか知らないので、私(わたし)的な『スタック感』となりますが……
まずはモデルから
 スタックは、メモリの管理方法の1つです。それを、なんとなくモデルにしてみました。
 ココに1本の茶筒状のシリンダーがあります。茶筒は口が開いており、底は閉じています。
 口の開いた茶筒
 ココに、円筒形のブロックを入れていきます。円筒形のブロックには数字が書いてあります。
 茶筒にブロックを詰める
 1つブロックが入りました。これで、データが1つ格納されました。続けてポコポコ入れます。
 たくさん詰めました
 さて、ブロック(=データ)を取り出すにはどうしたらいいでしょう?簡単です。茶筒をひっくり返せばデータが1つ落ちてきます。
 なんで1つしか落ちてこないかって突っ込まないの……
 こんな感じで、後に入れたデータが最初に、先に入れたデータが最後に取り出されるようなメモリ管理方法の1つが、スタックです。
 ちなみに、スタックとは逆に、先に入れたデータは最初に取り出されるようなデータ管理の1つは、キューというそうです。
もっと実装的に……
 スタックはメモリ管理方法ですので、当然、スタック用のメモリが必要です。上のモデルだと茶筒に相当ですね。
 そして、上のモデルだと『茶筒のどこまで詰まっているか』を記憶しておくメモリが必要です。スタックポインタと呼ばれると思います。
 上の例をもう少しソレっぽく図にしたのだが……
 スタックにデータを詰めることを『プッシュ』、データを取り出すことを『ポップ』『プル』というみたいです。
 上の図で次にABが『プッシュ』されると、1004がABになって、スタックポインタが1005になりそうですね。

 ここまではモデルですが……
   ・スタック用メモリがどこに確保されるか
   ・それは固定された場所か
   ・そのサイズが固定か可変か
   ・1回の値のやり取りで何ビットデータが取り出されるか
   ・スタックポインタの移動方向   ※上のモデルケースと違ってプッシュで減ることが多いと思う
   ・スタックポインタは次に積む位置を指すのか取り出す位置を指すのか
 等は、全て処理系依存です。
 例えば、ファミコンですと……
   ・スタック用メモリはメモリは0100〜01FFに場所もサイズも固定
   ・8ビット単位で積み下ろし
   ・プッシュ時にスタックポインタは減る
   ・スタックポインタは、次に積む場所を指す
 です。
 あと、スタック上のデータも、所詮メモリ上のデータなので、わざわざ茶筒をひっくり返さなくても、横から書き換えたり取り出したりも当然出来ます。処理系がそれを許すなら。
 この場合は、スタックポインタの場所が変わらないことになりますな。『スタックポインタの値を取り出していくつか加減算したアドレス』から取り出せば、『n回前にプッシュしたデータ』を取り出したりもできるでしょう……
なんの役に立つのよ?
 なんか、値のやり取りに制限があって全然便利そうじゃないスタックですが実はとんでもなく便利です。誰が考えたんでしょ?
 スタックを使う花形は、サブルーチンの呼び出しです。
 プログラミング言語を使った事のある方は、サブルーチンからなんで元の場所に復帰できるのだろう……とか思ったことがあるかもしれません。
 あくまでモデルになりますが……
 サブルーチンコールするときに、元の場所(プログラム実行位置)をスタックにプッシュします。
(そしてさらに、そのサブルーチン内でさらにサブルーチンを呼ぶときは、さらにその場所をスタックにプッシュします。)
 サブルーチンから元の位置に帰る時は、プログラム実行位置を、スタックからポップしたデータの場所にすれば、元の場所に戻れます。
 こうして、スタック用メモリが許す限り、何重にもサブルーチンコールすることが出来ます。
 高級言語ですと、『元の場所』以外にも、『呼び出しに際する引数』や『サブルーチン内で用いるローカル変数』なんかもスタックに積みます。
 これらは、そのサイズがコンパイル時に計算されているので、スタックポインタを適当に調整してスタックから取り出したり書き込んだりすれば、引数やローカル変数と、自由に値をやり取りできるわけです。
 なんかわかりづらいので図解してみたけど、余計わかりにくいような……
 わかりづらい図解
 今にもスタックオーバーフローを起こしそうな図解だ^^
(22)2007年2月17日 プレさ兵衛
inserted by FC2 system