问题
你是不是有个疑问，关于循环队列，在取循环队列的头指针和尾指针的时候，直接加减不就好了，为什么要取模呢？
解决
循环队列的概念：

循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。


出队时：Q.Front++
入队时：Q.Front++

这样每次不管是入队还是出队，指针数都会++，如果不取模，就容易造成指针溢出。

循环队列

循环队列，解决出队列时时间复杂度是O(n)的问题
在循环队列中，设置两个索引front、tail
当front == tail时，队列为空
当tail+1 == front时，队列满：(tail +1)%data.length == front
在循环队列中浪费一个空间
循环队列不再使用之前我们实现的动态数组作为底层实现
循环队列的出队的时间复杂度与入队的时间复杂度均为O(1)，均摊时间复杂度

/**
 * 循环队列，解决出队列时时间复杂度是O(n)的问题
 * 在循环队列中，设置两个索引front、tail
 * 当front == tail时，队列为空
 * 当tail+1 == front时，队列满：(tail +1)%data.length == front
 * 在循环队列中浪费一个空间
 * 循环队列不再使用之前我们实现的动态数组作为底层实现
 * 循环队列的出队的时间复杂度与入队的时间复杂度均为O(1)，均摊时间复杂度
 *
 * @author f242
 * @since V1.0.0
 * 2020-03-21 15:00
 */
public class LoopQueue<E> implements Queue<E>{

    private E[] data;
    private int front,tail;
    private int size;

    public LoopQueue(int capacity){
        //在循环队列的实现中我们有意识的浪费一个空间
        data = (E[])new Object[capacity+1];
        front = 0;
        tail = 0;
        size =0;
    }

    public LoopQueue(){
        this(10);
    }

    public int getCapacity(){
        return data.length -1;
    }

    @Override
    public boolean isEmpty(){
        return front == tail;
    }

    @Override
    public int getSize(){
        return size;
    }

    @Override
    public void enqueue(E e){
        //判断当前队列是否满
        if((tail +1)%data.length == front){
            //扩容
            resize(2 * getCapacity());
        }
        data[tail] = e;
        tail = (tail+1) % data.length;
        size ++;
    }
    @Override
    public E dequeue(){
        if(isEmpty()){
            throw  new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        E ret = data[front];
        data[front] = null;
        front = (front +1)%data.length;
        size --;
        if(size == getCapacity()/4 && getCapacity()/2 !=0){
            resize(getCapacity()/2);
        }
        return ret;
    }

    @Override
    public E getFront(){
        if(isEmpty()){
            throw new IllegalArgumentException("Queue is Empty");
        }
        return data[front];
    }

    private void resize(int newCapacity){
        E[] newData = (E[])new Object[newCapacity+1];
        for(int i=0;i<size;i++){
            newData[i] = data[(i+front)%data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("LoopQueue:size = %d, capacity = %d\n",size,getCapacity()));
        res.append("front [");
        for(int i=front;i !=tail;i=(i+1)%data.length){
            res.append(data[i]);
            if((i+1)%data.length !=tail){
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }
}

循环队列样式结构图：



优点：

解决了顺序队列只能从队尾插入元素而导致空间的浪费；

问题：

在循环队列中，空队特征是front = rear, 队满时也会有front = rear; 判断条件将出现二义性；
解决方法
1、使用额外的标记

（1）引入Size标记

来记录队列的长度，当size为队列最大长度时为满，size=0为空；

（2）引入tag标记

删除时tag=0，插入时tag=1；当front == rear时，如果 tag==0则为空，否则为满；

2、仅使用n-1个数组空间
空闲单元法：


循环队列满的条件：

（rear+1）% N == front；

循环队列空的条件：

（front==rear）；

前言
循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。其将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。在循环队列中，当队列为空时，有front=tail，而当所有队列空间全占满时，也有front=tail。为了区别这两种情况，规定循环队列最多只能有capacity-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是front=tail，而队列判满的条件是front =(tail+1)%capacity，如下图所示：

具体实现

接口

public interface Queue<T> {

    /**
     * 添加元素
     * @param t
     */
    void enqueue(T t);

    /**
     * 元素出队
     * @return
     */
    T dequeue();

    /**
     * 获取队首元素
     * @return
     */
    T getFront();

    /**
     * 获取队列长度
     * @return
     */
    int getSize();

    /**
     * 是否为空
     * @return
     */
    boolean isEmpty();
}


实现类

public class LoopQueue<T> implements Queue<T> {

    /**
     * 数组
     */
    private T[] data;

    /**
     * 元素起始与结束位置
     */
    private int front, tail;

    /**
     * 大小
     */
    private int size;

    /**
     * 构造函数
     * @param capacity
     */
    public LoopQueue(int capacity) {
        data = (T[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    /**
     * 无参构造函数
     */
    public LoopQueue() {
        this(10);
    }

    /**
     * 获取容量
     * @return
     */
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * 是否为空
     * @return
     */
    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    /**
     * 获取大小
     * @return
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 添加元素
     * @param t
     */
    @Override
    public void enqueue(T t) {
        if ((tail + 1) % data.length == front) {
            // 数组扩容
            resize(2 * getCapacity());
        }

        data[tail] = t;
        tail = (tail + 1) % data.length;
        size ++;
    }

    /**
     * 数组增减容
     * @param newCapacity
     */
    private void resize(int newCapacity) {
        T[] newData = (T[]) new Object[newCapacity + 1];

        for (int i = 0; i < size; i++) {
            newData[i] = data[(i + front) % data.length];
        }

        data = newData;
        front = 0;
        tail = size;
    }

    /**
     * 元素出队
     * @return
     */
    @Override
    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty dequeue.");
        }

        T res = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size --;

        // 数组减容
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }

        return res;
    }

    /**
     * 获取队首元素
     * @return
     */
    @Override
    public T getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is Empty.");
        }
        return data[front];
    }

    /**
     * 重写toString方法
     * @return
     */
    @Override
    public String toString() {
        StringBuilder resp = new StringBuilder();
        resp.append(String.format("Queue: size = %d, capacity = %d, front [", size, getCapacity()));
        for (int i = front; i != tail; i = (i + 1) % data.length) {
            resp.append(data[i]);

            if ((i + 1) % data.length != tail) {
                resp.append(",");
            }

        }

        resp.append("] tail");

        return resp.toString();
    }

    public static void main(String[] args) {
        LoopQueue<Integer> arrayQueue = new LoopQueue<>();
        for (int i = 0; i < 10; i++) {
            arrayQueue.enqueue(i);
            System.out.println(arrayQueue);

            if (i % 3 == 2) {
                arrayQueue.dequeue();
                System.out.println(arrayQueue);
            }
        }
    }
}

.end