(c言語)リングバッファのキューの無駄をなくす

状況

リングバッファのキューは先頭に戻す処理時に1つ無駄ができることを知ったので、改善策を考えた。(enqueueのみ)

リングバッファのキューとは

リングバッファのキューは、キューの限界に領域まで達したら、先頭に戻すことでデキューをタイミングよくすれば無限に入るキューが完成する。

これがリングバッファのキューである。

enqueue以外のコードに関しては以下である。

#include <stdio.h>
#include <stdlib.h>

#define SIZE 4

struct queue {
  int head, tail;
  char elem[SIZE];
};
char dequeue(struct queue *q) {
  char val;
  if (q->head == q->tail) {
    printf("queue underflow\n");
    exit(1);
  } else {
    val = q->elem[q->head];
    q->head++;
    if (q->head >= SIZE) {
      q->head = 0;
    }
    return val;
  }
}

int main(void) {
  struct queue Q;
  char e, moji[5];
  int input, i;

  Q.head = 0;
  Q.tail = 0;
  printf("キューに格納されている値\n");
  for (i = 0; i < 10; i++) {
    printf("%i:::%c\n", i, Q.elem[i]);
  }
  while (1) {
    // メニュー表示
    printf("操作を選択:\n");
    printf("  1: 格納\n");
    printf("  2: 取得\n");
    scanf("%d", &input);  // 操作を入力

    switch (input) {
      case 1:  // 格納
        printf("格納する文字を入力してください：");
        scanf("%s", moji);
        enqueue(&Q, moji[0]);
        printf("\n");
        printf("キューに格納されている値\n");
        for (i = Q.head; i <= Q.tail; i++) {
          printf("%i::%c\n", i, Q.elem[i]);
        }
        printf("tailの値::%d\n", Q.tail);
        printf("headの値::%d\n", Q.head);
        break;
      case 2:  //出力
        e = dequeue(&Q);
        printf("%c\n", e);
        printf("キューに格納されている値\n");
        for (i = Q.head; i <= Q.tail; i++) {
          printf("%i::%c\n", i, Q.elem[i]);
        }
        printf("tailの値::%d\n", Q.tail);
        printf("headの値::%d\n", Q.head);
        break;

        break;
    }
  }
  return 0;
}

問題となる例とコード

以下が今回の問題となる部分です。

先頭に値を入れていない。(*1)
または、全てが埋まった瞬間にoverflowとなってしまい、デキューの可能性を否定している。(*2)

void enqueue(struct queue *q,char val){
  q->tail++;
  if(q->tail==SIZE){//最後まで行ったら先頭に戻す
    q->tail=0;
  }
  if(q->tail==q->head){//先頭と最後の指す位置が同じならoverflowとする
    printf("queue overflow\n");
  }else{
     q->elem[q->tail] = val;//値の代入
  }
}

void enqueue(struct queue *q,char val){
  q->elem[q->tail] = val;//値の代入
  q->tail++;
  if(q->tail==SIZE){//最後まで行ったら先頭に戻す
    q->tail=0;
  }
  if(q->tail==q->head){//先頭と最後の指す位置が同じならoverflowとする
    printf("queue overflow\n");
  }
}

解決のためのコード

上記の問題を解決するために以下のようなコードにします。

void enqueue(struct queue *q, char val) {
  if ((q->tail) % SIZE == (q->head) % SIZE && (q->tail) != 0) {
    printf("queue overflow\n");
  } else {
    q->elem[(q->tail) % SIZE] = val;
    q->tail++;
  }
  return;
}

処理内容

tailをSIZEで割った値の余りとheadをSIZEで割った値の余りを比較する
一緒であり、tailの値が0でないoverflowとする
違うならtailをSIZEで割った値の余り番目に値を代入する

詳細

リングバッファで何回も周回してもSIZEで割った際の余りは常に1周目の場所と同じところを指すため、SIZEで割った余りの値を参考にoverflow等を判定している。
また、if文の条件式において、&&の後ろは&&の前半部分のみだけだと、一番最初にenqueueをした際にはじかれてしまうので、最初でないことを示すために書いている。

まとめ

今回、リングバッファのキューにおいて無駄があったため解決策を探した。
正直、余りを使った構造で無駄をなくす構造なのでoverflowしていないのにおかしいと思う人はぜひ活用していただきたい。