1、普通隊列存在什么問題？

隊列大家都知道，有幾個重要的屬性：

• rear：指向隊列的尾巴，即最后一個元素所在的位置，初始值為-1
• front：指向隊列的頭部的前一個位置，初始值也為-1
• capacity：隊列的容量

空隊列的rear和front都等于-1，入隊時，front不動，rear++，當(dāng) rear == capacity - 1時，隊列已滿；出隊時，rear不動，front++，當(dāng)front == rear時，隊列為空?？雌饋砗芡昝?，但實(shí)際上有問題。假如一個隊列capacity = 3，入隊了三個元素，此時front = -1; rear = 2，然后再將三個元素都出隊，此時front = 2, rear = 2。這時隊列明明是空的，但是卻不能再入隊元素的，因?yàn)闈M足rear = capacity - 1，也就是相當(dāng)于這隊列是一次性的，用過之后就不能再用了，即使為空也不能再入隊了，造成空間的浪費(fèi)，所以環(huán)形隊列就出現(xiàn)了。

2、環(huán)形隊列實(shí)現(xiàn)思路：

環(huán)形隊列中的幾個重要屬性：

• rear：指向隊列尾巴的后一個位置，初始值為0
• front：指向隊列的頭部，即第一個元素所在的位置，初始值為0
• capacity：隊列的容量

下面是環(huán)形隊列的一些算法：

• 隊列為空時：      front == rear
• 隊列已滿時：      (rear + 1) % capacity == front
• 獲取隊列元素個數(shù)：      (rear + capacity - front) % capacity
• 入隊操作時：      rear = (rear + 1) % capacity
• 出隊操作時：      front = (front + 1) % capacity;

判斷隊列是否已滿是環(huán)形隊列中最重要也是最難理解的地方。假如有一個隊列capacity = 3，入隊操作如下：

• 第一個元素入隊：      front = 0，因?yàn)?      (rear + 1) % capacity = 1 % 3 != front，所以元素可以入隊，元素入隊后      rear = 1；
• 第二個元素入隊：      front = 0，因?yàn)?      (rear + 1) % capacity = 2 % 3 != front，所以元素可以入隊，元素入隊后      rear = 2；
• 第三個元素入隊：      front = 0，因?yàn)?      (rear + 1) % capacity = 3 % 3 == front，所以元素不能入隊，隊列已滿；

隊列容量明明是3，只入隊了兩個元素就告訴我隊列滿了？沒錯，這種判斷隊列是否已滿的算法需要犧牲數(shù)組的一個空間。

現(xiàn)在進(jìn)行出隊操作：

• 第一個元素出隊：      front = 1，      rear = 2，      (rear + 1) % capacity = 3 % 3 = 0 != front。

可以發(fā)現(xiàn)，當(dāng)一個元素出隊后，又滿足入隊條件了，所以數(shù)組空間就可以重復(fù)利用了。

3、代碼實(shí)操：

public class CircleQueue {
    private int capacity;
    private int front;
    private int rear;
    private Object[] arr;

    public CircleQueue(int capacity){
        this.capacity = capacity;
        this.arr = new Object[capacity];
        this.front = 0;
        this.rear = 0;
    }

    public boolean isFull(){
        return (rear + 1) % capacity == front;
    }

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

    public void addQueue(E e){
        if (isFull()){
            throw new RuntimeException("隊列已滿，入隊失敗");
        }
        arr[rear] = e;
        // rear指針后移
        rear = (rear + 1) % capacity;
    }

    public E getQueue(){
        if (isEmpty()){
            throw new RuntimeException("隊列為空，出隊失敗");
        }
        E val = (E) arr[front];
        front = (front + 1) % capacity;
        return val;
    }


    public int getSize(){
        return (rear + capacity - front) % capacity;
    }

    // 遍歷
    public void showQueue(){
        if (isEmpty()){
            return;
        }
        for (int i = front; i < front + getSize(); i++) {
            System.out.printf("arr[%d]=%d\n", i%capacity, arr[i%capacity]);
        }
    }

    public static void main(String[] args){
        CircleQueue queue = new CircleQueue<>(3);
        queue.addQueue(1);
        queue.addQueue(2);
        queue.showQueue();
        //queue.addQueue(3);
        System.out.println(queue.getSize());
        System.out.println(queue.getQueue());;
        queue.addQueue(3);
        queue.showQueue();
    }
}