使用循环队列来解决“假溢出”问题：
其实，并没有真正的环，只是用环作为类比（用长方形也可以得出同样的结论）
思路一：牺牲一个存储空间来避免冲突
首先，重新定义 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
思路一是通过牺牲存储空间来实现的，思路二和思路三可以不牺牲空间，提倡思路三，因为在不牺牲空间的同时，掌握了队列中的有效数据个数
网友评论