??點(diǎn)擊上方?好好學(xué)java?，選擇?星標(biāo)?公眾號(hào)

重磅資訊、干貨，第一時(shí)間送達(dá) 今日推薦：iphone 也是辦公神器，用了就知道了，不行送你一個(gè)試試個(gè)人原創(chuàng)+1博客：點(diǎn)擊前往，查看更多 鏈接：https://segmentfault.com/a/1190000022046581

在正式進(jìn)行循環(huán)隊(duì)列學(xué)習(xí)之前，我們先來看看在順序隊(duì)列中刪除隊(duì)首元素出現(xiàn)的問題：

（1）設(shè)一個(gè)容量為capacity=8，size=5(a,b,c,d,e)的數(shù)組，左側(cè)為隊(duì)首、右側(cè)為隊(duì)尾。

file

（2）出隊(duì)一個(gè)元素后，需整體往前移動(dòng)一位

出隊(duì)：

file

整體前移一位：

file

關(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ì)列的情況。

file

1.循環(huán)隊(duì)列原理

(1)初始，數(shù)組整體為空時(shí)，隊(duì)首front、隊(duì)尾tail指向同一個(gè)位置（數(shù)組索引為0的地方）也即front==tail 時(shí)隊(duì)列為空

file

(2)當(dāng)往數(shù)組中添加元素后

file

(3)出隊(duì)一個(gè)元素，front指向新的位置

file

(4)入隊(duì)元素，tail疊加

file

(5)當(dāng)tail不能再增加時(shí)，數(shù)組前面還有空余，此時(shí)循環(huán)隊(duì)列就該出場(chǎng)了。

file

此時(shí)數(shù)組應(yīng)該變?yōu)檫@樣：

file

在往數(shù)組中添加一個(gè)元素：

file

這樣數(shù)組就已經(jīng)滿了（tail+1==front 隊(duì)列滿），開始出發(fā)擴(kuò)容操作。capacity中，浪費(fèi)一個(gè)空間。

為了tail能返回到數(shù)組的前面位置，將隊(duì)列滿的表達(dá)式變?yōu)?（tail+1）%c==front這樣數(shù)組就可以循環(huán)移動(dòng)了。

2.循環(huán)隊(duì)列代碼實(shí)現(xiàn)

新建一個(gè)類LoopQueue并實(shí)現(xiàn)接口Queue。

2.1、接口Queue代碼如下：

package Queue;public interface Queue<E> {//獲取隊(duì)列中元素個(gè)數(shù)int getSize();//隊(duì)列中元素是否為空boolean isEmpty();//入隊(duì)列void enqueue(E e);//出隊(duì)列E dequeue();//獲取隊(duì)首元素E getFront(); }

2.2、LoopQueue相關(guān)代碼：

package Queue;//循環(huán)隊(duì)列 public class LoopQueue<E> implements Queue<E> {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類中需要注意的：

（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值的說明

為了保證入隊(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ù)組防止越界

2.3、直接在LoopQueue中添加一個(gè)main函數(shù)進(jìn)行測(cè)試，相關(guān)代碼如下：

//測(cè)試用例 public static void main(String[] args) {LoopQueue<Integer> queue = new LoopQueue<Integer>();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é)果為：

file

3.循環(huán)隊(duì)列時(shí)間復(fù)雜度

file

到此我們就實(shí)現(xiàn)了一個(gè)循環(huán)隊(duì)列操作，解決了在順序隊(duì)列中出隊(duì)時(shí)的時(shí)間復(fù)雜度為O(n)的情況，在循環(huán)隊(duì)列中出隊(duì)的時(shí)間復(fù)雜度為O(1)。

總結(jié)

以上是生活随笔為你收集整理的Java 循环队列原理与用法详解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。