見出し画像

（答案提出）C言語教室 第23回 - スタックとキュー（キュー編、その３）

Akio van der Meer

C言語教室 第23回の課題を提出したと思っていたら、キュー編はまだ「答案作成中」のままだったことに気付く。

姉弟子のAyumiさんから、無限にenqueue()、dequeue()が実行される旨ご指摘いただき、ここはちゃんと、それぞれの処理が実行不可だった場合には明示的にエラーを返すように仕様を変更することにします。呼ぶ側でエラーを受け取ったのちにどのように対処するかを判断して貰います。

注意！　追記を参照ください。

課題

2. 配列を使って、キューを書いてください。キューの初期化する関数で配列の大きさを指定してください。可能であれば配列をリングバッファとして循環して使えるようにしてください。

https://note.com/kazushinakamura/n/n6eab5a1b1870

ソースコード

/**********************************************************************
	lesson23　Configure a queue with an array
		by Akio van der Meer

[変更履歴]
 (無印)  記事初投稿時のコード
 r1.1	bool dequeue(int *queue, int *val)の変更
	取得したqueueの値は、参照渡し（*val）で返す
	dequeue()した配列要素は、0にリセットする
	戻り値は、実行結果の論理値（成功；true / 失敗；false）とする
 r1.2	bool enqueue(int *queue, int val)の変更
 	セットしたqueueの値の表示機能を廃止
	戻り値は、実行結果の論理値（成功；true / 失敗；false）とする

**********************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define Queue_MAX 10
int queue_top = 0;
int queue_bottom = 0;
int read_point = 0;
bool is_reverse = false;

int * init_queue(int queue_size) {
  int *arry;
	arry = (int*)malloc(sizeof(int) * queue_size);
	if (arry == NULL) exit(0);

  for (int i = 0; i < queue_size; i++) {
    arry[i] = 0;
  }
  return arry;
}

bool enqueue(int * queue, int val) {
  if (is_reverse == false) {
    if (queue_top < Queue_MAX) {
      queue[queue_top++] = val;
    } else {
      queue_top = 0;
      is_reverse = true;
    }
  }

  if (is_reverse == true) {
    if (queue_top < queue_bottom) {
      queue[queue_top++] = val;
    } else {
      printf("Queue is FULL! (%d has not been queued.)\n", val);
      return false;
    }
  }

  return true;
}

bool dequeue(int *queue, int *val) {
  *val = 0;

  if (queue_bottom >= Queue_MAX) {
    queue_bottom = 0;
    is_reverse = false;
  }

  if (is_reverse == false) {
    if (queue_bottom < queue_top) {
        *val = queue[queue_bottom];
        queue[queue_bottom++] = 0;
        return true;
    } else {
      printf("Queue is Empty!\n");
      return false;
    }
  } else  {
    *val = queue[queue_bottom];
    queue[queue_bottom++] = 0;
    return true;
  }
}

void print_queue(int * queue) {
  read_point = queue_bottom;

  printf("\nprint_queue: ");

  if (is_reverse == true) {
    while (read_point < Queue_MAX) {
      printf("%02d ",queue[read_point++]);
    }

    read_point = 0;
    while (read_point < queue_top) {
      printf("%02d ",queue[read_point++]);
    }
  }

  if (is_reverse == false) {
    while (read_point < queue_top) {
      printf("%02d ",queue[read_point++]);
    }
  }

  printf("\n");
}

void dump_queue(int * queue) {
  printf("queue dump: ");
  for (int i = 0; i < Queue_MAX; i++) {
    printf("%02d ", queue[i]);
  }
  printf("\n\n");
}

int main() {
  int cnt = 0;
  int rst = 0;
  int sample = 1;
  int *queue;
  queue = init_queue(Queue_MAX);

  printf("初期状態--------------\n");
  print_queue(queue);
  dump_queue(queue);

  printf("３回 取り出し--------------\n");
  for (cnt = 0; cnt < 3; cnt++) {
    if (dequeue(queue, &rst) == true) printf("dequeued (%d)\n", rst);
  }
  print_queue(queue);
  dump_queue(queue);

  printf("4回追加--------------\n");
  for (cnt = 0; cnt < 4; cnt++) {
    if (enqueue(queue, sample) == true) printf("enqueued (%d)\n", sample);  
    sample++;  
  }
  print_queue(queue);
  dump_queue(queue);

  printf("4回追加--------------\n");
  for (cnt = 0; cnt < 4; cnt++) {
    if (enqueue(queue, sample) == true) printf("enqueued (%d)\n", sample);  
    sample++;  
  }
  print_queue(queue);
  dump_queue(queue);

  printf("4回追加--------------\n");
  for (cnt = 0; cnt < 4; cnt++) {
    if (enqueue(queue, sample) == true) printf("enqueued (%d)\n", sample);  
    sample++;  
  }
  print_queue(queue);
  dump_queue(queue);

  printf("３回 取り出し--------------\n");
  for (cnt = 0; cnt < 3; cnt++) {
    if (dequeue(queue, &rst) == true) printf("dequeued (%d)\n", rst);
  }
  print_queue(queue);
  dump_queue(queue);

  printf("５回追加--------------\n");
  for (cnt = 0; cnt < 5; cnt++) {
    if (enqueue(queue, sample) == true) printf("enqueued (%d)\n", sample);  
    sample++;  
  }
  print_queue(queue);
  dump_queue(queue);

  printf("6回取り出し--------------\n");
  for (cnt = 0; cnt < 6; cnt++) {
    if (dequeue(queue, &rst) == true) printf("dequeued (%d)\n", rst);
  }
  print_queue(queue);
  dump_queue(queue);

  printf("7回追加--------------\n");
  for (cnt = 0; cnt < 7; cnt++) {
    if (enqueue(queue, sample) == true) printf("enqueued (%d)\n", sample);  
    sample++;  
  }
  print_queue(queue);
  dump_queue(queue);

  printf("11回取り出し--------------\n");
  for (cnt = 0; cnt < 11; cnt++) {
    if (dequeue(queue, &rst) == true) printf("dequeued (%d)\n", rst);
  }
  print_queue(queue);
  dump_queue(queue);

  printf("3回追加--------------\n");
  for (cnt = 0; cnt < 3; cnt++) {
    if (enqueue(queue, sample) == true) printf("enqueued (%d)\n", sample);  
    sample++;  
  }
  print_queue(queue);
  dump_queue(queue);

  printf("4回取り出し--------------\n");
  for (cnt = 0; cnt < 4; cnt++) {
    if (dequeue(queue, &rst) == true) printf("dequeued (%d)\n", rst);
  }
  print_queue(queue);
  dump_queue(queue);


  //終了処理
  free(queue);
  return (0);
}

実行結果

jm3nrhMac-mini-:c akio$ gcc lesson23_r1.2.c
jm3nrhMac-mini-:c akio$ ./a.out
初期状態--------------

print_queue: 
queue dump: 00 00 00 00 00 00 00 00 00 00 

３回 取り出し--------------
Queue is Empty!
Queue is Empty!
Queue is Empty!

print_queue: 
queue dump: 00 00 00 00 00 00 00 00 00 00 

4回追加--------------
enqueued (1)
enqueued (2)
enqueued (3)
enqueued (4)

print_queue: 01 02 03 04 
queue dump: 01 02 03 04 00 00 00 00 00 00 

4回追加--------------
enqueued (5)
enqueued (6)
enqueued (7)
enqueued (8)

print_queue: 01 02 03 04 05 06 07 08 
queue dump: 01 02 03 04 05 06 07 08 00 00 

4回追加--------------
enqueued (9)
enqueued (10)
Queue is FULL! (11 has not been queued.)
Queue is FULL! (12 has not been queued.)

print_queue: 01 02 03 04 05 06 07 08 09 10 
queue dump: 01 02 03 04 05 06 07 08 09 10 

３回 取り出し--------------
dequeued (1)
dequeued (2)
dequeued (3)

print_queue: 04 05 06 07 08 09 10 
queue dump: 00 00 00 04 05 06 07 08 09 10 

５回追加--------------
enqueued (13)
enqueued (14)
enqueued (15)
Queue is FULL! (16 has not been queued.)
Queue is FULL! (17 has not been queued.)

print_queue: 04 05 06 07 08 09 10 13 14 15 
queue dump: 13 14 15 04 05 06 07 08 09 10 

6回取り出し--------------
dequeued (4)
dequeued (5)
dequeued (6)
dequeued (7)
dequeued (8)
dequeued (9)

print_queue: 10 13 14 15 
queue dump: 13 14 15 00 00 00 00 00 00 10 

7回追加--------------
enqueued (18)
enqueued (19)
enqueued (20)
enqueued (21)
enqueued (22)
enqueued (23)
Queue is FULL! (24 has not been queued.)

print_queue: 10 13 14 15 18 19 20 21 22 23 
queue dump: 13 14 15 18 19 20 21 22 23 10 

11回取り出し--------------
dequeued (10)
dequeued (13)
dequeued (14)
dequeued (15)
dequeued (18)
dequeued (19)
dequeued (20)
dequeued (21)
dequeued (22)
dequeued (23)
Queue is Empty!

print_queue: 
queue dump: 00 00 00 00 00 00 00 00 00 00 

3回追加--------------
enqueued (25)
enqueued (26)
enqueued (27)

print_queue: 25 26 27 
queue dump: 26 27 00 00 00 00 00 00 00 25 

4回取り出し--------------
dequeued (25)
dequeued (26)
dequeued (27)
Queue is Empty!

print_queue: 
queue dump: 00 00 00 00 00 00 00 00 00 00 

jm3nrhMac-mini-:c akio$ gcc lesson23_r1.2.c
jm3nrhMac-mini-:c akio$ ./a.out
初期状態--------------

print_queue: 
queue dump: 00 00 00 00 00 00 00 00 00 00 

３回 取り出し--------------
Queue is Empty!
Queue is Empty!
Queue is Empty!

print_queue: 
queue dump: 00 00 00 00 00 00 00 00 00 00 

4回追加--------------
enqueued (1)
enqueued (2)
enqueued (3)
enqueued (4)

print_queue: 01 02 03 04 
queue dump: 01 02 03 04 00 00 00 00 00 00 

4回追加--------------
enqueued (5)
enqueued (6)
enqueued (7)
enqueued (8)

print_queue: 01 02 03 04 05 06 07 08 
queue dump: 01 02 03 04 05 06 07 08 00 00 

4回追加--------------
enqueued (9)
enqueued (10)
Queue is FULL! (11 has not been queued.)
Queue is FULL! (12 has not been queued.)

print_queue: 01 02 03 04 05 06 07 08 09 10 
queue dump: 01 02 03 04 05 06 07 08 09 10 

３回 取り出し--------------
dequeued (1)
dequeued (2)
dequeued (3)

print_queue: 04 05 06 07 08 09 10 
queue dump: 00 00 00 04 05 06 07 08 09 10 

５回追加--------------
enqueued (13)
enqueued (14)
enqueued (15)
Queue is FULL! (16 has not been queued.)
Queue is FULL! (17 has not been queued.)

print_queue: 04 05 06 07 08 09 10 13 14 15 
queue dump: 13 14 15 04 05 06 07 08 09 10 

6回取り出し--------------
dequeued (4)
dequeued (5)
dequeued (6)
dequeued (7)
dequeued (8)
dequeued (9)

print_queue: 10 13 14 15 
queue dump: 13 14 15 00 00 00 00 00 00 10 

7回追加--------------
enqueued (18)
enqueued (19)
enqueued (20)
enqueued (21)
enqueued (22)
enqueued (23)
Queue is FULL! (24 has not been queued.)

print_queue: 10 13 14 15 18 19 20 21 22 23 
queue dump: 13 14 15 18 19 20 21 22 23 10 

11回取り出し--------------
dequeued (10)
dequeued (13)
dequeued (14)
dequeued (15)
dequeued (18)
dequeued (19)
dequeued (20)
dequeued (21)
dequeued (22)
dequeued (23)
Queue is Empty!

print_queue: 
queue dump: 00 00 00 00 00 00 00 00 00 00 

3回追加--------------
enqueued (25)
enqueued (26)
enqueued (27)

print_queue: 25 26 27 
queue dump: 26 27 00 00 00 00 00 00 00 25 

4回取り出し--------------
dequeued (25)
dequeued (26)
dequeued (27)
Queue is Empty!

print_queue: 
queue dump: 00 00 00 00 00 00 00 00 00 00 

jm3nrhMac-mini-:c akio$


追記（2023.05.01)

上記のコード（lesson23_r1.2.c2）には、ある条件下で無条件にdequeue()できてしまうという致命的なバグがあります。

詳細は以下の記事を参照ください。
https://note.com/jm3nrh/n/ndc6096e79e05


いいなと思ったら応援しよう！

Akio van der Meer
これまでの収益は全て、それを必要としておられる方々へ、支援機関を通して寄付させていただきました。この活動は今後も継続したいと思っています。引き続きよろしくお願いいたします。