スタックとキューの演習
スタックとキューは基本的なデータ構造で、個数が変わる配列のようなイメージで一時的なデータ置き場として使う。CPUの内部などハードウェアでも用意されている。
スタックとキューは、はじめはカラであり、できることはデータを一ついれる、一つ取り出すの２種類だけである。（拡張してその他のことができるものもある）
スタックは FILO : ファーストインラストアウト。入れたデータは積み重なり、最後に入れたものが先に取り出せる。
キューは FIFO : ファーストインファーストアウト。入れたデータは押し込まれ、最初に入れたものが先に取り出せる。コンビニ棚の先入先出のこと。
スタックの実装例
スタックエリア(data )、スタックポインタ(pointer)からなる構造体でデータを保持し、
扱う関数として push (=入れ)と、pop （=取り出し）の機能がある。
ここでのpopは取り出すだけでスタックを変更しないので、スタックの一番上を捨てる関数 drop も別に用意した
typedef struct Stack { ... } Stack; という書き方は構造体に短い名前をつけて使う方法。「struct Stack」を「Stack」と短く書けるようになる。
code:stack.c
typedef struct Stack{
int pointer;
} Stack;
/* ----- prototypes ----- */
Stack stack_init();
Stack stack_push(Stack s, int n);
int stack_pop(Stack s);
Stack stack_drop(Stack s);
/* ----- main ----- */
int main(void){
Stack s;
int o;
s = stack_init();
s = stack_push(s, 10);
s = satck_push(s, 20);
o = stack_pop(s);
s = stack_drop(s);
s = stack_push(s, 30);
// s.stack の中身は 10, 30 となっている。 o には 20 が入っている。
}
/* ----- functions ----- */
Stack stack_init(){
Stack s;
s.pointer = 0;
return s;
}
Stack stack_push(Stack s, int n){
if(s.pointer >= MAX_S) {printf("error : stack overflow\n"); exit(1); }
s.pointer ++;
return s;
}
int stack_pop(Stack s){
if(s.pointer == 0) {printf("error : stack empty\n"); exit(1); }
}
Stack stack_drop(Stack s){
if(s.pointer == 0){{printf("error : stack underflow\n"); exit(1); }
s.pointer --;
return s;
}
クイズ
pop と drop を分けている理由はなにか
それを分けないですむ方法を考えよう -> 演習５
演習問題
1） スタック s の中身がないとエラーで終了になってしまう。
あらかじめ、sの中身がカラかどうかを判定し カラなら 0、あればそれ以外（1や2、、）の整数を返す関数 stack_isnotempty( ) を書こう
2） いくつかの整数を読み込んで逆順に表示するプログラムを作ろう。
-1 が入力されるまで読み込む
code: q1base.c
// stack の準備など
// prototype宣言など
/* ----- main -----*/
int main(void){
Stack s;
int in;
while(1){
scanf("%d", &in);
if (in == -1) break;
// なにかかく
}
while(1){
if (stack_isempty(s) == 0) break;
// なにかかく
}
}
3) いくつかの整数を読み込み、奇数は表示せず偶数だけを逆順に表示するプログラムを書こう
例 1 2 3 4 5 -> 4 2
4) スタック s の中の様子を表示する stack_display( ) 関数を書こう
5) スタックの渡し方をポインタに変更し stack_pop( ) と stack_drop( ) を同時に行う
int stack_pop(Stack * s)
を書こう。合わせて、Stack *stack_init(Stack *s )、Stack *stack_push(Stack *s ) も変更しよう。
(Stack stack_init(Stack s), Stack stack_push(Stack s) でも実装できる)