Page 84 - 高中 信息技术 选择性必修1 数据与数据结构

第三章 线性数据的组织和存储

讨 论

小组内展开讨论：随着顺序队列不断有元素出队和入队，当队尾标志达到队列的最大

长度时，整个队列中还有剩余空间吗？还能继续入队吗？评价顺序队列在对存储空间的利
用率上存在什么问题，想想是否有改进的办法。
2．循环队列
当我们对顺序队列不断执行入队操作时，队列就有可能出现溢出现象。如已定义顺序

队列q，队头front，队尾rear，数组容量为6，当有元素入队时，有下面两种情况：
（1）真溢出。
广东教育出版社
当队列中的实际元素个数达到队列最大长度maxsize时，队列满，这时做入队操作将产

生空间溢出的现象，如图3-13所示。真溢出是一种出错状态，应设法避免。

图3-13 真溢出

（2）假溢出。

由于同时有入队和出队两种操作，队头标志front、队尾标志rear的值只增加不减少，
致使已出队元素的空间永远无法重新利用。当队列中的实际元素个数小于队列最大长度
（即数组容量）maxsize时，也可能由于队尾标志已达到maxsize而不能做入队操作，这时就

出现了假溢出。如图3-14所示。

图3-14 假溢出

为充分利用队列的存储空间，克服“假溢出”现象，可以将数组存储区想象为一个首
尾相接的圆环，并称存储在其中的队列为循环队列。同时，为了区别队满和队空，我们约

定：当数组中只剩下一个元素为空时，即若队尾标志继续后移一位将与队头标志重叠，就
判为队满，此时不能再做入队操作。

76 76

21X2204.indd 76 2019/9/26 13:53:17