循环队列是线性结构、顺序存储结构的队列。故其一开始创建,空间大小就已经确定,无论是入队还是退队,都是在确定空间中执行,当循环队列满时,再执行插入会产生“上溢”错误,当循环队列为空时,再执行删除会产生“下溢”错误。空循环队列的初始状态为front=rear=0,当入队一个元素时,rear=rear+1,表现在循环队列中,rear=m到了rear=1的位置,如上图的第二个,再入队一个元素,rear=rear+1=2。退队一个元素,即让front=front+1,表现在循环队列中就是从front=m到front=1,此时原来位置1的元素被删除。
通过以上论述,可知,入队 *** 作指针rear,退队 *** 作front。而且front和rear的大小不能确定,可能出现以下3种情况,分别为
①front=rear,此时循环队列可能为空,也可能为满。
②front ③front>rear,如上图第2个所示,此时循环队列中的元素为(rear+m-front)个(rear代表左边的元素个数,m-front代表右边的元素个数) 1.循环队列的存储空间为 Q(1:50) ,初始状态为 front=rear=50 。经过一系列正常的入队与退队 *** 作后, front=rear=25 ,此后又插入一个元素,则循环队列中的元素个数为( A) A.1,或50且产生上溢错误 B.51 C.26 D.2 解析:front=rear说明此时循环队列可能为空也可能满。当循环队列为空时,再插入一个元素此时循环队列有1个元素;当循环队列为满时,再插入一个元素会导致上溢错误。故选A。 2.设循环队列的存储空间为Q(1:m),初始状态为空。现经过一系列正常的入队与退队 *** 作后,front=m,rear=m-1,此后从该循环队列中删除一个元素,则队列中的元素个数为(B) A.m-1 B.m-2 C.0 D.1 解析:front>rear,此时循环队列中元素有(rear+m-front)=(m-1+m-m)=(m-1)个元素,再删除一个元素,此时有(m-2)个元素。故选B。 3.设循环队列的存储空间为Q(1:m),初始状态为front=rear=m。现经过一系列正常的入队与退队 *** 作后,front=30,rear=10。现在要在该循环队列中作顺序查找,最坏情况需要比较的次数为(D) A.19 B.20 C.m-19 D.m-20 解析:循环队列最终元素个数取决于最后front和rear的位置。由于front=30>20=rear,故此时循环队列中元素个数为(rear+m-front)=(10+m-30)=(m-20)个元素。又考虑最坏情况查找元素,故考虑每个元素都比较完才找到的情况,即要进行(m-20)次。故选D。 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)