数组实现队列之循环队列

对于链表实现方式，队列的入队、出队操作和栈是大同小异的。但对于数组实现方式来说，因为数组的长度固定，队列的入队和出队操作有了一些有趣的变化。

队列为队尾入队，对头出队，但如果不断出队，对头的左边就会失去作用，如下图：

image.png

在数组不做扩容的前提下，如何让新元素入队并确定新的队尾位置呢？我们可以利用已出队元素留下的空间，让队尾指针重新指回数组的首位。

image.png
这样一来，整个队列的元素就“循环”起来了。在物理存储上，队尾的位置也可以在队头之前。当再有元素入队时，将其放入数组的首位，队尾指针继续后移即可。
image.png

一直到（队尾下标+1）%数组长度 = 队头下标时，代表此队列真的已经满了。需要注意的是，队尾指针指向的位置永远空出1位，所以队列最大容量比数组长度小1。

image.png
循环队列不但充分利用了数组的空间，还避免了数组元素整体移动的麻烦，还真是有点意思呢！至于入队和出队的时间复杂度，都同样是O(1)
具体代码实现：

private int[] array;
private int front;
private int rear;

public MyQueue(int capacity){
    this.array = new int[capacity];
}
/**
 * 入队
 * @param element 入队的元素
 */
public void enQueue(int element) throws Exception {
    if((rear+1)%array.length == front){
        throw new Exception(" 队列已满！");
    }
    array[rear] = element;
    rear =(rear+1)%array.length;
}

/**
* 出队
*/
public int deQueue() throws Exception {
    if(rear == front){
        throw new Exception(" 队列已空！");
    }
    int deQueueElement = array[front];
    front =(front+1)%array.length;
    return deQueueElement;
}

/**
* 输出队列
*/
public void output(){
    for(int i=front; i!=rear; i=(i+1)%array.length){
        System.out.println(array[i]);
    }
}

public static void main(String[] args) throws Exception {
    MyQueue myQueue = new MyQueue(6);
    myQueue.enQueue(3);
    myQueue.enQueue(5);
    myQueue.enQueue(6);
    myQueue.enQueue(8);
    myQueue.enQueue(1);
    myQueue.deQueue();
    myQueue.deQueue();
    myQueue.deQueue();
    myQueue.enQueue(2);
    myQueue.enQueue(4);
    myQueue.enQueue(9);
    myQueue.output();
}