ADT循环队列队列和脱队列

Question

#define SIZE 5
struct queue{   float data[SIZE];
                int head,tail;
};

void init(struct queue *q){ q->head=0; q->tail=SIZE-1; }
int  empty(struct queue *q){
    int temp=q->tail+1;
    if(temp==SIZE) temp=0;
    return temp==q->head;
}
int  full(struct queue *q){
    int temp=q->tail+2;
    //if(temp==SIZE) temp=0;
    //if(temp==SIZE+1) temp=1;
    if(temp>=SIZE) temp-=SIZE;
    return temp==q->head;
}
void enqueue(struct queue *q, float item){
    if(++q->tail>=SIZE) q->tail-=SIZE;
    q->data[q->tail]=item;
}
float dequeue(struct queue *q){
    float temp= q->data[q->head];
    if(++q->head>=SIZE) q->head-=SIZE;
    return temp;
}

上面的代码是由我的教授提供的，我在理解队列函数、if(++q->tail>=SIZE) q->tail-=SIZE;部件和去队列函数if(++q->head>=SIZE) q->head-=SIZE;方面有困难，为什么我需要评估这些条件？谁来给我详细解释一下..。谢谢

Answer 1

让我举一个例子：

看这个图片：队列图像 (我不能在这里发布图像，因为声誉点，所以，给出链接)

现在，在图1中：

head=0，tail=3

所以，首先我们需要检查一下是否是tail==size-1。但无花果的情况并非如此。所以，我们只需要在那个位置增加尾部并存储新的项目。

在图中。2：

head=2，tail=7

所以，首先我们需要检查一下是否是tail==size-1。因此，我们将增加尾部，然后从它减去size，得到tail=0。

总结这些步骤，我们需要增加tail并检查tail==size-1，如果是真的，我们需要执行tail=tail-size。所以，我们代码所做的是，将步骤增量和检查结合起来。因此，它通过语句tail检查size和++q->tail>=size的增量值。如果是真的，那么从size中减去tail。

在这里，不管条件是真还是假，++q->tail都会发生。

如果您对C语言还不熟悉，就可以在enquque中选择这个选项：

++q->tail;    // or q->tail=q->tail+1 or q->tail+=1;
if(q->tail==size)
    q->tail=q->tail-size;
q->data[q->tail]=item;

对于带头的Dequeue也可以这样解释。

Answer 2

队列是圆形的。当您试图在队列中加入一个项目时

void enqueue(struct queue *q, float item){
    if(++q->tail>=SIZE) q->tail-=SIZE;
    q->data[q->tail]=item;
}

队列的尾部将到达SIZEth元素(理论元素在队列结束后的索引处)，队列设计为从队列开始包装和覆盖项。

Answer 3

该方法同样适用于其它问题。

首先，您应该了解或了解代码应该做什么。

在这个特殊的问题中，我们处理的是一个循环队列，这意味着一些东西(数字)站在一个有限大小的队列中，首先离开的是它的头，最后到达的是尾部。

循环队列是“循环”的，因为头尾的“等待点”不断变化，而队列的最大大小保持不变。这样做的想法是，您不移动队列中的项目(就像队列中的人)--您只需标记队列中的第一项和最后一项并保持顺序

要正确理解这些语句是什么，您首先应该尝试展开复合语句。

if(++q->tail>=SIZE) q->tail-=SIZE;

根据这张桌子，这意味着：

++q->tail /* we have a new arrival, tail is always the index of the last to come-in*/
/* lets say that the previous arrival was placed in q->data[4], the last element of the array, where we should put the new one? q->tail is now 5 but data[5] is out of bounds */
if((q->tail) >= SIZE) /* we increased the index but we have limited space in the array*/       
   /* this is the "circular" part. for size=5 it means that tail 
      was over the limit and should do the circle back to 0 to 
      make space for the new arrival */
   q->tail -= SIZE;

试着一个人把你的注意力集中在排队上。使用优先级规则将语句解压缩为几个。