请教一道关于循环队列的数据结构题

2024年11月29日 20:51
有2个网友回答
网友(1):

可以想象把对尾指针移动到队首需要走多远?
队尾指针想移动到队首,首先需要rear - length + 1。

例如,队伍中有3个元素,队尾指针指向第3个元素,想移动到队首,要向前移动2次就能到达第一个元素。(rear-3+1)

不过,因为rear的值不定(在0与m之间),所以rear-3+1就有可能小于0!也就是说数组的下标小于0,这是不行的。例如数组有12格时候,下标等于-2,那么它本来应该是10。就像钟表,-2点就是10点。算法是(-2+12) mod 12。6点还是6点,算法(6+12) mod 12。
所以把结果加一个m再mod m(其实加几个m都是可以的)
即rear + m + 1 - length。

网友(2):

队列长度应该为:(rear
-
front
+
m)%
m
循环队列主要是两种情况:
1.front在上面,比如一个长度为5的循环队列:-代表空,x代表有数据
|-------5|
|-------4|
<-rear
|xxxxxx3|
|xxxxxx2|<-front
|-------1|
那么队列的长度是rear-front是没有问题的
2.由于是循环队列,入队的时候从尾巴进,出来的时候从front出来,如果情况1再进来2个元素就变为
|xxxxx5|
|xxxxx4|
|xxxxx3|
|xxxxx2|<-front
|-------|<-rear
显然,这种情况下用rear-front得出来的结果就不正确了,所以就出来上面的公式了
其实我觉得取绝对值也可以吧