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

  1. リストによるスタック
  2. リストによるキュー

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

課題1: リストによるスタック

リストを用いて，整数の値を蓄積するスタックを実現したソースコード prog7-1.c を作成する．

ここでは，リストを表現する構造体を以下のように定義する． 

struct element {
    int value;
    struct element *next;
};

また，リストを用いたスタックを以下の構造体で定義する． 

struct stack {
    struct element *top;
    int size;
};
この構造体は，整数の値を top が先頭の要素を指すリストに格納する．

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

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

さらに，スタックを操作する以下に示す4つの関数を用意する．

(5) stack に整数の値 value を挿入する．
void push(struct stack *stack, struct element *elem);
(6) stack から整数の値を取り出す．スタックが空の場合は NULL を返す．
struct element *pop(struct stack *stack);
(7) stack から次に取り出される整数の値を取得する(整数の値は取り出さない)．スタックが空の場合は NULL を返す．
struct element *peek(struct stack *stack);
(8) stack が空かどうかを検査する．空の場合は 1，空でない場合は 0 を返す．
int is_empty(struct stack *stack);

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

課題2: リストによるキュー

リストを用いて，整数の値を蓄積するキューを実現したソースコード prog7-2.c を作成する．

ここでは，リストを表現する構造体を以下のように定義する． 

struct element {
    int value;
    struct element *next;
};

また，リストを用いたキューを以下の構造体で定義する． 

struct queue {
    struct element *top;
    struct element *rear;
    int size;
};
この構造体は，整数の値を top が先頭の要素，rearが末尾の要素を指すリストに格納する．

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

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

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

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

上記の8つの関数を持つ prog7-2.c を作成せよ．

課題3:

3種類の括弧'{ }', '[ ]', '( )'を含む文字列 text に対して，左括弧と右括弧の対応が正しいかどうかを検査する関数 

int check(char *text);
を持つソースコード prog7-3.c を作成する．

対応が正しいとは，同じ種類の左括弧と右括弧がネストしている(入れ子構造になっている)ことを指す．対応が正しい場合には 1，対応が正しくない場合には 0 を返す．


スタック(配列でもリストでもよい)を用いて，prog7-3.c を作成せよ．その際，あらかじめ用意した5つのテスト関数に加えて，新たなテスト関数を追加せよ．
Go to Top