2 スタック

最後に入れたデータをはじめに取り出すスタックと呼ばれるデータ構造について説明する．

2.1 イメージ

スタック(stack)を辞書で調べてみると，次のような意味が書かれている．

1. (干し草などの)大きな山，積みわら(haystack);(物のきちんとした)積み重ね
2. (図書館などの)書棚の列，書架；((the 〜s)) (図書館の)(閉架)書庫
3. (屋上の)組み合わせ煙突(chimney stack);煙突，煙出し
4. 《コンピューター》スタック:最後に入れたデータを最初に取り出せるようにしたデータ構造

もちろん，情報科学の分野で使われるのは最後の意味で，図2のようなデータ構造で ある．データ構造であるから，データを蓄えることと，それを取り出すことができる．ス タックの特徴は，最後に入れたデータが一番最初に取り出されることにある．取り出され るデータは，格納されている最新のデータで，最後に入れられたものが最初に取り出され ることから，LIFO(last in first out, 後入れ先出し)と呼ばれる．スタックの途中のデー タを取り出すことは許されないのである．

スタックにデータを積むことをプッシュ(push)と，スタックからデータを取り出すことを ポップ(pup)と呼ぶ．これらの英語の意味は，

push

＜人・物を＞押す，突く

pop

ポンという音を立てる，ひょいとやって来る[出て行く]，急にはいる[出る], ひょっこり現れる

である．

図 2: スタック

2.2 実際の応用

スタックは単純なデータ構造であるが，有用でいろいろな場面で使われる．例えば，次の ような場合である．

• 関数を呼び出した場合，呼び出し元のデータをいったん保存するときのデータ構 造として使われる．
• 算術式の評価(教科書 [1]のpp.189-192)．これは逆ポーランド記 法でかかれた数式を計算するプログラムである．

カッコの対応を調べるプログラムや逆ポーランド記法を用いた数式の計算(p.114-115 List 4-3)などでも使われる．授業では説明しないので，興味のある者は自分でソースコー ドを解析するのが良いだろう．

2.3 スタックの実装

配列を使えば，スタックの実装は簡単である．教科書 [1]では，次のよう な構造体を宣言している．

	typedef struct stack{
	  int top;
	  int size;
	  int data[1];
	}stack_t;

この構造体には，スタックに必要な情報がすべてがある．図3に示 すようにメンバー変数topは，次にデータを入れる配列の添え字を表している． sizeは配列の要素数を表し，このスタックに蓄えることができるデータ数となって いる．

図 3: 教科書 [1]のスタックのイメージ．配列中の?はデータは あるが，意味のない--使い道のない--データを表している．

スタックを実際に使うためには記憶領域が確保と操作を行う必要がある．教科書のstack.c では，次の3つの関数でそれを行っている．記憶領域の確保を行うcreat_stackとデー タを格納するpush()，データを取り出すpop()である．

ホームページ: Yamamoto's laboratory
著者: 山本昌志