数据结构-5.队列-循环队列

使用循环队列来解决“假溢出”问题：

其实，并没有真正的环，只是用环作为类比（用长方形也可以得出同样的结论）

思路一：牺牲一个存储空间来避免冲突

首先，重新定义 front 和 rear 的定义

定义 front 为第一个元素对应的索引，可以理解为每次取出的元素位置

定义 rear 为最后一个元素的下一个元素对应的索引，可以理解为每次放入元素的位置

首先初始化队列

初始化队列，front == rear == 0 插入 ABCDEFGH 后，队列满，删除 ABCDEFGH 后，队列为空，此时 front == rear == 0

此时无法区分队列空和队列满状态，因为 rear == front 在两种情况下都成立，这意味着，无论使用何种运算方法，都无法将二者区分开。解决办法就是牺牲一个存储单位

插入 ABCDEFG 后，队列空出一个空位，删除 ABCDEFG后，队列为空

队列满时，用取模运算来判断位置 (rear + 1) % maxSize == front，则认为队列已满

队列中的有效数据个数为

（1）当 rear 比 front 大的时候，有效数据个数为 rear - front

（2）当 rear 比 front 小的时候，说明已经使用过一圈的容量了，rear + maxSize - front

总结起来为：

    (rear - front + maxSize) % maxSize

队列空时，用相等来判断 rear == front，则认为队列已空

代码实现：

相同的成员变量，不同的构造方法，注意 front 和 rear 含义的变化 为了避免冲突，而牺牲一个存储空间，导致判断队列满和队列空的变化 由于 rear 变为最后一个元素的后一个位置，直接将元素插到该位置，注意使用模运算来避免可能的索引越界 由于 front 变为第一个元素的位置，直接取得该位置的元素，注意使用模运算来避免可能的索引越界 显示队列中的有效元素，即 front 及以后 (rear + maxSize - front) % maxSize 个元素，注意使用模运算来避免可能的索引越界 查看首元素的方法

思路二：设置一个计数数据

设置一个 num，来表示队列中当前的有效数据，初始化时，其值为 0

每当有一个数据成功进入队列时，num + 1

每当有一个数据成功取出队列时，num - 1

则队列为满的时候：

rear == front == num > 0

则队列为空的时候：

num == 0

思路三：设置一个标志变量

设置一个 flag，初始值为 0

当有数据成功计入队列时，队列中有数据，flag 的值就是 1

当所有数据都被取出队列时，队列中没有数据，flag 的值就是 0

则队列为满的时候：

rear == front && flag == 1

则队列为空的时候：

rear == front && flag == 0

思路一是通过牺牲存储空间来实现的，思路二和思路三可以不牺牲空间，提倡思路三，因为在不牺牲空间的同时，掌握了队列中的有效数据个数