STEP 4.2A　配列でキュー

<問題> 配列によるキュー実装例。プログラムを読み、自分なりのコメント文をつけて解読してみてください。

<実行例>　

head =  0 tail =  0 elements =  0
a is enqueued
b is enqueued
c is enqueued
head =  0 tail =  3 elements =  3
Q[1] = a
Q[2] = b
Q[3] = c
a is dequeued
b is dequeued
head =  2 tail =  3 elements =  1
Q[3] = c
d is enqueued
c is dequeued
e is enqueued
head =  3 tail =  5 elements =  2
Q[4] = d
Q[5] = e
de

• 上の文字列str中、２番目の動物を表示する。

解答例

#include <stdio.h>
#define MAX 5

void enqueue(char x);
char dequeue(void);
void initialize(void);
int empty(void);
void show(void);

char Q[MAX]; /* 教科書のコードは誤り */
char Q[MAX+1]; /* Q[1] - Q[5]まで5個を使用するプログラムになっています。2023年Hさんありがとう */
int head = 0; /* 先頭の1つ前 */
int tail = 0; /* 末尾へのポインター */
int number = 0; /* 格納されているデータ数  MAXまで */

/* キューにデータを追加 */
void enqueue(char x) {
   if (number < MAX) {
      number++;
      tail = (tail % MAX) + 1; /* 環状の配列 %は余り(modulo関数)を与える
                                tailポインターをインクリメント */
      Q[tail] = x;
   } else {
      printf("Queue Q overflows.\n");
   }
}

/* キューからデータを取り出し */
char dequeue(void) {
   if (number > 0) {
      number--;
      head = (head % MAX) + 1; /* headポインタをインクリメント */
      return (Q[head]);
   } else {
      printf("Queue Q is empty.\n");
      return ('\0');
   }
}

/* 配列Q、headポインター、tailポインター、データの個数numberの初期化 */
void initialize(void) {
   int i;
   head = 0;
   tail = 0;
   number = 0;
   for (i = 0; i < MAX; i++) {
      Q[i] = '\0';
   }
}

/* キューが空の状態なら1 */
int empty(void) {
   if (number == 0) {
      return (1);
   }

   return (0);
}

/* headの次から、number個 プリント */
void show(void) {
   int n;
   int p;
   printf("head = %2d tail = %2d elements = %2d \n", head, tail, number);
   p = head+1;
   for (n = 1; n <= number ; n++) {
      printf("Q[%d] = %c\n", p, Q[p]);
      p++;
      if (p > MAX)
         p = p % MAX;
   }
}

int main(void) {
   char x;

   show();
   printf("a is enqueued \n");
   enqueue('a');
   printf("b is enqueued \n");
   enqueue('b');
   printf("c is enqueued \n");
   enqueue('c');
   show();


   x = dequeue();
   printf("%c is dequeued \n", x);
   x = dequeue();
   printf("%c is dequeued \n", x);
   show();

   printf("d is enqueued \n");
   enqueue('d');
   x = dequeue();
   printf("%c is dequeued \n", x);
   printf("e is enqueued \n");
   enqueue('e');
   show();

   /* 教科書のプログラム。キューが空になるまで、dequeueしながらプリント */
   while (!empty()) {
      printf("%c", dequeue());
   }
   printf("\n");

   return (0);
}