（答案作成中）C言語教室第23回 - スタックとキュー（キュー編）

2023年4月28日 22:06

試練の日々は続く、、、。
（課題22は先送りして、こちらから行きます。）

より複雑そうなキュー機能の実現を先回りしてトライしてみました。
諸兄姉からのツッコミは覚悟してます。

課題

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

https://note.com/kazushinakamura/n/n6eab5a1b1870?magazine_key=m07bb4da8df3e

配列を使って、キューを作成する

【設計方針】

配列（queue[]）を用意する（初期化する関数を設定する）
グローバル変数のqueue_top（次にキューを書き始めるアドレス）を用意しておく。
グローバル変数のqueue_bottom（次にキューを読み始めるアドレス）を用意しておく。
グローバル変数としてリングバッファの状況を示すis_reverseを用意しておく。
固定値Queue_Maxを設定しておく
初期値は以下の通り
1. queue_top = 0;
2. queue_bottom = 0;
3. is_reverse = false;
4. Queue_Maxは任意（仮に10)
enqueue()関数では、is_reeverse = falseの場合、
1. queue_topがQueue_Maxに達していなければ、queue[queue_top++]に、引数で与えられた値をセットするし、その旨表示する。
2. そうでなければ、queue_topに0 をセット、is_reverseにtrueをセットする。
3. is_reverse = trueの場合、
  1. queue_top < queue_bottomの場合、queue[queue_top++]に、引数で与えられた値をセットするし、その旨表示する。
  2. そうでなければ、queue[]は満杯なので、その旨エラー表示する。
dequeue()では、queue_bottom >=Queue_Maxの場合、
queue_bottomに0をセット、is_reverseにfalseをセットする。
1. is_reverse=falseの場合、
  1. queue_bottom < queue_topの場合、queue_bottom++を返す
  2. そうでなければ、queue[]は空なので、その旨表示する。
2. is_reverse= trueの場合、queue_bottom++を返す。

void * init_queue(int max_size);

引数；　キューのサイズを与える
戻り値；関数内で生成したキュー用配列を返す

void enqueue(int * queue, int val);

引数；キュー用の配列、キューに保管する整数
キューが満タンでenqueue()できない場合は、エラー表示して終了する。
そもそも、エラー表示するだけで、与えられた引数を破棄して処理を続行するような仕様で良いのかという懸念は放置している。

int dequeue(int * queue)

引数；キュー用の配列、
戻り値；取得した配列要素の要素番号（0 〜 (maz_size - 1))
queue[]が空で戻り値がない場合は、-1を返す。（要素番号のマイナス値はありえないため。当初は、取得した配列要素自体を戻り値とするようにコーディングしていたが、取得できなかったときに何を返すべきかに悩んだ結果、このような仕様に変更した。そうでなければ、関数の戻り値をbool値として取得の成否を返し、配列要素は参照渡しで返すべきかな？）

void print_queue(int * queue)

引数；キュー用の配列、
キューに保管されたデータを一覧表示する（デバグ用）

void dump_queue(int * queue)

引数；キュー用の配列、
キューの内容をダンプ表示する（デバグ用）

開発途中経過

ソースコードと実行結果はこちら。

#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 *a;
	a = (int*)malloc(sizeof(int) * queue_size);
	if (a == NULL) exit(0);

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

  return a;
}

void enqueue(int * queue, int val) {
  if (is_reverse == false) {
    if (queue_top < Queue_MAX) {
      queue[queue_top++] = val;
      printf("enqueued (%d)\n", val);
    } else {
      queue_top = 0;
      is_reverse = true;
    }
  }

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

int dequeue(int *queue) {

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

  if (is_reverse == false) {
    if (queue_bottom < queue_top) {
      return queue_bottom++;
    } else {
      printf("Queue is Empty!\n");
      return (-1);
    }
  }

  if (is_reverse == true) {
    return queue_bottom++;
  }
}

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 < 10; 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++) {
    rst = dequeue(queue);
    if (rst != (-1)) printf("dequeued (%d)\n", queue[rst]);
  }
  print_queue(queue);
  dump_queue(queue);

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


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


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

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

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

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

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


  printf("１0回取り出し--------------\n");
  for (cnt = 0; cnt < 10; cnt++) {
    rst = dequeue(queue);
    if (rst != (-1)) printf("dequeued (%d)\n", queue[rst]);
  }
  print_queue(queue);
  dump_queue(queue);


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


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


  free(queue);
  return (0);
}



