大门| 2012年CS大门|问题33

假设容量（n–1）元素的循环队列由n个元素组成的数组实现。假设插入和删除操作分别使用REAR和FRONT作为数组索引变量执行。最初，后=前=0。检测队列已满和队列已空的条件如下 （A） 满：（后+1）模块n==前，空：后==前 （B） 满：（后+1）模n==前，空：（前+1）模n==后 （C） 满：后==前，空：（后+1）模块n==前 （D） 满：（前+1）模块n==后，空：后==前 答复: （A） 说明： 循环队列的实现：

头 –它始终指向队列中下一次删除的位置。 尾 –它总是指向下一个空位置，下一次插入将在队列中进行。

我们将使用环绕功能，因为它是一个循环队列，当尾部或头部位于索引n-1时，下一个操作将把它们带到索引0。尽管阵列中的容量为n，但我们将保留一个空位，以检测溢出（队列已满）和下溢（队列已空）情况。队列中的元素位于位置Q.head，Q.head+1，Q.tail+1，这里我们“环绕”，即位置0以循环顺序紧跟位置n-1。

算法：

ENQUEUE(Q, x)                        
{

  if Q.head == Q.tail + 1
      error "Queue overflow"

  Q[Q.tail] = x

  if Q.tail == Q.length    - 1
      Q.tail = 0
  else
      Q.tail = Q.tail + 1
}


DEQUEUE(Q)
{
  if Q.head == Q.tail
      error "Queue underflow"

  x = Q[Q.head]

  if Q.head == Q.length - 1
      Q.head = 0
  else
      Q.head = Q.head + 1

  return x
}

看见 http://en.wikipedia.org/wiki/Circular_buffer#Always_Keep_One_Slot_Open

这个解决方案是由 Pranjul Ahuja 这个问题的小测验