本文實(shí)例講述了Java數(shù)組隊(duì)列概念與用法。分享給大家供大家參考，具體如下：

（1）隊(duì)列也是一種線性結(jié)構(gòu)

（2）相比數(shù)組，隊(duì)列對(duì)應(yīng)的操作是數(shù)組的子集

（3）只允許在一端插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作，進(jìn)行插入操作的一端稱為隊(duì)尾（入隊(duì)列），進(jìn)行刪除操作的一端稱為隊(duì)頭（出隊(duì)列）

（4）隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)（FIFO）

此處我們先來學(xué)習(xí)一下順序隊(duì)列 ，順序隊(duì)列 就是用數(shù)組實(shí)現(xiàn)：比如有一個(gè)ｎ個(gè)元素的隊(duì)列，數(shù)組下標(biāo)0的一端是隊(duì)頭，入隊(duì)操作就是通過數(shù)組下標(biāo)一個(gè)個(gè)順序追加，不需要移動(dòng)元素，但是如果刪除隊(duì)頭元素，后面的元素就要往前移動(dòng)，對(duì)應(yīng)的時(shí)間復(fù)雜度就是O(n)。

對(duì)于隊(duì)列，我們關(guān)注的相關(guān)實(shí)現(xiàn)如下：

對(duì)于該節(jié)的相關(guān)代碼，我們新建一個(gè)package（Queue）,同時(shí)為了理解方便，此時(shí)把動(dòng)態(tài)數(shù)組相關(guān)代碼拷貝到該包中。

1.先創(chuàng)建一個(gè)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.創(chuàng)建一個(gè)類ArrayQueue實(shí)現(xiàn)Queue接口并重寫Object類的toString()方法

package Queue;public class ArrayQueue<E> implements Queue<E> { private DynamicArray<E> array; //構(gòu)造函數(shù)，傳入隊(duì)列的容量capacity構(gòu)造函數(shù) public ArrayQueue(int capacity) { array = new DynamicArray<E>(capacity); } //無參構(gòu)造函數(shù)，默認(rèn)隊(duì)列的容量capacity=10 public ArrayQueue() { array = new DynamicArray<E>(); } //獲取隊(duì)列中元素?cái)?shù)據(jù)是否為空 @Override public boolean isEmpty() { return array.isEmpty(); } //獲取隊(duì)列中元素個(gè)數(shù) @Override public int getSize() { return array.getSize(); } //獲取隊(duì)列的容量 public int getCapacity() { return array.getCapacity(); } //入隊(duì)操作 @Override public void enqueue(E e) { array.addLast(e); } //出隊(duì)操作 @Override public E dequeue() { return array.removeFirst(); } //獲取隊(duì)首元素 @Override public E getFront() { return array.getFirst(); } //重寫object類的toString方法 @Override public String toString() { StringBuilder res = new StringBuilder(); res.append('Queue:'); res.append('front [');//體現(xiàn)左側(cè)為隊(duì)首 for (int i = 0; i < array.getSize(); i++) { res.append(array.get(i)); if (i != array.getSize() - 1) {res.append(','); } } res.append('] tail');//體現(xiàn)右側(cè)為隊(duì)尾 return res.toString(); }}

3.測試

新建一個(gè)TestMain類，添加一個(gè)main函數(shù)來測試我們編寫好的ArrayQueue類

相關(guān)代碼如下：

package Queue;public class TestMain { public static void main(String[] args) { ArrayQueue<Integer> queue = new ArrayQueue<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); } } }}

對(duì)于第7行代碼是測試入隊(duì)列操作的，第10、11行代碼的意思是每添加3個(gè)元素出隊(duì)列一個(gè)元素。結(jié)果為：

對(duì)于出隊(duì)的時(shí)間復(fù)雜度為O(n)的解釋：

由于實(shí)現(xiàn)數(shù)組隊(duì)列的底層是動(dòng)態(tài)數(shù)組，入隊(duì)操作就是通過數(shù)組下標(biāo)一個(gè)個(gè)順序追加，不需要移動(dòng)元素，但是如果刪除隊(duì)頭元素（removeFirst()方法），后面的元素就要往前移動(dòng)，對(duì)應(yīng)的時(shí)間復(fù)雜度就是O(n)。這樣當(dāng)有數(shù)組中有大量數(shù)據(jù)時(shí)性能肯定是不好的，下一節(jié)我們將進(jìn)行改進(jìn)，使得出隊(duì)的時(shí)間復(fù)雜度為O(1)。

源碼地址 https://github.com/FelixBin/dataStructure/tree/master/src/Queue

更多關(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ì)有所幫助。