H18春FE午前
問12 空の状態のキューとスタックの二つのデータ構造がある。次の手続を順に実行した場合,変数ｘに代入されるデータはどれか。ここで,
データyをスタックに挿入することをpush(y),
スタックからデータを取り出すことをpop(),
データyをキューに挿入することをenq(y),
キューからデータを取り出すことをdeq() ,
とそれぞれ表す。

push(a)
push(b)
enq(pop())
enq(c)
push(d)
push(deq())
x←pop()

ア a　　イ b　　ウ c　　エ d
正解は、イのbです。

実行結果を先に書きます。実際のプログラムは後半に記載します。
c:\pg>stack.exe
初期状態
スタックの状態：
キューの状態：

push(a) データ a をスタック（の最後）に挿入
スタックの状態：[a]
キューの状態：

push(b)　データ b をスタック（の最後）に挿入
スタックの状態：[a][b]
キューの状態：

enq(pop())　スタック（の最後）からデータを取り出して、それをキュー（の最後）に挿
入
スタックの状態：[a]
キューの状態：[b]

enq(c)　データ c をキュー（の最後）に挿入
スタックの状態：[a]
キューの状態：[b][c]

push(d)　データ d をスタック（の最後）に挿入
スタックの状態：[a][d]
キューの状態：[b][c]

push(deq())　キュー（の先頭）からデータを取り出して、スタック（の最後）に挿入
スタックの状態：[a][d][b]
キューの状態：[c]

x = pop()　スタック（の最後）からデータを取り出したデータを x とする
x の値： b
スタックの状態：[a][d]
キューの状態：[c]
実際のプログラムはこちら
#include <stdio.h>
#define MAX_SIZE 256 //スタックとキューの容量

//データを保存するコンテナの構造体(struct)の型を定義する
struct container
{
 char data_array[MAX_SIZE]; //CHAR型の配列。サイズはMAX_SIZEで定義された数（＝256）
 int size;     //データの個数（サイズ）を把持する変数。上記の配列で最初から何番目までのデータが使われているかを記憶する。
};

int push(char data); //スタック（の最後）にデータを挿入する関数の宣言。 push(y) と書くと、ｙ をスタックに挿入できる
char pop();    //スタック（の最後）からデータを取り出す関数の宣言。 y=push() と書くと、ｙ にスタックから取り出した値を取得できる
int enq(char data);  //キュー（の最後）にデータを挿入する関数の宣言。 enq(y) と書くと、ｙ をキューに挿入できる
char deq();    //キュー（の先頭）からデータを取り出す関数の宣言。 y=deq() と書くと、ｙ にキューから取り出した値を取得できる

void printStack();  //スタックの状態を表示する関数の宣言。 printStack() と書くと、画面にスタックの状態が表示される
void printQueue();  //キューの状態を表示する関数の宣言。 printQueue() と書くと、画面にキューの状態が表示される

struct container q;  //スタックのデータを保存する構造体の変数を定義（メモリ上に確保）
struct container s;  //キューのデータを保存する構造体の変数を定義（メモリ上に確保）

int main() //プログラムのエントリーポイント（最初に呼ばれる関数）
{
 //データの初期化
 q.size = 0; //サイズをゼロに初期化
 s.size = 0; //サイズをゼロに初期化

 printf("初期状態\n"); //メッセージを表示して改行
 printStack();   //スタックの状態を表示
 printQueue();   //キューの状態を表示
 printf("\n");   //改行

 printf("push(a) データ a をスタック（の最後）に挿入\n"); //メッセージを表示して改行
 ////
 push('a');  //char型のデータ a をスタック（の最後）に挿入
 ////
 printStack(); //スタックの状態を表示
 printQueue(); //キューの状態を表示
 printf("\n");

 printf("push(b)　データ b をスタック（の最後）に挿入\n"); //メッセージを表示して改行
 ////
 push('b');  //char型のデータ b をスタック（の最後）に挿入
 ////
 printStack(); //スタックの状態を表示
 printQueue(); //キューの状態を表示
 printf("\n");

 printf("enq(pop())　スタック（の最後）からデータを取り出して、それをキュー（の最後）に挿入\n"); //メッセージを表示して改行
 ////
 enq(pop());  //２つの処理を１行で行っている。（１） y=pop()：スタック（の最後）からデータを取り出して　（２） enq（y）：それをキュー（の最後）に挿入
 ////
 printStack(); //スタックの状態を表示
 printQueue(); //キューの状態を表示
 printf("\n");

 printf("enq(c)　データ c をキュー（の最後）に挿入\n"); //メッセージを表示して改行
 ////
 enq('c');  //char型のデータ c をキュー（の最後）に挿入
 ////
 printStack(); //スタックの状態を表示
 printQueue(); //キューの状態を表示
 printf("\n");

 printf("push(d)　データ d をスタック（の最後）に挿入\n"); //メッセージを表示して改行
 ////
 push('d');  //char型のデータ d をスタック（の最後）に挿入
 ////
 printStack(); //スタックの状態を表示
 printQueue(); //キューの状態を表示
 printf("\n");

 printf("push(deq())　キュー（の先頭）からデータを取り出して、スタック（の最後）に挿入\n"); //メッセージを表示して改行
 ////
 push(deq()); //２つの処理を１行で行っている。（１）y=deq()：キュー（の先頭）からデータを取り出して、（２）push(y)：スタック（の最後）に挿入
 ////
 printStack(); //スタックの状態を表示
 printQueue(); //キューの状態を表示
 printf("\n");

 printf("x = pop()　スタック（の最後）からデータを取り出したデータを x とする\n"); //メッセージを表示して改行
 ////
 char x = pop();
 printf("x の値： %c\n", x); //取得した値（char型）を表示して改行
 ////
 printStack(); //スタックの状態を表示
 printQueue(); //キューの状態を表示
 printf("\n"); //改行

    return 0;
}

