第6回では，以下の項目に関して学ぶ．

  1. 配列によるスタック
  2. 配列によるキュー

課題のソースコードのテンプレート:

課題1: 配列によるスタック

スタック(stack)とは，要素を一時的に蓄積するデータ構造の一つである．要素は後入れ先出し(LIFO: Last In First Out)で行われる．よって，最後に挿入された要素が最初に取り出される．

ここでは，以下に示す構造体を用いて，整数の値を蓄積するスタックを実現したソースコード prog6-1.c を作成する． 

struct stack {
    int data[STACK_SIZE];
    int top;
};
この構造体は，整数の値を配列 data[] に格納する．data[] に対して，top は次に整数の値が格納される位置を指す．

スタックの例を図6.1に示す．


図6.1: スタックの例

いま，スタックを実現するために，以下に示す3つの関数を用意する．

(1) 空のスタックを生成する．
struct stack *create_stack();
(2) stack に格納されている整数の値を挿入した順番に画面に表示する．
void print_stack(struct stack *stack);
(3) stack に格納されている要素の数を取得する．
int size_of_stack(struct stack *stack);

上記の3つの関数を持つ prog6-1.c を作成せよ．

本課題では，図6.1のスタックの利用例にあわせて，テスト関数 test1() がすでに用意されている．スタックの動作を検査するテストコードを prog6-1.c に追加せよ．

課題2: 配列によるスタックの操作

課題1で作成したソースコード prog6-1.c に対して，以下に示す4つの関数を追加したソースコード prog6-2.c を作成する．

(1) stack に整数の値 value を挿入する．挿入が成功した場合は1，失敗した場合は 0 を 返す
int push(struct stack *stack, int value);
(2) stack から整数の値を取り出す．スタックが空の場合は -1 を返す．
int pop(struct stack *stack);
(3) stack から次に取り出される整数の値を取得する(整数の値は取り出さない)．スタックが空の場合は -1 を返す．
int peek(struct stack *stack);
(4) stackが空かどうかを検査する．空の場合は 1，空でない場合は 0 を返す．
int is_empty(struct stack *stack);

上記の4つの関数とテストコードを含む prog6-2.c を作成せよ．

課題3: 配列によるキュー

キュー(queue)とは，要素を一時的に蓄積するデータ構造の一つである．要素は先入れ先出し(FIFO: First In First Out)で行われる．よって，最初に挿入された要素が最初に取り出される．

ここでは，以下に示す構造体を用いて，整数の値を蓄積するキューを実現したソースコード prog6-3.c を作成する． 

struct queue {
    int data[QUEUE_MAX_SIZE];
    int top;
    int rear;
};
この構造体は，整数の値を配列 data[] に格納する．data[] に対して，top はキューの先頭の位置，rear は次に整数の値が格納される位置を指す．

キューの例を図6.2に示す．


図6.2: キューの例

いま，キューを実現するために，以下に示す3つの関数を用意する．

(1) 空のキューを生成する．
struct queue *create_queue();
(2) queue に格納されている整数の値を挿入した順番に画面に表示する．
void print_queue(struct queue *queue);
(3) queue に格納されている要素の数を取得する．
int size_of_queue(struct queue *queue);

上記の3つの関数を持つ prog6-3.c を作成せよ．

本課題では，図6.3のキューの利用例にあわせて，テスト関数 test1() がすでに用意されている．キューの動作を検査するテストコードを prog6-3.c に追加せよ．

課題2: 配列によるキューの操作

課題3で作成したソースコード prog6-3.c に対して，以下に示す4つの関数を追加したソースコード prog6-2.c を作成する．

(1) queue に整数の値 value を挿入する．挿入が成功した場合は1，失敗した場合は 0 を 返す
int enqueue(struct queue *queue, int value);
(2) queue から整数の値を取り出す．キューが空の場合は -1 を返す．
int dequeue(struct queue *queue);
(3) queue から次に取り出される整数の値を取得する(整数の値は取り出さない)．キューが空の場合は -1 を返す．
int peek(struct queue *queue);
(4) queueが空かどうかを検査する．空の場合は 1，空でない場合は 0 を返す．
int is_empty(struct queue *queue);

上記の4つの関数とテストコードを含む prog6-4.c を作成せよ．

課題5: リングバッファを用いた配列によるキュー

課題4のようなキューの実現方法では，要素を格納する配列において，次に要素を挿入する位置が単調に増加する．このため，要素の挿入と取り出しを繰り返すと，要素を蓄積できる領域が足りなくなる．

これを回避するためには，キューから要素を取り出すごとに，配列に残っているすべての要素をキューの先頭側にずらせばよい．しかしながら，蓄積している要素の数が多い場合，この方法は効率が悪い．

そこで，配列内の要素をずらすことなく，キューを実現するために，リングバッファを導入する．リングバッファとは，配列の末尾がその先頭につながっているように見せかけるデータ構造である．

ここでは，以下に示す構造体を用いて，整数の値を蓄積するキューを実現したソースコード prog6-5.c を作成する． 

struct queue {
    int data[QUEUE_SIZE];
    int top;
    int rear;
    int num;
};
この構造体は，整数の値をリングバッファである配列 data[] に格納する．data[] に対して，top はキューの先頭の位置，rear は次に整数の値が格納される位置を指す．num はキューに蓄積されている要素の数を指す．

いま，リングバッファを導入したキューを実現するために，以下に示す3つの関数を用意する．

(1) 空のキューを生成する．
struct queue *create_queue();
(2) queue に格納されている整数の値を挿入した順番に画面に表示する．
void print_queue(struct queue *queue);
(3) queue に格納されている要素の数を返す．
int size_of_queue(struct queue *queue);

さらに，キューを操作する以下に示す4つの関数を用意する．

(4) queue に整数の値 value を挿入する．挿入が成功した場合は1，失敗した場合は 0 を 返す
int enqueue(struct queue *queue, int value);
(5) queue から整数の値を取り出す．キューが空の場合は -1 を返す．
int dequeue(struct queue *queue);
(6) queue から次に取り出される整数の値を取得する(整数の値は取り出さない)．キューが空の場合は -1 を返す．
int peek(struct queue *queue);
(7) queueが空かどうかを検査する．空の場合は 1，空でない場合は 0 を返す．
int is_empty(struct queue *queue);

上記の7つの関数とテストコードを含む prog6-5.c を作成せよ．
Go to Top