キューのついて

[かける]

学校で使っている教科書のキューの順配列による表現のプログラム例で

#define M 1000
#define OVERFLOW -1
#defime UNDERFLOW -2


if(f-r == 1 || f-r+M == 1) //fはキューの先頭を表すポインタ、rは次に格納すべき番地を表すポインタ
return OVERFLOW;
else {
x[[/url] = y;
if(++r == M) r = 0;
}



というenqueのときのプログラム何ですが、
最初のif文のところがわからないです

[Poco]

キューが一杯かどうか確認する処理です。
f-r == 1はf>rの時、f-r+M == 1はf<rの時にいっぱいかどうかを表しています。

> //fはキューの先頭を表すポインタ、rは次に格納すべき番地を表すポインタ

このコメントは嘘です。f,rはポインタではありません。

[toyo]

fが読み出し位置でrが書き込み位置ですかね
リングバッファでこのような処理をします
もっとわかりやすい変数名にしてくれたらいいのに

[Poco]

> fが読み出し位置でrが書き込み位置ですかね
> リングバッファでこのような処理をします
> もっとわかりやすい変数名にしてくれたらいいのに

f:front
r:rear
ですかね。

[かける]

みなさまお答えありがとうございます


fがデキューする位置でｒがインキューする位置なのですが


f-r == 1の場合は
ｒにはあとひとつ値が入れられるのではないですか？
ｒがインキューする位置なのだから

何かひとつ領域を空けておく必要があるのですか？

[Poco]

キューが空である場合と、満杯である場合を区別するためです。

・キューが空であるとは、fとrが等しい時である。→f-r == 0を満たす時である。
・キューが満杯であるとは、
　・f<rのとき、fが0で、rが999の時である。→f-r+M == 1を満たす時である。
　・f>rのとき、fが1ならrは0、fが2ならrは1、…fが999ならrは998のときである→f-r == 1を満たす時である。

さて、キューが満杯の条件をちょっと変え、もう一個余分に挿入できるようにした場合、どうなるでしょうか？

　・f>rのとき、fが1ならrは1、fが2ならrは2、…fが999ならrは999のときである→f-r == 0を満たす時である。

キューが空である条件と被ります。
空なら挿入できますが、空でない場合は挿入できません。でも区別がつきません。

[かける]

ありがとうございます


区別をするためにひとつ領域を余らせているのですね！！

[Poco]

キューの要素数を格納する変数を用意すれば領域の無駄を省けるんですけどね。

[かける]

ぽこさん
何どもありがとうございます


Ｃ言語は得意なのですか？

[Poco]

> Ｃ言語は得意なのですか？

まだまだです。

[かける]

キューを使って横型探索をする課題がでているので詰まったらまたおねがいします