1、普通隊(duì)列存在什么問(wèn)題？

隊(duì)列大家都知道，有幾個(gè)重要的屬性：

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

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

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

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

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

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

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

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

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

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

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

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

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

3、代碼實(shí)操：

public class CircleQueue<E> {
    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("隊(duì)列已滿，入隊(duì)失敗");
        }
        arr[rear] = e;
        // rear指針后移
        rear = (rear + 1) % capacity;
    }

    public E getQueue(){
        if (isEmpty()){
            throw new RuntimeException("隊(duì)列為空，出隊(duì)失敗");
        }
        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<Integer> 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();
    }
}