Python二级--循环队列专题

Python二级--循环队列专题 知识点

        循环队列是线性结构、顺序存储结构的队列。故其一开始创建，空间大小就已经确定，无论是入队还是退队，都是在确定空间中执行，当循环队列满时，再执行插入会产生“上溢”错误，当循环队列为空时，再执行删除会产生“下溢”错误。空循环队列的初始状态为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。