//スタック（の最後）にデータを挿入する関数の定義
//引数：(char)挿入するデータ
//戻り値：(int)挿入後のサイズ
//但し、スタックの容量を超えたら追加できないので、-1を返す。
int push(char data)
{
 if (s.size == MAX_SIZE)
  return -1; //スタックの容量を超えたら追加できない。

 s.data_array[s.size++] = data; //追加前のスタックのサイズは、スタックの最後に追加するデータのインデックス（０からはじまる）に等しい。そのインデックスが指す位置にデータをセットし、スタックのサイズを１つ増やす。
 return s.size; //挿入後のスタックのサイズを返す
}

//スタック（の最後）からデータを取り出す関数の定義
//戻り値：(char)取り出したデータ
//但し、スタックが空の場合は、-1を返す。
char pop()
{
 if (s.size == 0)
  return -1; //スタックが空の場合は、-1を返す。

 char ret = s.data_array[--s.size]; //スタックのサイズを１つ減らすと、その値はスタックの最後のデータのインデックス（０から始まる）と等しくなるので、配列からそのインデックスが指す値を取り出す。
 return ret;  //スタック（の最後）から取り出したデータを返す
}

//キュー（の最後）にデータを挿入する関数の定義
//引数：(char)挿入するデータ
//戻り値：(int)挿入後のサイズ
//但し、キューの容量を超えたら追加できないので、-1を返す。
int enq(char data)
{
 if (q.size == MAX_SIZE)
  return -1; //キューの容量を超えたら追加できない。

 q.data_array[q.size++] = data; //追加前のキューのサイズは、データを追加する配列のインデックス（０からはじまる）に等しい。そのインデックスが指す位置にデータをセットし、キューのサイズを１つ増やす。

 return q.size; //挿入後のキューのサイズを返す
}

//キュー（の先頭）からデータを取り出す関数の定義
//戻り値：(char)取り出したデータ
//但し、キューが空の場合は、-1を返す。
char deq()
{
 int i;

 if (q.size == 0)
  return -1; //キューが空の場合は、-1を返す。

 char ret = q.data_array[0]; //キュー（の先頭）からデータを取り出す

 //データを奥につめる
 for (i = 0; i < q.size; i++) //キューの先頭から最後までループ
 {
  q.data_array[i] = q.data_array[i + 1]; //i+1番目の配列から、i番目の配列に値をコピーする。（１つ左につめる）
 }
 
 q.size--; //キューのサイズを１つ小さくする

 return ret; //スタック（の最後）から取り出したデータを返す
}

//スタックの状態を表示する関数の定義
void printStack()
{
 printf("スタックの状態：");
 int size = s.size;
 for (int i = 0; i < size; i++) //スタックの先頭から最後までループ
 {
  printf("[%c]", s.data_array[i]); //データ（CHAR型）の値を表示
 }
 printf("\n"); //改行
}

//キューの状態を表示する関数の定義
void printQueue()
{
 printf("キューの状態：");
 int size = q.size;
 for (int i = 0; i < size; i++) //キューの先頭から最後までループ
 {
  printf("[%c]", q.data_array[i]); //データ（CHAR型）の値を表示
 }
 printf("\n"); //改行
}