0

現在、こちらの記事を読んでいてリングバッファの際の末尾の判定基準が分かりません。

#include <iostream>
#include <vector>
using namespace std;
const int MAX = 100000; // キュー配列の最大サイズ

int qu[MAX]; // キューを表す配列
int tail = 0, head = 0; // キューの要素区間を表す変数

// キューを初期化する
void init() {
    head = tail = 0;
}

// キューが空かどうかを判定する
bool isEmpty() {
    return (head == tail);
}

// スタックが満杯かどうかを判定する
bool isFull() {
    return (head == (tail + 1) % MAX);
}

// enqueue (tail に要素を格納してインクリメント)
void enqueue(int v) {
    if (isFull()) {
        cout << "error: queue is full." << endl;
        return;
    }
    qu[tail++] = v;
    if (tail == MAX) tail = 0; // リングバッファの終端に来たら 0 に
}

// dequeue (head にある要素を返して head をインクリメント)
int dequeue() {
    if (isEmpty()) {
        cout << "error: stack is empty." << endl;
        return -1;
    }
    int res = qu[head];
    ++head;
    if (head == MAX) head = 0;
    return res;
}

int main() {
    init(); // キューを初期化

    enqueue(3); // キューに 3 を積む {} -> {3}
    enqueue(5); // キューに 5 を積む {3} -> {3, 5}
    enqueue(7); // キューに 7 を積む {3, 5} -> {3, 5, 7}

    cout << dequeue() << endl; // {3, 5, 7} -> {5, 7} で 3 を出力
    cout << dequeue() << endl; // {5, 7} -> {7} で 5 を出力

    enqueue(9); // 新たに 9 を積む {7} -> {7, 9}
    enqueue(11); // {7, 9} -> {7, 9, 11}

    dequeue(); // {7, 9, 11} -> {9, 11}
    dequeue(); // {9, 11} -> {11}
    dequeue(); // {11} -> {}

    // 空かどうかを check: empty の方を出力
    cout << (isEmpty() ? "empty" : "not empty") << endl;
}

スタックが満杯の際に

// スタックが満杯かどうかを判定する
bool isFull() {
    return (head == (tail + 1) % MAX);
}

こちらの関数が書かれているのですが、(tail + 1) % MAXをなぜやっているのでしょうか?
私が思うに、head ==(tail + 1)だけで、先頭と末尾のそれぞれの値が一致していることが分かると思います。
なぜ、配列の数で割る必要があるのでしょうか?
ぜひご教授宜しくお願い致します。

1
  • Qiita にはコメント欄もあるはずなので、記事やプログラムを書いた本人に質問することも検討してください。
    – cubick
    2022年8月21日 12:24

1 件の回答 1

0

私が思うに、head ==(tail + 1)だけで、先頭と末尾のそれぞれの値が一致していることが分かると思います。

tailがMAX-1まで進んだときになにが起こるのか、を考えればいいです
head ==(tail + 1)とすると、headがMAXとなってしまいます。
このときにenqueueしたら、tailはどういう値になればいいと思いますか。

10
  • コメントありがとう御座います。自分で考えてみると、もしhead ==(tail + 1)だけでMax判定をしようと思ったら配列の数の途中でもこれに該当する可能性があり、配列の要素自体のいくらを使っているかどうかを判定したいのに、前の自分の考えだったら何も意味がないことが分かりました。また、なぜhead ==(tail + 1)の際に、head ==tailだけで+1しなくてもMax判定できるのはないかと思いましたが、常にエンキュとデキュの中でこの関数を呼び出すということは、次に追加することを示すindexの値(+1)というのがないと判定できないということが分かりました。ありがとうございます! 2022年8月21日 12:45
  • 1つ分からないので、なぜ(tail + 1) % MAX-1では無いのでしょうか? 配列自体は、0オリジンでMaxはオフセットの配列のインデックスを示す数なので、quという配列自体の最大のindex数はMax-1だと思います。ご意見宜しくお願い致します。 2022年8月21日 12:50
  • 自己解決できたので、自分に回答させて頂きます。配列quというものに対してMaxという配列数が存在する。そのMaxに対して何個あるかというのが、そもそもの割り算。またこの条件下で、絶対に商が1になることはない。なぜなら、商が1以上になった時そのtailやheadは、オーバフローだから。quは、0オリジンで始まり常にMax-1までのインデックス数をとる。この時、ある値に対してのインデックス数は、%maxをすることで、その余りは必ず0オリジンで始まり常にMax-1になる。ここを参照 2022年8月21日 13:08
  • 1
    で、自己解決したなら、その解決の内容を自己回答し、解決済としましょう
    – y_waiwai
    2022年8月21日 23:21
  • 1
    「満杯」とは「tail の次」にheadがある状態.→じゃあ「tailの次」を表す配列indexとは何か? ほとんどの場合は(tail+1)だけど,tailが配列末尾要素の場合には例外的に0とせねばならない.剰余を使っている式はそれをやっているだけのこと.
    – fana
    2022年8月22日 1:37

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。