实现循环队列时的细微错误

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]。

谢谢

- Abhay Hegde

---

你能用一些输入值来解释一下这段代码出了什么问题吗？当它不满时，你所说的“给出完整队列”的意思是什么？ - LearningC

由于您正在使用C ++，因此应将功能封装到类中，而不是使用全局变量。即使在C中，使用全局变量也是不好的编程风格。 - Jabberwocky

同意@MichaelWalz，但是让我们暂时忘记复杂性。我想先想出正确的逻辑。 - Abhay Hegde

正如您在问题的第一点下解释的那样，将1添加到inputArray[1]而不是inputArray[0]，这很明显，yun在增加queueBack之前进行了操作。 - Jabberwocky

我刚刚注意到你的变量名不符合标准。通常，当项目被推入时，queueFront会前进，而当项目被弹出时，queueBack会前进，即后面跟随前面。 - user3386109

Answer 1

这不是一个错误，而是循环队列的一种特性。如果你不留下一个空闲槽位，那么就无法区分满和空的情况。当然，pop函数应该返回它从队列中读取的整数，并且没有必要将该值设置为-1。

- user3386109

---

在这种情况下，将值设置为-1是一个错误，因为它是在queueFront被增加之后完成的（因此它会覆盖下一个元素）。 - pat

不是真的有bug，因为OP对两个指针都进行了预增操作。我同意后增更直观，但如果OP将最后一行替换为返回语句（以返回值），那么你会发现预增实际上更有效率。 - user3386109

啊，我现在明白了。我的错。 - pat

@user3386109，我修改了pop()函数，现在它正确了吗？ - Abhay Hegde