エンキューとデキューの操作関数

質問

エンキューとデキューの操作関数なのですが、
どのような考え方なのかがいまいちわからず困っています。
どなたか解説お願いします。

int QueueEnque(Queue *q, int x)
{
if(q->num >= q->max){
return (-1);
}else{
q->num++;
q->que[q->front++] = x;
if(q->front == q->max){
q->front =0;
}
if(q->num ==1){
q->rear--;
if(q->rear == -1){
q->rear = q->max-1;
}
}
return (0);
}
}
int QueueDeque(Queue *q, int *x)
{
if(q->num <= 0){
return (-1);
}else{
q->num--;
q->rear++;
if(q->rear == q->max){
q->rear =0;
}
*x = q->que[q->rear];
if(q->num ==0){
q->front =q->rear;
}
return (0);
}
}

キューを実現する構造体がこのようになっています。
typedef struct {
int max; /* キューのサイズ */
int num; /* 現在の要素数 */
int front; /* 先頭要素カーソル */
int rear; /* 末尾要素カーソル */
int *que; /* キュー（の先頭要素へのポインタ） */
} Queue;

回答No.2

LongSecret · ベストアンサー

なんかわざわざrearをずらして読み辛くしてある感じがします。このコード。
どう使うのかは呼び出し側のコードとセットで初めて分かるので一応「断定」はできませんが

今見たらかなり似てるやつが
C言語によるアルゴリズムとデータ構造（柴田望洋＋辻亮介著）
に載ってました。

初期化の段階で

num　
front
rear
が0になってて

queが確保領域へのポインタ
maxに確保領域の要素数

が入ってるとして
その物のコードや詳しい解説は買ってみてのお楽しみ（？）ということでｗ
一応少しだけ変形して引用すると

int QueueEnque( Queue *q, int x ){

if( q->num == q->max ) return -1;

q->num++;
q->que[q->rear++] = x;
if ( q->rear == q->max ) q->rear = 0;
return 0;

}

int QueueDeque( Queue *q, int *x ){

if ( !q->num ) return -1;

q->num--;
*x = q->que[q->front++];
if( q->front == q->max ) q->front = 0;
return 0;

}

こういうコードの方が遥かに素直だと思います。
なお

q->que[q->rear++] = x;
if ( q->rear == q->max ) q->rear = 0;

↓

q->que[q->rear] = x;
q->rear = (q->rear+1) % q->max;

とも書けますね。

循環がキーワードですが
これらのコードでは意味は分かりますか？

お礼

わかりました！ありがとうございました！

回答No.3

Tacosan

そ～なんですよ, エンキューで rear をいじる必要などないんですよ～＞#2. このコードではデキューの方でデータを取り出す前にインクリメントしてるものだから, そこにあわせてエンキューで rear を調整しなきゃならないなっちゃってる. これは本来デキューの方を修正すべきところです. ぶっちゃけいえば「コードが悪い」ってこと.

ああ, #1 のお礼に「あれが何を行っているのかがわからなくて…」と書かれてますが, 「あれ」が何かわからないので反応できません.

お礼

回答ありがとうございました！

回答No.1

Tacosan

このプログラムはさておいて, 「抽象的なデータ構造」としてのキューやエンキュー・デキューという操作は理解できていますか?

q->max との比較は成り立たないのが普通だから, そこはとりあえず無視して考えてみ.

お礼

それは、一応わかっているつもりです。
１行ずつ解釈していこうと思って、講義資料など見ていたのですが、
あれが何を行っているのかがわからなくて…