概念
隊(duì)列
先進(jìn)先出嗽元，后進(jìn)后出：比如生活中的排隊(duì)買票沧烈，先來的先買掠兄，后來的排隊(duì)，最后一個(gè)最后一個(gè)買掺出。
隊(duì)列徽千，又稱為佇列（queue），是先進(jìn)先出（FIFO, First-In-First-Out）的線性表汤锨。在具體應(yīng)用中通常用鏈表或者數(shù)組來實(shí)現(xiàn)双抽。隊(duì)列只允許在后端（稱為rear）進(jìn)行插入操作，在前端（稱為front）進(jìn)行刪除操作闲礼。
隊(duì)列的操作方式和堆棧類似牍汹，唯一的區(qū)別在于隊(duì)列只允許新數(shù)據(jù)在后端進(jìn)行添加铐维。
——維基百科
循環(huán)隊(duì)列
假如隊(duì)列是一個(gè)固定長度的隊(duì)列，而進(jìn)來的元素都只能往隊(duì)列的后面排慎菲，最終會排到隊(duì)列的最后一個(gè)位置嫁蛇。而前面如果有元素已經(jīng)出來空出了位置，但此時(shí)也沒法讓其他元素進(jìn)來露该，出現(xiàn)了偽溢出的現(xiàn)象（雖然隊(duì)列已經(jīng)排到尾了睬棚，但前面還有空位），而循環(huán)隊(duì)列就解決了這個(gè)問題解幼。
當(dāng)隊(duì)列排到尾抑党，而前面還有空位的話，那就從頭開始進(jìn)入撵摆。但隊(duì)列依舊遵循先進(jìn)先出的原則底靠，性質(zhì)并沒有被改變。
屬性
循環(huán)隊(duì)列需要以下的幾個(gè)屬性：
int maxSize：記錄隊(duì)列的最大容量
T[] arr：由于是固定長度特铝，所以用數(shù)組來存儲元素暑中，而長度就根據(jù)maxSize來初始化
int front：記錄隊(duì)列中頭元素的坐標(biāo)
int rear：記錄隊(duì)列中末尾元素的后一位坐標(biāo)（比如當(dāng)前最后一個(gè)元素的坐標(biāo)為2，則rear = 3）
編寫時(shí)的兩個(gè)問題：
1. 隊(duì)列空/隊(duì)列滿
判斷隊(duì)空：當(dāng)front == rear 為空
判斷隊(duì)滿：當(dāng) front == (rear+1) % maxSize 為滿
正常情況下鲫剿，當(dāng)隊(duì)列滿時(shí)鳄逾，front 和 rear 應(yīng)該指向的是同一個(gè)坐標(biāo)，但是這樣就會與隊(duì)空情況的坐標(biāo)位置一樣牵素，后續(xù)作判斷時(shí)有分歧严衬。所以這里為了方便后續(xù)判斷隊(duì)列空滿，這里假設(shè)還剩一個(gè)位置時(shí)笆呆，隊(duì)列就滿了，不再允許入隊(duì)粱挡， 此時(shí) rear 應(yīng)該在 front 的前一位赠幕。
所以當(dāng) rear+1 == front 為滿，但由于是循環(huán)隊(duì)列询筏，如上圖榕堰，rear 的坐標(biāo)為 7，7+1!=0嫌套，為此通過%取余使 (7+1)%8 == 0逆屡，同時(shí)也不影響其他坐標(biāo)情況的判斷，如 6+1 == (6+1)%8 （如下圖）
隊(duì)滿狀態(tài)
2. 有效元素個(gè)數(shù)
情況一：當(dāng) front<rear 時(shí)踱讨，size = rear - front;
情況二：當(dāng) front > rear 時(shí)魏蔗，size = rear + (maxSize-front)
為了方便，通過（rear + maxSize - front) % maxSize 公式來獲取元素個(gè)數(shù)痹筛；
這里可能有點(diǎn)轉(zhuǎn)不過彎莺治，首先要知道廓鞠，當(dāng)一個(gè)數(shù)%一個(gè)比他大的數(shù)取余，得到的結(jié)果跟原來的數(shù)是一樣的谣旁。
所以對于第一種情況床佳，rear - front 是不會大于maxSize的，那么情況一的公式加maxSize再摩爾maxSize 的結(jié)果還是會等于 rear - front
對于情況二： rear + (maxSize-front) 這個(gè)結(jié)果再摩爾maxSize 也不會被改變
實(shí)現(xiàn)代碼
public class CircularQueue<E> {
private Integer maxSize;
private E[] arr;
private Integer front = 0;
private Integer rear = 0;
/**
* 構(gòu)建時(shí)初始化存儲元素的數(shù)組
*
* @param maxSize 指定隊(duì)列的最大容量
*/
public CircularQueue2(Integer maxSize) {
this.maxSize = maxSize;
this.arr = (E[]) new Object[maxSize];
}
/**
* @return 返回當(dāng)前隊(duì)列是否為空
*/
public boolean isEmpty() {
//這里規(guī)定當(dāng) front 等于 rear 時(shí)榄审，隊(duì)列為空
if (this.front == this.rear) {
return true;
}
return false;
}
/**
* 入隊(duì)
*
* @param element
*/
public void enqueue(E element) {
//判斷隊(duì)列是否為滿(當(dāng)rear+1等于front時(shí)為滿)
if ((this.rear + 1) % this.maxSize == this.front) {
throw new RuntimeException("queue is full");
} else {
//未滿時(shí)直接入隊(duì)
this.arr[this.rear] = element;
//rear的坐標(biāo)往后移
this.rear = (this.rear + 1) % this.maxSize;
}
}
/**
* 出隊(duì)
*
* @return 返回出隊(duì)的元素
*/
public E dequeue() {
//判斷隊(duì)列是否為空
if (this.isEmpty()) {
//隊(duì)列為空拋出異常
throw new RuntimeException("queue is empty");
} else {
//先讀取隊(duì)列的頭元素
E element = this.arr[this.front];
//front坐標(biāo)后移
this.front = (this.front + 1) % this.maxSize;
return element;
}
}
/**
*
* @return 獲取隊(duì)列的頭元素
*/
public E getFront() {
return this.arr[this.front];
}
/**
*
* @return 獲取隊(duì)列的有效長度
*/
public int getSize() {
return (this.maxSize - this.front + this.rear) % this.maxSize;
}
}
