応用情報技術者試験 - SE娘の剣 -

応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。少しずつ追記していきます

スタックとキューの問題

H18春FE午前
問12 空の状態のキューとスタックの二つのデータ構造がある。次の手続を順に実行した場合,変数xに代入されるデータはどれか。ここで,
データ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) と書くと、y をスタックに挿入できる
char pop();    //スタック(の最後)からデータを取り出す関数の宣言。 y=push() と書くと、y にスタックから取り出した値を取得できる
int enq(char data);  //キュー(の最後)にデータを挿入する関数の宣言。 enq(y) と書くと、y をキューに挿入できる
char deq();    //キュー(の先頭)からデータを取り出す関数の宣言。 y=deq() と書くと、y にキューから取り出した値を取得できる

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());  //2つの処理を1行で行っている。(1) y=pop():スタック(の最後)からデータを取り出して (2) 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()); //2つの処理を1行で行っている。(1)y=deq():キュー(の先頭)からデータを取り出して、(2)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; //追加前のスタックのサイズは、スタックの最後に追加するデータのインデックス(0からはじまる)に等しい。そのインデックスが指す位置にデータをセットし、スタックのサイズを1つ増やす。
 return s.size; //挿入後のスタックのサイズを返す
}

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

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

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

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

 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番目の配列に値をコピーする。(1つ左につめる)
 }
 
 q.size--; //キューのサイズを1つ小さくする

 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"); //改行
}