jm3nrhMac-mini-:c akio$ gcc lesson23.c
lesson23.c:64:1: warning: non-void function does not return a value in all control paths [-Wreturn-type]
}
^
1 warning generated.
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: 01 02 03 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 04 05 06 07 08 09 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 

１0回取り出し--------------
dequeued (10)
dequeued (13)
dequeued (14)
dequeued (15)
dequeued (18)
dequeued (19)
dequeued (20)
dequeued (21)
dequeued (22)
dequeued (23)

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

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

print_queue: 25 26 27 
queue dump: 26 27 15 18 19 20 21 22 23 25 

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

print_queue: 
queue dump: 26 27 15 18 19 20 21 22 23 25 

jm3nrhMac-mini-:c akio$

しめしめ、うまく行ってるみたい。
念の為、CharGPT様にお伺いを立ててみた。
ところが、、、


下記のコードの潜在的なバグについて述べよ
（以下、上記のコードを指定しているため省略）

1回目

このコードの潜在的なバグはいくつかあります。以下に説明します。 dequeue()関数の戻り値が間違っています。現在の実装では、dequeue()関数はキューの先頭の要素を返すべきですが、実際には先頭の要素のインデックスを返しています。そのため、実際には先頭の要素の値が消去されたかどうかを確認するために、追加のステップが必要になります。 is_reverseフラグがうまく機能していないため、キューに要素が追加されない場合があります。特に、queue_topとqueue_bottomの値が一致する場合に問題が発生します。この場合、enqueue()関数は何もしないため、キューに要素が追加されません。この問題を解決するには、queue_topとqueue_bottomの値が等しい場合に is_reverseフラグをトグルする必要があります。 enqueue()関数の2番目の条件式は、is_reverseフラグが真である場合に実行されるべきですが、現在の実装ではqueue_topがqueue_bottomより小さい場合に実行されます。これは、queue_topがQueue_MAXより大きい場合には動作しません。 dump_queue()関数は、キューのサイズがQueue_MAXより大きい場合には機能しません。 main()関数内のいくつかのループで、変数cntが未初期化で使用されています。これは、C言語の仕様で未初期化の変数を使用すると不定の動作を引き起こす可能性があるため、バグの原因となる可能性があります。

2回目

2 / 2

このコードの潜在的なバグは以下の通りです。Queue_MAXとqueue_sizeは同じ値であり、Queue_MAXがqueue_sizeより大きい場合、初期化されないエリアが残ってしまう。
read_pointはグローバル変数であり、異なる関数で使用される可能性がある。これは、現在のキューの状態を誤って示す可能性がある。
is_reverseがtrueに設定された場合、enqueueはqueue_top < queue_bottomの条件に基づいて値を追加し続ける。これは、queue_topがqueue_bottomを超えた後も続けられ、バッファの上書きとデータの損失を引き起こす。
dequeue関数は、実際のキューデータではなく、queue_bottomを返します。これは、実際のキューデータが後で破棄され、再使用された場合に問題が発生する可能性があります。
print_queue関数で、最初にエラーを引き起こす可能性のあるキューの状態をチェックする前に、read_pointがqueue_bottomに初期化されるため、誤った結果が表示される可能性がある。

これらの問題は、プログラムの安定性と信頼性に影響を与える可能性があります。修正する必要があります。

3回目

3 / 3

このコードには、いくつかの潜在的なバグがあります。配列の境界チェック不足配列の先頭または末尾に到達したとき、境界チェックが不足しているため、エラーが発生する可能性があります。配列サイズが10であるため、Queue_MAX変数を使用して配列のサイズを指定しているが、関数の実装では、Queue_MAX変数に基づく境界チェックが欠落している。
ポインタの不適切な使用 enqueue関数において、queue_top、queue_bottom、is_reverse、queueの4つの変数をグローバル変数として定義しているため、複数のqueueを同時に操作することができません。この問題を解決するために、enqueue関数とdequeue関数でポインタを使用することができます。
dequeue関数における戻り値の不適切な使用 dequeue関数は、dequeued要素の値を返すことができますが、実装では、配列のインデックスを返しています。これにより、queue配列の要素が変更された場合、以前の返された値が不正確になります。
enqueue関数でqueue_topの更新の不適切な使用 queue_topの値を更新するために、post-increment演算子を使用しています。しかし、post-increment演算子を使用すると、queue_topの現在の値が使用されてから変更されるため、間違った値がqueue_topに格納される可能性があります。
is_reverse変数の使用 is_reverse変数は、queue_topがQueue_MAXを超えたときに使用され、キューがリバースモードに移行することを示します。しかし、この実装では、queue_topとqueue_bottomの関係に基づく境界条件を使用する必要があるため、正しい機能を提供しません。
print_queue関数でのポインタの不適切な使用 print_queue関数は、queue配列の要素を読み取るためにread_point変数を使用しています。しかし、ポインタを更新しているだけで、queue配列の要素を読み取るために使用しているわけではありません。したがって、この実装では、print_queue関数は正確な結果を返しません。

