满/空缓冲器的区别在循环队列

Question

在数组实现，如果我们前面指向第一元件和后到最后一个元件之前的狭槽的圆形队列，母鸡我们面对如何识别问题的队列是否已满空。

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

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

1）点前面的第一个元素&后的最后一个元素 2）具有以下功能：检查队列只有1左 3）如果我们dequeing的最后一个元素，使元素前后 - 1。如果两个前&后部是-1，如果前面=（背面+ 1）％大小

Answer 1

有逻辑上没有太大的错这种方法 5）isFull将为真 4）的isEmpty（）为真。您正在将front和rear中的负值视为一种标志来指示队列为空。假设你的逻辑来更新front和rear保持在范围0 .. size值，你只需要设置其中的一个是范围之外，表示队列为空。

考虑这个选择。许多圆形队列与front和rear指数无符号数，和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; 
}