循环队列的实现

1 定义

为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。

2 理解循环队列

image

如图所示，front为循环队列头指针，rear为循环队列尾指针。

初始状态为front == rear，队列为空

每次入队一个元素，rear+1，当队列满时，front == rear，同队列为空时一样，故而无法区分队列为空还是满。

所以采取空闲一个单元格，令队满特征为 front = (rear +1)%size

3 动手实现

思路

队列头 front

队列尾 rear

队列长度 size

入队(rear + 1)%size

出队(front + 1)%size

队列空 front == rear

队列满 (rear + 1)%size == front

public class CircleQueue<E> {

    private E[] circleQueueArray;

    private int front;

    private int rear;

    private int size;

    public CircleQueue(){
        this(10);
    }

    @SuppressWarnings("unchecked")
    public CircleQueue(int size) {
        this.circleQueueArray = (E []) new Object[size + 1];
    }

    boolean enQueue(E data) throws Exception {
        if (isFull()){
            throw new Exception("The Queue is full");
        }

        circleQueueArray[rear] = data;

        rear = (rear + 1) % circleQueueArray.length;

        size++;

        return true;

    }

    public E deQueue() throws Exception{
        if (isEmpty()){
            throw new Exception("The Queue is empty");
        }

        E data = getFront();

        circleQueueArray[front] = null;

        front = (front + 1)%circleQueueArray.length;

        size--;

        return data;
    }

    public int getSize(){
        return size;
    }

    private E getFront() throws Exception {
        if (isEmpty()){
            throw new Exception("The Queue is empty");
        }
        return circleQueueArray[front];
    }

    private boolean isEmpty(){
        return rear == front;
    }

    private boolean isFull(){
        return (rear + 1) % circleQueueArray.length == front;
    }
}