第８回目 スタック（5/29）

今日のキーワード

• スタックの操作は、push と pop
• 数のスタック
• ポインタのスタック

■ スタック

• スタックとは、データを積み重ねて格納する方法である。最初に格納したデータは、最後に参照できる。たとえば、何冊もの本を、机の上に１冊ずつ積み重ねると、最初に積んだ本は、後から積んだ本をとり除かなければ手にすることができない。
• データを積む（格納する）操作を「push」、取り出す操作を「pop」という。
• 最後に積んだデータを表すポインタをスタックポインタという。push 操作では、スタックポインタを1つ動かして、データを格納する。pop 操作では、データを参照後、スタックポインタを1つ動かす。

  

• 一般に、アセンブラ言語（機械語のレベルのプログラミング言語）では、push 操作によりスタックポインタがアドレス値の小さい方向に進み、pop 操作により大きい方向に進む。
• 今回の演習では、C言語で作成する場合は、push操作によりスタックポインタが配列番号の大きい方向に進み、pop操作ではその逆に進むものとする。上図はC言語の練習用に作図している。

■ 数のスタック

／＊　ｌｉｓｔ０８０１．ｃ　＊／
＃ｄｅｆｉｎｅ　ＳＩＺＥ　２０

ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ｛
　　ｉｎｔ　ｎｕｍ［ＳＩＺＥ］；
　　ｉｎｔ　ｓｐ；
｝　Ｓｔａｃｋ；


Ｓｔａｃｋ　＊ｓｔａｃｋ＿ｉｎｉｔｉａｌｉｚｅ（）
｛
　　Ｓｔａｃｋ　＊ａｎｓ；

　　ａｎｓ　＝　（Ｓｔａｃｋ　＊）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（Ｓｔａｃｋ））；
　　ａｎｓ−＞ｓｐ　＝　−１；
　　ｒｅｔｕｒｎ　ａｎｓ；
｝

ｖｏｉｄ　ｐｕｓｈ（Ｓｔａｃｋ　＊ｓ，　ｉｎｔ　ｎ）
｛
　　ｓ−＞ｓｐ　＋＝　１；
　　ｓ−＞ｎｕｍ［ｓ−＞ｓｐ］　＝　ｎ；
｝

ｉｎｔ　ｐｏｐ（Ｓｔａｃｋ　＊ｓ）
｛
　　ｉｎｔ　ａｎｓ；

　　ａｎｓ　＝　ｓ−＞ｎｕｍ［ｓ−＞ｓｐ］；
　　ｓ−＞ｓｐ　−＝　１；
　　ｒｅｔｕｒｎ（ａｎｓ）；
｝

ｍａｉｎ（）
｛
　　Ｓｔａｃｋ　＊ｓ；

　　ｓ　＝　ｓｔａｃｋ＿ｉｎｉｔｉａｌｉｚｅ（）；
　　ｐｕｓｈ（ｓ，１）；
　　ｐｕｓｈ（ｓ，２）；
　　ｐｕｓｈ（ｓ，３）；
　　ｐｒｉｎｔｆ（”％ｄ＼ｎ”，ｐｏｐ（ｓ））；
　　ｐｒｉｎｔｆ（”％ｄ＼ｎ”，ｐｏｐ（ｓ））；
　　ｐｒｉｎｔｆ（”％ｄ＼ｎ”，ｐｏｐ（ｓ））；
　　ｆｒｅｅ（ｓ）
｝

□ 演習１

• list0801.c は、次の問題が残っている。
  • 関数 stack_initialize で、malloc に失敗したことを検査していない。
  • SIZE を越えて push できる。
  • スタックが空の状態であっても pop できる。
  それぞれ検出した際にエラー終了とせよ。⇒ prac0801.c

■ ポインタのスタック

ポインタのスタックは次のように定義する。

ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ｛
　　Ｓｔｕｄｅｎｔ　＊ｓｔｄ［ＳＩＺＥ］；
　　ｉｎｔ　ｓｐ；
｝　Ｓｔａｃｋ；

上では省略されているが、Stack 型の宣言をする前に、Student 型の宣言、SIZE の define を済ませておく。

初期化関数 stack_initialize は、list0801.c と同じである。

関数 push は、基本的に以下の処理をする。

ｉｎｔ　ｐｕｓｈ（Ｓｔａｃｋ　＊ｓ，　Ｓｔｕｄｅｎｔ　＊ｓ１）
｛
　　スタックポインタを１つ進める。
　　ｓのｓｔｄ配列のうち、スタックポインタの位置にある領域に、ｓ１（アドレス値）を書き込む。
｝

関数 pop は、基本的に以下の処理をする。

Ｓｔｕｄｅｎｔ　＊ｐｏｐ（Ｓｔａｃｋ　＊ｓ）
｛
　　ｓのｓｔｄ配列のうち、スタックポインタの位置にあるアドレス値を得る。
　　スタックポインタを１つ戻す。
｝

以前に作成した関数 print_student は、student_print に名前を変更する。

メイン関数は、次のとおりとする。

ｍａｉｎ（）
｛
　　Ｓｔａｃｋ　＊ｓ；
　　Ｓｔｕｄｅｎｔ　＊ｓｔ；

　　ｓ　＝　ｓｔａｃｋ＿ｉｎｉｔｉａｌｉｚｅ（）；
　　ｓｔ　＝　（Ｓｔｕｄｅｎｔ　＊）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（Ｓｔｕｄｅｎｔ））；
　　ｓｅｔ＿ｇａｋｕｓｅｋｉ（ｓｔ，”０２２００２”）；
　　ｓｅｔ＿ｎａｍｅ（ｓｔ，”天野淳介”）；
　　ｐｕｓｈ（ｓ，ｓｔ）；
　　ｓｔ　＝　（Ｓｔｕｄｅｎｔ　＊）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（Ｓｔｕｄｅｎｔ））；
　　ｓｅｔ＿ｇａｋｕｓｅｋｉ（ｓｔ，”０２２００４”）；
　　ｓｅｔ＿ｎａｍｅ（ｓｔ，”有川竜則”）；
　　ｐｕｓｈ（ｓ，ｓｔ）；
　　ｓｔ　＝　（Ｓｔｕｄｅｎｔ　＊）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（Ｓｔｕｄｅｎｔ））；
　　ｓｅｔ＿ｇａｋｕｓｅｋｉ（ｓｔ，”０２２００５”）；
　　ｓｅｔ＿ｎａｍｅ（ｓｔ，”淡路啓太”）；
　　ｐｕｓｈ（ｓ，ｓｔ）；

　　ｓｔ　＝　ｐｏｐ（ｓ）；
　　ｓｔｕｄｅｎｔ＿ｐｒｉｎｔ（ｓｔ）；
　　ｆｒｅｅ（ｓｔ）；
　　ｓｔ　＝　ｐｏｐ（ｓ）；
　　ｓｔｕｄｅｎｔ＿ｐｒｉｎｔ（ｓｔ）；
　　ｆｒｅｅ（ｓｔ）；
　　ｓｔ　＝　ｐｏｐ（ｓ）；
　　ｓｔｕｄｅｎｔ＿ｐｒｉｎｔ（ｓｔ）；
　　ｆｒｅｅ（ｓｔ）；
｝
 実行中にメモリの確保されるイメージ