若循环队列以数组Q[0,…,m－1]作为其存储结构,变量rear表示循环队列中队尾元素的实际位置,其移动按

Question

若循环队列以数组Q[0，…，m-1]作为其存储结构，变量rear表示循环队列中队尾元素的实际位置，其移动按rear=(rear+1)mod m进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是(67)。

A．rear-length

B．(rear-length+m)mod m

C．(1+rear+m-length)mod m

D．m-length

Answer 1

正确答案：C
解析：这种题目在考场上最好的解题方法是随便拿一个实际的例子，往里面一套便知道了。不过，作为试题分析，下面解释一下原理。循环队列就是将实现队列的数组a[m]的第一个元素a[0]与最后一个元素a[m-1]连接起来。队空的初态为head=tail＝0。在循环队列中，当tail赶上head时，队列满。反之，当head赶上tail时，队列变为空。这样队空和队满的条件都同为head=tail，这会给程序判别队空或队满带来不便。因此，可采用当队列只剩下一个空闲结点的空间时，就认为队列已满的简单办法，以区别队空和队满。即对空的判别条件是head＝tail，队满的判别条件是head=tail+1。因为rear表示的是队列尾元素的实际位置(注意：不是队尾指针)。而且题中有“移动按rear=(rear+1)modm进行”，这说明队列存放元素的顺序为：e[1]，Q[2]，…，Q[m-1]，Q[0]。在理想情况下，rear-length+1能算出队首元素的位置，例如，当m=8，rear=-5，length=2时，rear-length+1＝4，4就是正确的队首元素实际位置。但rear-length+1有一种极端情况无法处理，例如，当m=8，rear=1，length=5时，无法算出队首元素的实际位置，所以必须使用(1+rear+m-length)modm方法来计算。