Question

求循环队列的元素个数算法，已知front 和 rear，还有容量数，怎么求队列中的循环元素个数？

求循环队列的元素个数算法，已知front 和 rear，还有容量数，怎么求队列中的循环元素个数？

Answer 1

如果是用数组实现的 用队尾减队头再模数组长度；如果是链表 就要有个计数变量了。

front为对头指针，rear为对尾指针，n为队列最大元素个数。队列元素个数=(rear-front+1+n)%n %是求余数。

循环队列的元素个数计算公式：

如果rear<front结果是rear-front+maxsize； 

如果rear>front结果是rear-front；

为了用一个表达式同时表达两者，用(rear-front+maxsize)%maxsize；

假设maxsize=10；

rear=1 front=9，那么结果是2；

rear=9 front=1，那么结果是8。

扩展资料

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

解决这个问题的方法至少有两种：

① 另设一布尔变量以区别队列的空和满；

②另一种方式就是数据结构常用的： 队满时：(rear+1)%n==front，n为队列长度（所用数组大小），由于rear，front均为所用空间的指针，循环只是逻辑上的循环，所以需要求余运算。

队已满，但是rear（5）+1=6！=front（0），对空间长度求余，作用就在此6%6=0=front（0）。

Answer 2

当rear > front时，元素个数为rear - front, 当rear <= front时，元素个数为rear-front+capacity
综上述两种情况，可得元素个数为(rear-front+capacity)%capacity，其中capacity表循环队列容量。

Answer 3

如果是用数组实现的 用队尾减队头再模数组长度
如果是链表 就要有个计数变量了