实现循环队列的微妙错误

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为true,而剩下一个空的空间即inputArray [0].

谢谢

Answer 1

这不是一个错误,它是循环队列的一个特征.如果你没有留下一个空槽,那么就无法区分完整和空的情况.当然,pop函数应该返回它从队列中读取的int,并且不需要将值设置为-1.