演習課題「キューを実装しよう」
右のコードエリアには、前回のチャプターの方法で実装したキューのコードがあります。
このキューには、繰り返し使うごとに容量が小さくなってしまう、という問題点があります。
enqueue 関数と dequeue 関数を修正し、この問題点を解消してください。
プログラムを実行して、正しく出力できれば演習課題クリアです！
期待する出力値
10
20
30
40
50
＃07:キューを実装しよう (3)
このチャプターでは、前回実装したキューの問題点を改善します。
// キューを実装しよう(3)
#include <stdio.h>
#define N 10
typedef int data_t;
data_t queue[N];
int head;
int tail;
void init(void)
{
head = 0;
tail = 0;
}
void enqueue(data_t x)
{
if (tail >= N) {
printf("queue overflow\n");
return;
}
queue[tail] = x;
tail++;
}
void dequeue(data_t *x)
{
if (head == tail) {
printf("queue underflow\n");
return;
}
*x = queue[head];
head++;
}
int main(void)
{
// キューの初期化
init();
// キューに値を追加
enqueue(10);
enqueue(20);
// キューから値を取り出す
int x;
dequeue(&x);
printf("%d\n", x);
dequeue(&x);
printf("%d\n", x);
}
上のコードでは、tail、head の値が enqueue、dequeue を実行するごとに増えていってしまいます。
そのため、enqueue と dequeue を使うごとに、キューの容量が小さくなっていってしまいます。
◯ キューの容量が小さくなりオーバーフローになるコード例// キューを実装しよう(3)
#include <stdio.h>
#define N 4
typedef int data_t;
data_t queue[N];
int head;
int tail;
void init(void)
{
head = 0;
tail = 0;
}
void enqueue(data_t x)
{
if (tail >= N) {
printf("queue overflow\n");
return;
}
queue[tail] = x;
tail++;
}
void dequeue(data_t *x)
{
if (head == tail) {
printf("queue underflow\n");
return;
}
*x = queue[head];
head++;
}
int main(void)
{
// キューの初期化
init();
// キューに値を追加
enqueue(10);
enqueue(20);
enqueue(30);
// キューから値を取り出す
int x;
dequeue(&x);
printf("%d\n", x);
dequeue(&x);
printf("%d\n", x);
// キューに値を追加
enqueue(40);
enqueue(50); //=> オーバーフロー
}
このチャプターで作成したコードです。// キューを実装しよう(3)
#include <stdio.h>
#define N 4
typedef int data_t;
data_t queue[N];
int head;
int tail;
void init(void)
{
head = 0;
tail = 0;
}
void enqueue(data_t x)
{
if (head == (tail + 1) % N) {
printf("queue overflow\n");
return;
}
queue[tail] = x;
tail = (tail + 1) % N;
}
void dequeue(data_t *x)
{
if (head == tail) {
printf("queue underflow\n");
return;
}
*x = queue[head];
head = (head + 1) % N;
}
int main(void)
{
// キューの初期化
init();
// キューに値を追加
enqueue(10);
enqueue(20);
enqueue(30);
// キューから値を取り出す
int x;
dequeue(&x);
printf("%d\n", x);
dequeue(&x);
printf("%d\n", x);
// キューに値を追加
enqueue(40);
enqueue(50);
}