循环队列中的满/空缓冲区区分

Question

在循环队列的数组实现中，如果在第一个元素之前指向一个插槽，而在最后一个元素之后指向一个插槽，则会面临如何识别队列是满还是空的问题。

为了解决这个问题，我们要么使用计数器，要么在缓冲区中浪费一个空间。

我在想下面的方法。请纠正我的错误，如果没有请让我知道这是一个更好/更差的解决方案比以上。

null

Answer 1

这种方法在逻辑上没有太大的错误。您将front和freel中的负值视为一种标志，以指示队列为空。假设更新front和freed的逻辑将值保持在0...size范围内，则只需将其中一个值设置为超出该范围即可指示队列为空。

考虑一下这个选择。许多循环队列使用front和freed索引作为无符号值，size作为2的幂。它们的值的更新总是递增的，并且允许它们环绕。这避免了调整这些指数的复杂逻辑。由于索引是无符号的，即使它们是环绕的，差分算术也可以正确地确定元素的数量。

即使索引在增量上缠绕，模数仍然工作的诀窍是size是2的幂。这确保了环绕不影响模的计算。

unsigned front_ = 0, rear_ = 0;
Type q_[SIZE];

unsigned getCount () { return rear_ - front_; }
bool isEmpty () { return getCount() == 0; }
bool isFull () { return getCount() == SIZE; }
bool enQ (Type val) {
    bool result = !isFull();
    if (result) q_[rear_++ % SIZE] = val;
    return result;
}
bool deQ (Type *val) {
    bool result = !isEmpty();
    if (result) *val = q_[front_++ % SIZE];
    return result;
}