Question

二级计算机知识, 循环队列

Answer 1

循环队列的容量为50，如果头指针front=45(指向队头元素的前一个位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有15元素。50-45+10=15。

循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。

解决这个问题的方法至少有两种：一种为另设一布尔变量以区别队列的空和满；另一种方式就是数据结构常用的： 队满时：(rear+1)%n==front，n为队列长度（所用数组大小）。由于rear，front均为所用空间的指针，循环只是逻辑上的循环，所以需要求余运算。

类型定义采用环状模型来实现队列，各数据成员的意义如下：front指定队首位置，删除一个元素就将front顺时针移动一位；rear指向元素要插入的位置，插入一个元素就将rear顺时针移动一位；count存放队列中元素的个数，当count等于MaxQSize时，不可再向队列中插入元。

扩展资料：

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置。

即将存储空间的第一个位置作为队尾。 循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。

为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1)%MaxSize。

参考资料来源：百度百科-循环队列