本文實例講述了Java循環隊列原理與用法。分享給大家供大家參考，具體如下：

在正式進行循環隊列學習之前，我們先來看看在順序隊列中刪除隊首元素出現的問題

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

（2）出隊一個元素后，需整體往前移動一位

#出隊

#2整體前移一位

關于該種操作方式我們很容易得出時間復雜度為O(n)。

這時我們就想可不可以在出隊元素后，整體元素不往前移，而是在數組中記下隊首front是誰，同時隊尾tail指向在下一次元素入隊時的位置，這樣當再有出隊時只需要維護一下front的指向即可，而不需移動元素。就這樣我們就有了循環隊列的情況。

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

(2)當往數組中添加元素后，

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

(4)入隊元素，tail疊加

(5)當tail不能再增加時，數組前面還有空余，此時循環隊列就該出場了。

此時數組應該變為這樣：

在往數組中添加一個元素：

這樣數組就已經滿了（tail+1==front 隊列滿），開始出發擴容操作。【capacity中，浪費一個空間】。

為了tail能返回到數組的前面位置，將隊列滿的表達式變為 【（tail+1）%c==front】這樣數組就可以循環移動了。

新建一個類LoopQueue并實現接口Queue。

#1：接口Queue代碼如下：

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

#2：LoopQueue相關代碼：

package Queue;//循環隊列public class LoopQueue<E> implements Queue<E> { private E[] data; private int front, tail; private int size;//隊列中元素個數 //構造函數，傳入隊列的容量capacity構造函數 public LoopQueue(int capacity) { data = (E[]) new Object[capacity + 1];//浪費與一個空間 front = 0; tail = 0; size = 0; } //無參構造函數，默認隊列的容量capacity=10 public LoopQueue() { this(10); } //真正容量 public int getCapacity() { return data.length - 1; } //隊列是否為空 @Override public boolean isEmpty() { return front == tail; } //隊列中元素個數 @Override public int getSize() { return size; } //入隊列操作 @Override public void enqueue(E e) { if ((tail + 1) % data.length == front) {//隊列已滿，需要擴容 resize(getCapacity() * 2); } data[tail] = e; tail = (tail + 1) % data.length; size++; } //出隊操作 @Override public E dequeue() { if (isEmpty()) { throw new IllegalArgumentException('隊列為空'); } E ret = data[front]; data[front] = null;//手動釋放 front = (front + 1) % data.length; size--; if (size == getCapacity() / 4 && getCapacity() / 2 != 0) { resize(getCapacity() / 2); } return ret; } //獲取隊首元素 @Override public E getFront() { if (isEmpty()) { throw new IllegalArgumentException('隊列為空'); } return data[front]; } //改變容量 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];//循環數組防止越界 } data = newData; front = 0; tail = size; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format('Queue:size=%d, capacity=%dn', 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(); }}

在關于LoopQueue類中需要注意的：

（1）第11行中的+1是capacity需要浪費一個空間，故在實例化是多加1

data = (E[]) new Object[capacity + 1];//浪費與一個空間

（2）地24行真正的容量是data.length-1，這是由于有一個空間是浪費的。

data.length - 1;

（3）關于入隊中第46行tail值的說明

為了保證入隊是循環操作，tail值的變化規律為

tail = (tail + 1) % data.length;

（4）關于82行的數據遷移操作，取余操作是為了防止循環數組時越界。

newData[i] = data[(front + i) % data.length];//循環數組防止越界

#3直接在LoopQueue中添加一個main函數進行測試，相關代碼如下：

//測試用例 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個元素出隊列一個queue.dequeue();System.out.println(queue); } } }

結果為：

到此我們就實現了一個循環隊列操作，解決了在順序隊列中出隊時的時間復雜度為O(n)的情況，在循環隊列中出隊的時間復雜度為O(1)。

源碼地址 https://github.com/FelixBin/dataStructure/blob/master/src/Queue/LoopQueue.java

更多關于java算法相關內容感興趣的讀者可查看本站專題：《Java數據結構與算法教程》、《Java操作DOM節點技巧總結》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對大家java程序設計有所幫助。