STEP 4.2B 構造体でキュー

<問題> キュー配列とhead, tail, number変数をメンバーとする構造体(1つ)によるキュー実装例。プログラムを読み、自分なりのコメント文をつけて解読してみてください。


<実行例> (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

教科書と同じように、分割コンパイル
queue.h 共有情報
queue.c 関数定義
0402b.c main関数

gcc -c queue.c
gcc -c 0402b.c
gcc -o 0402b queue.o 0402b.o




解答例

以下、queue.h

#include <stdio.h>
#include <stdlib.h>
#define MAX 256

/* Queue構造体 mainで1つ生成 */
typedef struct {
   char data[MAX];
   int head, tail, number;
} Queue;

void enqueue(Queue *Q, char x);
char dequeue(Queue *Q);

/* 初期化 */
void initialize(Queue *Q);
int empty(Queue *Q);

/* キューを表示 */
void show(Queue *Q);


以下、queue.c

#include "queue.h"

/* 最後尾に追加 */
void enqueue(Queue *Q, char x) {
   if(Q -> number < MAX){
      Q -> number++;
      Q -> tail = (Q -> tail % MAX)+1;
      Q -> data[Q->tail] = x;
   } else {
      printf("Queue Q overflows.\n");
   }
}

/* 先頭からデータ取り出し */
char dequeue(Queue *Q){
   if(Q -> number >0) {
      Q -> number--;
      Q -> head = (Q -> head % MAX)+1;
      return(Q -> data[Q->head]);
   } else {
      printf("Queue Q is empty.\n");
      return('\0');
   }
}

/* 初期化 data配列は初期化していません */
void initialize(Queue *Q){
   Q -> head = 0;
   Q -> tail = 0;
   Q -> number =0;
}

int empty(Queue *Q){
   if(Q -> number == 0){
      return(1);
   }
   return(0);
}

/* headの次から、number個 プリント */
void show (Queue *Q){
   int n;
   int p;

   printf("head = %2d tail = %2d elements = %2d \n", Q -> head, Q -> tail, Q -> number);

   p = Q -> head + 1;
   for (n = 1; n <= Q -> number ; n++) {
      printf("Q[%d] = %c\n", p, Q -> data[p]);
      p++;
      if (p > MAX)
         p = p % MAX;
   }
}


以下, 0402b.c

#include "queue.h"

int main(void) {
   char x;
   Queue Q;

   initialize(&Q);
   show(&Q);
   printf("a is enqueued \n");
   enqueue(&Q, 'a');
   printf("b is enqueued \n");
   enqueue(&Q, 'b');
   printf("c is enqueued \n");
   enqueue(&Q, 'c');
   show(&Q);

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

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

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

   return (0);
}