| まず、用語をいくつか覚えましょう。スタックに値を格納することを push と言います。スタックから値を取り出すことを pop と言います。 | ||
| スタック中では push された値が下から積み上げられていきます。pop するときは、一番上に乗っている値から順に取り出されていきます。こういう方式を「先入れ後出し(LIFO = Last In/First Out)」と言います。 | ||
 |
||
| 上の図のようなバネがついた箱を想像するとイメージがわきやすいでしょう。でもこれは概念的なイメージです。もっと深く理解するにはメモリの中でのイメージを身につけないといけません。 | ||
| スタックを実現するために、専用のメモリ領域とレジスタが用意されています。専用のメモリ領域は「スタック領域」などと呼ばれます。1つの実行スレッドごとに1つのスタック領域が割り当てられます。"Hello, world" のような単純な(シングルスレッドの)プログラムの場合は、スタック領域は1つです。専用のレジスタは「スタックポインタ(SP)」と呼ばれるもので、スタック領域中のどこかのアドレスを格納することができるものです。 | ||
 |
||
| では、スタックに push する場合の動作を追ってみましょう。スタック領域は後ろの方(アドレスの大きい方)から使われます。いま、スタック領域とスタックポインタ(SP)が下図のようになっている状況を想定しましょう。 | ||
 |
||
| スタックポインタはスタック領域中のアドレス a を指しています。ここに4バイトの値(典型的には int 型)を push します。そのためには、まずスタックポインタの値を格納するデータのサイズ分だけ減らします。ここでは4バイトのデータなので、スタックポインタの値は a-4 になります。次に、スタックポインタが指すアドレスにデータを格納します。すると、次の図のような状態になります。 | ||
 |
||
| もうひとつ、1バイト(典型的には char 型)の値を push してみましょう。すると、次の図のような状態になります。 | ||
 |
||
| 今度は pop してみましょう。最後に push したデータから順に取り出すので、先に1バイトの値を取り出します。 | ||
| スタックポインタはいつも最後に push した値の先頭アドレスを指しています。そこで、まずスタックポインタが指すアドレスから1バイト取り出し、取り出したバイト数(ここでは1バイト)だけスタックポインタの値を増やします。すると、次の図のような状態になります。 | ||
 |
||
| 同様にして、4バイトの値を pop すると、次の図のような状態になります。 | ||
 |
||
| これで、スタックは最初の状態に戻りました。 | ||
|
※
|
スタックの概念的なイメージと、実際にメモリの中でどうなっているかのイメージを、しっかり対応付けておいてください。このような対応付けのトレーニングはエンジニアにとって重要な意味を持ちます。概念的なイメージは「モデル」にあたり、メモリ中での実際の動作は「実装」にあたります。これは「設計」と「コーディング」の対応関係とも似ています。設計の時にはシステムを表現するためにちょうど良い論理構造、すなわちモデルを見つけることが重要であり、コーディングにはそのモデルを実際にコンピューター上で実現するという意味があります。 | ||
| ところで、スタック領域のサイズは有限です。ですから push できるデータの総量は決まっています。この限界を越えて push しようとすると、スタックポインタがスタック領域をはみだしてしまいます。こうなると、プログラムはクラッシュします(または OS によって強制的に終了させられます)。ですから、スタックは無駄使いしないように注意しないといけません。たとえば関数呼び出しの時に大きなサイズのパラメータをたくさん使ったり、自分自身を繰返し呼び出すような関数(再帰呼び出し関数)を書くときには十分注意しないといけません。 | ||
| さて、ここまで理解できれば自分でスタックの形をしたデータを作ることができますね。大きめのメモリ領域を確保し、ポインタを1つ用意すればできてしまいます。スタックは基本的なデータ構造の1つなのです。 | ||
| スタックと言えば、もうひとつ「キュー」と呼ばれるデータ構造があります。"Hello, world" とはあまり関係ないのですが、次回はこれについて簡単に説明します。 | ||
 |
|
（"Hello, ANOTHER world!" は2001年11月から2002年11月にかけて作成されたコンテンツです。）
目次に戻る