数据结构：循环队列（循环数组实现）

为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

上一篇博客 数据结构：简单顺序队列的数组实现 中，我通过在进行出队操作的时候将元素整体向前移动一位的方式来克服“假溢出”现象，但是移动元素的操作对于数组来说是十分费时的，因为在理想情况下的顺序队列，入队、出队操作时间复杂度都是O(1)，但是涉及到元素的移动就会导致时间复杂度就变成O(n)，所以更好的实现办法就是通过循环队列来克服“假溢出”。

下面通过循环数组的方式来实现循环队列，其中有几个很经典的公式：

1. 队列空： front == rear
2. 队列满：(rear + 1) % N == front
3. 队列元素个数：(rear - front + N) % N
   

实现代码如下：

/**
 * @author lichen
 * @version 1.0.0
 * @date 2020-05-13 18:56
 */
class MyCircularQueue {

    int[] elements;
    int front;
    int rear;

    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        // initSize + 1 是因为需要一个位置空出来存放指针，所以实际存储的元素要比数组长度小1 
        elements = new int[k + 1];
    }

    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = rear + 1 >= elements.length ? 0 : rear + 1;
        return true;
    }

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        Object data = elements[front];
        // GC回收
        elements[front] = 0;
        front = front + 1 >= elements.length ? 0 : front + 1;
        return true;
    }

    /** Get the front item from the queue. */
    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return elements[front];
    }

    /** Get the last item from the queue. */
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        if (rear == 0) {
            return elements[elements.length - 1];
        } else {
            return elements[rear - 1];
        }
    }

    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        return front == rear;
    }

    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        return (rear + 1) % elements.length == front;
    }

    public static void main(String[] args) {
//        MyCircularQueue queue = new MyCircularQueue(2);
//        System.out.println(String.format("入队  %s", queue.enQueue(4)) + "  " + queue.front + "  " + queue.rear);
//        System.out.println(queue.Rear());
//        System.out.println(String.format("入队  %s", queue.enQueue(9)) + "  " + queue.front + "  " + queue.rear);
//        System.out.println(String.format("出队  %s", queue.deQueue()) + "  " + queue.front + "  " + queue.rear);
//        System.out.println(queue.Front());
//        System.out.println(String.format("出队  %s", queue.deQueue()) + "  " + queue.front + "  " + queue.rear);
//        System.out.println(String.format("出队  %s", queue.deQueue()) + "  " + queue.front + "  " + queue.rear);
//        System.out.println(queue.isEmpty());
//        System.out.println(String.format("出队  %s", queue.deQueue()) + "  " + queue.front + "  " + queue.rear);
//        System.out.println(String.format("入队  %s", queue.enQueue(6) + "  " + queue.front + "  " + queue.rear));
//        System.out.println(String.format("入队  %s", queue.enQueue(4) + "  " + queue.front + "  " + queue.rear));

        MyCircularQueue queue = new MyCircularQueue(3);
        System.out.println(String.format("入队  %s", queue.enQueue(1)) + "  " + queue.front + "  " + queue.rear);
        System.out.println(String.format("入队  %s", queue.enQueue(2)) + "  " + queue.front + "  " + queue.rear);
        System.out.println(String.format("入队  %s", queue.enQueue(3)) + "  " + queue.front + "  " + queue.rear);
        System.out.println(String.format("入队  %s", queue.enQueue(4)) + "  " + queue.front + "  " + queue.rear);
        System.out.println(queue.Rear());
        System.out.println(queue.isFull());
        System.out.println(String.format("出队  %s", queue.deQueue()) + "  " + queue.front + "  " + queue.rear);
        System.out.println(String.format("入队  %s", queue.enQueue(4) + "  " + queue.front + "  " + queue.rear));
        System.out.println(queue.Rear());

    }
}