(答案作成中)C言語教室 第23回 - スタックとキュー(キュー編)
試練の日々は続く、、、。
(課題22は先送りして、こちらから行きます。)
より複雑そうなキュー機能の実現を先回りしてトライしてみました。
諸兄姉からのツッコミは覚悟してます。
課題
配列を使って、キューを作成する
【設計方針】
配列(queue[])を用意する(初期化する関数を設定する)
グローバル変数のqueue_top(次にキューを書き始めるアドレス)を用意しておく。
グローバル変数のqueue_bottom(次にキューを読み始めるアドレス)を用意しておく。
グローバル変数としてリングバッファの状況を示すis_reverseを用意しておく。
固定値Queue_Maxを設定しておく
初期値は以下の通り
queue_top = 0;
queue_bottom = 0;
is_reverse = false;
Queue_Maxは任意(仮に10)
enqueue()関数では、is_reeverse = falseの場合、
queue_topがQueue_Maxに達していなければ、queue[queue_top++]に、引数で与えられた値をセットするし、その旨表示する。
そうでなければ、queue_topに0 をセット、is_reverseにtrueをセットする。
is_reverse = trueの場合、
queue_top < queue_bottomの場合、queue[queue_top++]に、引数で与えられた値をセットするし、その旨表示する。
そうでなければ、queue[]は満杯なので、その旨エラー表示する。
dequeue()では、queue_bottom >=Queue_Maxの場合、
queue_bottomに0をセット、is_reverseにfalseをセットする。is_reverse=falseの場合、
queue_bottom < queue_topの場合、queue_bottom++を返す
そうでなければ、queue[]は空なので、その旨表示する。
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("3回 取り出し--------------\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("3回 取り出し--------------\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("5回追加--------------\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("10回取り出し--------------\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
3回 取り出し--------------
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
3回 取り出し--------------
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
5回追加--------------
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
10回取り出し--------------
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回目
2回目
3回目
4回目
5回目
聞くたびに異なる回答をくれるのはいいんだけど、、、
ご節ご尤もと思うところと、それはないんじゃないかと思うところと、、、
疲れた。
今日はこれでおしまい。
一晩寝てから見直します。
おやすみなさい。
ここまで読んでいただき、有り難うございました。
この記事が参加している募集
これまでの収益は全て、それを必要としておられる方々へ、支援機関を通して寄付させていただきました。この活動は今後も継続したいと思っています。引き続きよろしくお願いいたします。