为什么循环队列中需要留一个空cell来判断是否为空？

Question

我刚刚在课堂上了解了循环队列，但我仍然很困惑，我知道如果没有空单元格，我们将无法区分空队列和只有一个元素的队列，但为什么呢？ 我使用 fh 作为原型，使用 fc 作为实现：
fh:

#define n 50
struct queue
{
    int key[n];
    unsigned head;
    unsigned tail;
};
void cree(struct queue *);
unsigned empty(struct queue);
int first(struct queue);
void enqueue(int, struct queue *);
void dequeue(struct queue *);

然后 fc:

#include <assert.h>
#include "f.h"
void cree(struct queue *q)
{
    q->head = 0;
    q->tail = 0;
}
unsigned empty(struct queue q)
{
    return (q.head == q.tail);
}
int first(struct queue q)
{
    unsigned i;
    assert(!empty(q));
    i = q.head + 1;
    if(i>n-1)
    {
        i = 0;
    }
    return(q.key[i]);
}
void enqueue(int x, struct queue *q)
{
    q->tail++;
    if(q->tail>n-1)
    {
        q->tail = 0;
    }
    assert(q->head != q->head);
    q->key[q->tail] = x;
}
void dequeue(struct queue *q)
{
    assert(!empty(*q));
    q->head++;
    if(q->head>n-1)
    {
        q->head =0 ;
    }
}

Answer 1

你在两个方面有点错误。第一种方式是空队列和满队列之间的混淆，而不是只有 1 个元素的队列。保持一个单元格为空会改变“已满”的含义。

那么，给定一个循环队列，如何确定其中有多少个元素呢？

您想编写size = (end_position - start_position) % array_length。事实上，% 运算符在您的语言中可能无法按照您想要的方式工作，因此您将编写 size = (array_length + end_position - start_position) % array_length

如果队列为空，您将得到 size == 0，这就是您想要的。但是，如果队列中有 array_length 元素，您也会得到 size == 0，这是错误的。您可以通过确保元素数量始终小于数组长度来解决此问题。

另一种错误的方式是“无法”部分。这种说法几乎总是错误的。例如，如果您存储 start_position 和 size，而不是 start_position 和 end_position，那么很容易区分完整位置从空开始，您可以将 array_length 元素放入队列中。