2 スタック

2.1 イメージ

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

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

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

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

push: ＜人・物を＞押す，突く
pop: ポンという音を立てる，ひょいとやって来る[出て行く]，急にはいる[出る], ひょっこり現れる

である．

**図 2:** スタック
$\includegraphics[keepaspectratio,scale=1.0]{figure/stack.eps}$

2.2 実際の応用

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

関数を呼び出した場合，呼び出し元のデータをいったん保存するときのデータ構造として使われる．
算術式の評価(教科書の List 4-3)

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

2.3 スタックの実装

スタックを実装する関数をリスト1に示す．これは，教科書の List 4-1(p.100)と同じである(転載について)．

スタックを実装するために必要な記憶領域は，スタックそのものの記憶領域とスタックの頂上を表す記憶領域である．スタックのための記憶領域として配列stack[]を使っている．また，スタックの頂上を表すために，変数stack_topを使っている ²．

スタックのために必要な記憶領域が確保されたならば，それを操作しなくてはならない．スタックに必要な操作は2つで，データを積む(push)ことと，データを取り出す(pop)ことである．リスト1では，次の2つの関数でそれを行っている．

void stack_push(double val): スタックへデータvalをプッシュする関数である．データを積み重ねたならば，スタックの頂上を表す変数 stack_topを1加算している．スタックがいっぱいで，さらにデータをプッシュしようとするとプログラムは終了するようになっている．
double stack_pop(void): スタックからデータを取り出す関数で，戻り値が取り出されたデータである．データを取り出したならば，スタックの頂上を表す変数stack_topを1減算している．スタックが空の状態でデータをポップしようとするとプログラムは終了するようになっている．

ここで使われているプログラムのテクニックは，すでに学習済みであるが，分かりにくいものだけ述べておく．

15行目 exit(EXIT_FAILURE);

関数exit()は，正常にプログラムを終了させるために使う．これが呼び出されると，諸々の処理を行いプログラムが止まる．ここで使われている引数EXIT_FAILUREの定義はstdlib.hに書かれている．私のコンパイラーでは，
```
	#define	EXIT_FAILURE	1	/* Failing exit status.  */
```
となっていた．したがって，この行は，
```
	exit(1);
```
と同じである．exit(EXIT_FAILURE);とすると処理系定義の不成功状態の形式が返される．

リスト1 スタックの実装(転載について)

   1 #define STACK_MAX 10
   2 
   3 /* ※この例では，double型のデータを格納するスタックを作成 */
   4 double stack[STACK_MAX];
   5 /* スタック頂上の位置（最下部からのオフセット） */
   6 int stack_top=0;
   7 
   8 /* スタックへpush */
   9 void stack_push(double val)
  10 {
  11     if(stack_top==STACK_MAX)
  12     {
  13         /* スタックが満杯になっている */
  14         printf("エラー:スタックが満杯です(Stack overflow)\n");
  15         exit(EXIT_FAILURE);
  16     }
  17     else
  18     {
  19         /* 渡された値をスタックに積む */
  20         stack[stack_top]=val;
  21         ++stack_top;
  22     }
  23 }
  24 
  25 /* スタックからデータをpop */
  26 double stack_pop(void)
  27 {
  28     if(stack_top==0)
  29     {
  30         /* スタックには何もない */
  31         printf("エラー:スタックが空なのにpopが呼ばれました"
  32                                         "(Stack underflow)\n");
  33         exit(EXIT_FAILURE);
  34         return 0;
  35     }
  36     else
  37     {
  38         /* いちばん上の値を返す */
  39         --stack_top;
  40         return stack[stack_top];
  41     }
  42 }

[転載について]
このページ中のリスト1のプログラムは，教科書として使用している以下の書籍

書名プログラミングの宝箱　アルゴリズムとデータ構造 ISBN4-7973-2419-8

著作者紀平拓男・春日伸弥

出版社ソフトバンク　パブリッシング株式会社

から転載しました．この転載に関しては，著者と版元に許諾を得ています．

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

no counter

書名	プログラミングの宝箱　アルゴリズムとデータ構造 ISBN4-7973-2419-8
著作者	紀平拓男・春日伸弥
出版社	ソフトバンク　パブリッシング株式会社