一昔期、普通隊(duì)列的弊端
隊(duì)列：是一種可以分別在兩端進(jìn)行增刪的特殊線性表。既然是線性表佛玄，那么可以使用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)來(lái)實(shí)現(xiàn)硼一，如果是鏈?zhǔn)酱鎯?chǔ)的話(huà)，那么增刪的復(fù)雜度都是O(1)梦抢，這一點(diǎn)很好理解般贼，應(yīng)該只要修改一下指針就好了，如果是順序存儲(chǔ)的話(huà)，在隊(duì)尾增加的時(shí)間復(fù)雜度是O(1)哼蛆，但是在隊(duì)頭進(jìn)行刪除的時(shí)候蕊梧，會(huì)涉及到遷移操作，這時(shí)候的時(shí)候復(fù)雜度就是O(n)人芽，所以一般來(lái)講不會(huì)直接使用順序存儲(chǔ)的方式來(lái)實(shí)現(xiàn)普通隊(duì)列望几。
二、循環(huán)隊(duì)列的原理概述
較之普通隊(duì)列用順序存儲(chǔ)來(lái)實(shí)現(xiàn)存在刪除帶來(lái)的時(shí)間損耗萤厅，怎么去避免它橄抹，因?yàn)槠胀?duì)列刪除隊(duì)頭結(jié)點(diǎn)，會(huì)將后續(xù)結(jié)點(diǎn)進(jìn)行整體的一個(gè)前移惕味，所以才會(huì)帶來(lái)O(n)的時(shí)間復(fù)雜度楼誓，如果不前移結(jié)點(diǎn)，而是調(diào)整頭結(jié)點(diǎn)的位置名挥，刪除一個(gè)結(jié)點(diǎn)疟羹，就將頭結(jié)點(diǎn)往后移動(dòng)一位。
TIP：front是指向頭結(jié)點(diǎn)的指針禀倔，rear是指向下一個(gè)要插入結(jié)點(diǎn)的指針
那么這樣子是可以避免刪除帶來(lái)的時(shí)間損耗了榄融，但是可以發(fā)現(xiàn)當(dāng)往下標(biāo)4插入數(shù)據(jù)后，rear指針該何去何從救湖，放在腳標(biāo)5愧杯？那么會(huì)報(bào)數(shù)組越界，而且很明顯下標(biāo)0和1的位置都空著鞋既，所以rear應(yīng)該指向0才對(duì)力九，那么這種實(shí)現(xiàn)方式其實(shí)就是循環(huán)列表。
實(shí)現(xiàn)循環(huán)列表存在幾個(gè)要考慮的事情：
1：啥時(shí)候表示隊(duì)列空著邑闺？
一般在循環(huán)隊(duì)列的初始狀態(tài)跌前，可以將front和rear指針都指向下標(biāo)0，當(dāng)插入元素時(shí)陡舅，rear會(huì)順時(shí)針?lè)较蚶奂拥峙遥?dāng)刪除元素時(shí)，front也會(huì)順時(shí)針?lè)较蚶奂影醒埽敲磩h的和加的一樣多臂寝，其實(shí)在同一個(gè)方向走的下標(biāo)也一樣多，那么自然容易想到當(dāng)front == rear時(shí)摊灭，表示隊(duì)列為空。只不過(guò)這里需要注意一點(diǎn)败徊，因?yàn)槭茄h(huán)隊(duì)列帚呼，front和rear的值不能無(wú)限遞增，比如一個(gè)數(shù)組，大小為5煤杀，最大下標(biāo)是4眷蜈，難道還能4+1=5，出來(lái)個(gè)5下標(biāo)沈自，明顯不可能酌儒，所以，這里的遞增枯途，需要這么操作：
(front + 1) % maxSize忌怎，巧妙的用到了取模運(yùn)算符。
2：啥時(shí)候表示隊(duì)列滿(mǎn)了酪夷？
隊(duì)列啥時(shí)候算滿(mǎn)呢榴啸？其實(shí)可以發(fā)現(xiàn)front可能在rear的后面，也有可能在rear的前面晚岭，仔細(xì)想想可能會(huì)發(fā)現(xiàn)某種情況下鸥印，當(dāng)rear == front也是隊(duì)列滿(mǎn)的時(shí)候，但是這樣就跟隊(duì)列空著的時(shí)候坦报，判斷條件一致了库说，這樣明顯也不行，為了區(qū)分開(kāi)來(lái)片择，單獨(dú)留一個(gè)結(jié)點(diǎn)不存值潜的，當(dāng)rear和front相差一個(gè)結(jié)點(diǎn)時(shí)，即證明循環(huán)隊(duì)列已滿(mǎn)构回。判斷條件為：(rear + 1) % maxSize = front
3：怎么才能知道隊(duì)列當(dāng)前含有元素的多少?
由于循環(huán)隊(duì)列的特性夏块，隊(duì)列里面的元素可能是連續(xù)的，也有可能是分成兩段的纤掸，那么怎么去統(tǒng)計(jì)含有多少元素呢脐供？可以使用這個(gè)公式(rear - front + maxSize) % maxSize，因?yàn)閞ear - front可能為正數(shù)借跪，也有可能會(huì)負(fù)數(shù)政己，為正數(shù)表示是連續(xù)的，為負(fù)數(shù)表示不連續(xù)的掏愁。
三歇由、循環(huán)隊(duì)列的實(shí)現(xiàn)-java
public class CircularQueue<E> {
/**
* 循環(huán)隊(duì)列
*/
/**
* 循環(huán)隊(duì)列常用的方法如下：
* 1、InitCircularQueue() 初始化一個(gè)循環(huán)隊(duì)列
* 2果港、ClearCircularQueue() 清空一個(gè)循環(huán)隊(duì)列
* 3沦泌、CircularEmpty() 判斷循環(huán)隊(duì)列是否為空
* 4、GetHead() 獲取循環(huán)隊(duì)列尾部結(jié)點(diǎn)數(shù)據(jù)
* 5辛掠、EnCircularQueue() 在循環(huán)隊(duì)列尾部插入新結(jié)點(diǎn)
* 6谢谦、DeCircularQueue() 刪除循環(huán)隊(duì)列頭部結(jié)點(diǎn)
* 7释牺、CircularQueueLength() 返回循環(huán)隊(duì)列的長(zhǎng)度
*/
Object[] queueArray = null;
int front; //隊(duì)頭指針
int rear; //隊(duì)尾指針
int maxQueueSize;
public CircularQueue(int maxSize){
// 初始化循環(huán)隊(duì)列的基礎(chǔ)存儲(chǔ)結(jié)構(gòu)，數(shù)組
this.maxQueueSize = maxSize;
this.queueArray = new Object[maxSize];
this.front = 0; //隊(duì)頭指針指向循環(huán)隊(duì)列的第一個(gè)結(jié)點(diǎn)回挽，初始為0
this.rear = 0;//隊(duì)尾指針指向循環(huán)隊(duì)列的待插入結(jié)點(diǎn)位置没咙，初始為0
}
public void ClearCircularQueue(){
if (front == rear){return;}
//清空一個(gè)循環(huán)隊(duì)列，只需要從front開(kāi)始千劈，一直到rear-1祭刚，將節(jié)點(diǎn)元素賦值成null
for (;front != rear;){
DeCircularQueue();
}
}
public Boolean CircularEmpty(){
if (front == rear){return true;}
else{return false;}
}
public E GetHead(){
return (E)queueArray[front];
}
public void EnCircularQueue(E elem){
//滿(mǎn)足(rear+1)%maxSize=front說(shuō)明該循環(huán)隊(duì)列已經(jīng)達(dá)到滿(mǎn)隊(duì)列狀態(tài)，無(wú)法在插入
if ((rear + 1) % maxQueueSize == front){
return;
}
queueArray[rear] = elem;
//循環(huán)隊(duì)列在rear指針時(shí)墙牌，如果只是簡(jiǎn)單累加涡驮，很可能會(huì)出現(xiàn)空指針異常
rear = (rear + 1) % maxQueueSize;
}
public E DeCircularQueue (){
//滿(mǎn)足front = rear時(shí)，說(shuō)明隊(duì)列為空
if (front == rear){return null;}
E returnElem = (E)queueArray[front];
queueArray[front] = null;
front = (front + 1) % maxQueueSize;
return returnElem;
}
public int CircularQueueLength(){
return (rear - front + maxQueueSize) % maxQueueSize;
}
public String toString(){
StringBuffer stringBuffer = new StringBuffer();
for (int index = 0;index < maxQueueSize;index++){
if (index + 1 < maxQueueSize){
stringBuffer.append(queueArray[index]);
stringBuffer.append(",");
}else{
stringBuffer.append(queueArray[index]);
}
}
return stringBuffer.toString();
}
public static void main(String[] args) {
}
}
四憔古、循環(huán)隊(duì)列時(shí)間復(fù)雜度分析
可以很明顯發(fā)現(xiàn)遮怜，循環(huán)隊(duì)列的增刪操作時(shí)間復(fù)雜度都是O(1)，并且還能實(shí)現(xiàn)充分利用申請(qǐng)到的空間鸿市，所以如果能夠確認(rèn)一個(gè)隊(duì)列的大小锯梁，那么就使用順序方式來(lái)實(shí)現(xiàn)，并且是循環(huán)隊(duì)列焰情，而不是普通隊(duì)列陌凳。如果確認(rèn)不了，那么還是使用鏈?zhǔn)椒绞絹?lái)實(shí)現(xiàn)内舟。
