本文實(shí)例講述了Java循環(huán)隊(duì)列原理與用法。分享給大家供大家參考，具體如下：
創(chuàng)新互聯(lián)是一家專業(yè)提供長(zhǎng)泰企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、H5建站、小程序制作等業(yè)務(wù)。10年已為長(zhǎng)泰眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站建設(shè)公司優(yōu)惠進(jìn)行中。
在正式進(jìn)行循環(huán)隊(duì)列學(xué)習(xí)之前，我們先來(lái)看看在順序隊(duì)列中刪除隊(duì)首元素出現(xiàn)的問(wèn)題
（1）設(shè)一個(gè)容量為capacity=8，size=5(a,b,c,d,e)的數(shù)組，左側(cè)為隊(duì)首、右側(cè)為隊(duì)尾。
（2）出隊(duì)一個(gè)元素后，需整體往前移動(dòng)一位
#出隊(duì)
#2整體前移一位
關(guān)于該種操作方式我們很容易得出時(shí)間復(fù)雜度為O(n)。
這時(shí)我們就想可不可以在出隊(duì)元素后，整體元素不往前移，而是在數(shù)組中記下隊(duì)首front是誰(shuí)，同時(shí)隊(duì)尾tail指向在下一次元素入隊(duì)時(shí)的位置，這樣當(dāng)再有出隊(duì)時(shí)只需要維護(hù)一下front的指向即可，而不需移動(dòng)元素。就這樣我們就有了循環(huán)隊(duì)列的情況。
(1)初始，數(shù)組整體為空時(shí)，隊(duì)首front、隊(duì)尾tail指向同一個(gè)位置（數(shù)組索引為0的地方）也即front==tail 時(shí)隊(duì)列為空
(2)當(dāng)往數(shù)組中添加元素后，
(3)出隊(duì)一個(gè)元素，front指向新的位置
(4)入隊(duì)元素，tail疊加
(5)當(dāng)tail不能再增加時(shí)，數(shù)組前面還有空余，此時(shí)循環(huán)隊(duì)列就該出場(chǎng)了。
此時(shí)數(shù)組應(yīng)該變?yōu)檫@樣：
在往數(shù)組中添加一個(gè)元素：
這樣數(shù)組就已經(jīng)滿了（tail+1==front 隊(duì)列滿），開(kāi)始出發(fā)擴(kuò)容操作?！綾apacity中，浪費(fèi)一個(gè)空間】。
為了tail能返回到數(shù)組的前面位置，將隊(duì)列滿的表達(dá)式變?yōu)?【（tail+1）%c==front】這樣數(shù)組就可以循環(huán)移動(dòng)了。
新建一個(gè)類(lèi)LoopQueue并實(shí)現(xiàn)接口Queue。
#1：接口Queue代碼如下：
package Queue; public interface Queue{ //獲取隊(duì)列中元素個(gè)數(shù) int getSize(); //隊(duì)列中元素是否為空 boolean isEmpty(); //入隊(duì)列 void enqueue(E e); //出隊(duì)列 E dequeue(); //獲取隊(duì)首元素 E getFront(); }
#2：LoopQueue相關(guān)代碼：
package Queue; //循環(huán)隊(duì)列 public class LoopQueueimplements Queue { private E[] data; private int front, tail; private int size;//隊(duì)列中元素個(gè)數(shù) //構(gòu)造函數(shù)，傳入隊(duì)列的容量capacity構(gòu)造函數(shù) public LoopQueue(int capacity) { data = (E[]) new Object[capacity + 1];//浪費(fèi)與一個(gè)空間 front = 0; tail = 0; size = 0; } //無(wú)參構(gòu)造函數(shù)，默認(rèn)隊(duì)列的容量capacity=10 public LoopQueue() { this(10); } //真正容量 public int getCapacity() { return data.length - 1; } //隊(duì)列是否為空 @Override public boolean isEmpty() { return front == tail; } //隊(duì)列中元素個(gè)數(shù) @Override public int getSize() { return size; } //入隊(duì)列操作 @Override public void enqueue(E e) { if ((tail + 1) % data.length == front) {//隊(duì)列已滿，需要擴(kuò)容 resize(getCapacity() * 2); } data[tail] = e; tail = (tail + 1) % data.length; size++; } //出隊(duì)操作 @Override public E dequeue() { if (isEmpty()) { throw new IllegalArgumentException("隊(duì)列為空"); } E ret = data[front]; data[front] = null;//手動(dòng)釋放 front = (front + 1) % data.length; size--; if (size == getCapacity() / 4 && getCapacity() / 2 != 0) { resize(getCapacity() / 2); } return ret; } //獲取隊(duì)首元素 @Override public E getFront() { if (isEmpty()) { throw new IllegalArgumentException("隊(duì)列為空"); } return data[front]; } //改變?nèi)萘? private void resize(int newCapacity) { E[] newData = (E[]) new Object[newCapacity + 1]; for (int i = 0; i < size; i++) { newData[i] = data[(front + i) % data.length];//循環(huán)數(shù)組防止越界 } data = newData; front = 0; tail = size; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("Queue:size=%d, capacity=%d\n", size, getCapacity())); res.append("front ["); for (int i = front; i != tail; i = (i + 1) % data.length) { res.append(data[i]); if ((i + 1) % data.length != tail) { res.append(","); } } res.append("] tail"); return res.toString(); } }
在關(guān)于LoopQueue類(lèi)中需要注意的：
（1）第11行中的+1是capacity需要浪費(fèi)一個(gè)空間，故在實(shí)例化是多加1
data = (E[]) new Object[capacity + 1];//浪費(fèi)與一個(gè)空間
（2）地24行真正的容量是data.length-1，這是由于有一個(gè)空間是浪費(fèi)的。
data.length - 1;
（3）關(guān)于入隊(duì)中第46行tail值的說(shuō)明
為了保證入隊(duì)是循環(huán)操作，tail值的變化規(guī)律為
tail = (tail + 1) % data.length;
（4）關(guān)于82行的數(shù)據(jù)遷移操作，取余操作是為了防止循環(huán)數(shù)組時(shí)越界。
newData[i] = data[(front + i) % data.length];//循環(huán)數(shù)組防止越界
#3直接在LoopQueue中添加一個(gè)main函數(shù)進(jìn)行測(cè)試，相關(guān)代碼如下：
重慶分公司
重慶分公司
//測(cè)試用例
public static void main(String[] args) {
LoopQueue queue = new LoopQueue();
for (int i = 0; i < 10; i++) {
queue.enqueue(i);
System.out.println(queue);
if(i%3==2){//每添加3個(gè)元素出隊(duì)列一個(gè)
queue.dequeue();
System.out.println(queue);
}
}
} 結(jié)果為：
到此我們就實(shí)現(xiàn)了一個(gè)循環(huán)隊(duì)列操作，解決了在順序隊(duì)列中出隊(duì)時(shí)的時(shí)間復(fù)雜度為O(n)的情況，在循環(huán)隊(duì)列中出隊(duì)的時(shí)間復(fù)雜度為O(1)。
源碼地址 https://github.com/FelixBin/dataStructure/blob/master/src/Queue/LoopQueue.java
更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。
