采用循环队列的优点是()

A.入队和出队可以在队列的同端点进行操作

B.入队和出队操作都不需要移动队列中的其他元素

C.避免出现队列满的情况

D.避免出现队列空的情况

请先 登录 后评论

1 个回答

亚里士德
擅长:互联网

2010、2013、2015、2021年下半年都考了循环队列。

书上在106页解释了循环队列。根据书上面的中文文字描述,可以使用排除法。

A选项,循环队列就相当于没有端点了(有头结点和尾节点),而且书上的过程描述,新增和删除节点是移动的队尾、队头节点指针。

B选项,可能需要读一下书上给的示例源码。选B。

CD选项,书中演示过程中是包含空队列和满队列的情况的。


往年题目:

1、给出队列容量M、真实队列长度size、对头节点位置front、队尾指针指向最后一个元素,要求队尾指针rear和前面的关系(2013年。2010年给出尾指针要求计算头指针)。

2、或者给出队列头结点front、尾节点rear、队列容量M,要求真实队列长度size(2015年)。


书上总共就说了这些:

循环队列想象是一个首尾相连的圆圈,有最大值M,真实的队列值就在圆圈内排列。

开始时,Q.rear=Q.front=0。

元素入队时,修改队尾指针Q.rear = (Q.rear+l)%MAXSIZE,如图3-8 (b)所示。

元素出队时,修改队头指针Q.front = (Q.front+l)%MAXSIZE,如图3-8 (c)所示。

当出队操作导致队列变为空时,则有Q.rear=Q.front,如图3-8 (d)所示;

若入队操作导致队列满,则Q.rear=Q.front。


总结可以发现,头结点+真实的size好像就可以确定尾节点的位置,但是因为它是一个环,所以尾节点位置还有可能会比头结点小的情况,所以需要把环的值考虑进去。所以,如果尾节点指向的是最后一个元素,那么: (Q.front+Q.size−1+M)%M = Q.rear。就是(头结点位置+实际长度+环的长度-1)除以环的长度取余数,就是尾节点的位置。如果是书上举的例子尾节点在最后节点的后一个节点,那么就不用减一了。


全是文字可能有点硬,建议看看书上的例子,这个知识点的图片还是很形象的。

请先 登录 后评论