循环队列

循环队列

https://www.jianshu.com/p/411f2d64c2c6

队列：是一种可以分别在两端进行增删的特殊线性表。既然是线性表，那么可以使用顺序存储和链式存储来实现，如果是链式存储的话，那么增删的复杂度都是O(1)，这一点很好理解，应该只要修改一下指针就好了，如果是顺序存储的话，在队尾增加的时间复杂度是O(1)，但是在队头进行删除的时候，会涉及到迁移操作，这时候的时候复杂度就是O(n)，所以一般来讲不会直接使用顺序存储的方式来实现普通队列。

较之普通队列用顺序存储来实现存在删除带来的时间损耗，怎么去避免它，因为普通队列删除队头结点，会将后续结点进行整体的一个前移，所以才会带来O(n)的时间复杂度，如果不前移结点，而是调整头结点的位置，删除一个结点，就将头结点往后移动一位。

TIP：front是指向头结点的指针，rear是指向下一个要插入结点的指针

初始状态
删除结点后 的状态

那么这样子是可以避免删除带来的时间损耗了，但是可以发现当往下标4插入数据后，rear指针该何去何从，放在脚标5？那么会报数组越界，而且很明显下标0和1的位置都空着，所以rear应该指向0才对，那么这种实现方式其实就是循环列表。

实现循环列表存在几个要考虑的事情：

1：啥时候表示队列空着？

一般在循环队列的初始状态，可以将front和rear指针都指向下标0，当插入元素时，rear会顺时针方向累加，当删除元素时，front也会顺时针方向累加，那么删的和加的一样多，其实在同一个方向走的下标也一样多，那么自然容易想到当front == rear时，表示队列为空。

只不过这里需要注意一点，因为是循环队列，front和rear的值不能无限递增，比如一个数组，大小为5，最大下标是4，难道还能4+1=5，出来个5下标，明显不可能。
所以，这里的递增，需要这么操作：(front + 1) % maxSize，巧妙的用到了取模运算符。

2：啥时候表示队列满了？

队列啥时候算满呢？其实可以发现front可能在rear的后面，也有可能在rear的前面，仔细想想可能会发现某种情况下，当rear == front也是队列满的时候，但是这样就跟队列空着的时候，判断条件一致了，这样明显也不行，
为了区分开来，单独留一个结点不存值。

当rear和front相差一个结点时，即证明循环队列已满。判断条件为：(rear + 1) % maxSize = front

3：怎么才能知道队列当前含有元素的多少?

由于循环队列的特性，队列里面的元素可能是连续的，也有可能是分成两段的，那么怎么去统计含有多少元素呢？可以使用这个公式 (rear - front + maxSize) % maxSize，因为rear - front可能为正数，也有可能会负数，为正数表示是连续的，为负数表示不连续的。