为什么我们需要在循环队列中留下一个空单元格来判断它是否为空？

Question

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

#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 *);

然后 f.c:

#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队列中的元素。

为什么我们需要在循环队列中留下一个空单元格来判断它是否为空？

Why do we need to leave an empty cell in a circular queue to determine whether it is empty or not?

c

data-structures