c - 实现循环队列的细微错误

Question

我正在尝试实现一个简单的循环队列操作，如下所示

void push(int theElement)
{
  //Check if the push causes queue to overflow
    if  (((queueBack + 1 ) % arrayLength) == queueFront) {
       std::cout<<"Queue is full."<<std::endl;
       return ;
    } 
    queueBack = (queueBack + 1) % arrayLength;
    inputArray[queueBack] = theElement;
}

int pop()
{
   //Check if queue  is already empty
  if ( queueFront == queueBack ) {
    std::cout<<"Queue is empty."<<std::endl;
    return;
  }
  queueFront = (queueFront + 1 ) % arrayLength;
  return inputArray[queueFront];

}

考虑最初 queueFront = 0 和 queueBack = 0，上面的代码导致队列已满，但实际上并非如此。我该如何纠正这个问题？在第一种情况下，我的实现是否正确？

测试用例最初arrayLength = 3, queueFront = 0, queueBack = 0;

1. 第一次调用 push(1) 结束时； queueFront = 0 , queueBack = 1 , 1 被添加到 inputArray[1] 而不是 0；

2. 在第二次调用 push(2) 结束时，queueFront = 0, queueBack = 2, , 2 被添加到 inputArray[2]，

3. 现在，(queueBack + 1) % arrayLength == queueFront 为真，而还剩下一个空白空间，即 inputArray[0]。

谢谢

Answer 1

这不是bug，是循环队列的一个特性。如果你不留一个空槽，那么就没有办法区分满箱和空箱。当然，pop函数返回的应该是从队列中读取出来的int，没必要设置为-1。