4回目

このコードの潜在的なバグはいくつかあります。主な問題は、リングバッファの実装にあります。リングバッファを使用することにより、Queue_MAXまで要素を格納できますが、先頭ポインタと末尾ポインタが常に現在のキューの要素数を追跡していないため、キューの状態を正確に追跡することができません。そのため、要素をキューに追加するときに、既にキューがいっぱいであると判断されている場合でも、新しい要素を追加しようとします。また、キューが空であると判断される場合でも、実際にはキューに要素がある場合があります。具体的には、次のような問題が発生する可能性があります。enqueue()関数にバグがあります。以下のような状況で、新しい要素がキューに追加されず、 "Queue is FULL"のエラーメッセージが表示される可能性があります。
キューが最初に初期化されたときに、queue_top = Queue_MAX
キューが逆順モードである場合、queue_top = queue_bottom
キューが通常のモードである場合、queue_top = Queue_MAXで、キューがいっぱいである場合、is_reverseがtrueに設定されます。

これらの状況では、新しい要素をキューに追加する前に、queue_topが再初期化されないため、キューがいっぱいであると誤って判断されることがあります。dequeue()関数にバグがあります。以下のような状況で、キューが空であると判断され、 "Queue is Empty"のエラーメッセージが表示される可能性があります。
キューが最初に初期化されたときに、queue_bottom = 0
キューが逆順モードである場合、queue_bottom = queue_top

これらの状況では、キューに要素があるにもかかわらず、新しい要素をキューに追加する前に、queue_bottomが再初期化されないため、キューが空であると誤って判断されることがあります。dequeue()関数は、要素の値を返す代わりに、要素のインデックスを返します。これは、ユーザーにとって使いにくく、プログラム全体で混乱を招く可能性があります。dequeue()関数は、キューから要素を

5回目

5 / 5

このコードの潜在的なバグはいくつかあります。dequeue()関数が、要素を取り出すだけでなく、要素の値を返すべきところで、インデックスを返しています。これにより、要素が0である場合、dequeue()が0を返すため、これをエラーの指標として解釈する可能性があります。
enqueue()関数で、queue_topの値がキューのサイズより大きい場合、インデックスを0にリセットしています。しかし、queue_topの後ろには他の値が存在しているため、この値を上書きする可能性があります。また、キューがすでに反転している場合、新しい要素を追加する前に、queue_topの値がqueue_bottomの値を超えていることを確認する必要があります。
print_queue()関数は、キューの逆順を適切に処理していません。is_reverseフラグによって、キューが反転しているかどうかが判断されますが、逆順の場合、queue_topの前にある要素がキューの末尾にあります。dump_queue()関数も、キューの反転を考慮していません。
dequeue()関数は、要素が空の場合に-1を返すように設計されています。しかし、これはキュー内の可能な要素の1つであるため、正しいエラー指標ではありません。
enqueue()関数は、Queue_MAXという値をハードコーディングしていますが、これはマクロで定義されています。また、main()関数でキューを初期化するときに、Queue_MAXの値を使用しているため、これらの定義が一致している必要があります。
init_queue()関数で、malloc()が失敗した場合にプログラムが終了しますが、エラーメッセージは表示されません。また、メモリを解放する方法がありません。
一部の関数で使用されるグローバル変数が、他の関数からアクセスできるため、プログラムの状態が混乱する可能性があります。これらの変数は、関数内で宣言されたローカル変数に置き換えることができます。

聞くたびに異なる回答をくれるのはいいんだけど、、、
ご節ご尤もと思うところと、それはないんじゃないかと思うところと、、、

疲れた。

今日はこれでおしまい。
一晩寝てから見直します。

おやすみなさい。

ここまで読んでいただき、有り難うございました。

この記事が参加している募集

#AIとやってみた

27,969件

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