您好,登錄后才能下訂單哦!
本文實例講述了Java數(shù)組隊列概念與用法。分享給大家供大家參考,具體如下:
(1)隊列也是一種線性結(jié)構(gòu)
(2)相比數(shù)組,隊列對應(yīng)的操作是數(shù)組的子集
(3)只允許在一端插入數(shù)據(jù)操作,在另一端進(jìn)行刪除數(shù)據(jù)操作,進(jìn)行插入操作的一端稱為隊尾(入隊列),進(jìn)行刪除操作的一端稱為隊頭(出隊列)
(4)隊列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)(FIFO)
此處我們先來學(xué)習(xí)一下順序隊列 ,順序隊列 就是用數(shù)組實現(xiàn):比如有一個n個元素的隊列,數(shù)組下標(biāo)0的一端是隊頭,入隊操作就是通過數(shù)組下標(biāo)一個個順序追加,不需要移動元素,但是如果刪除隊頭元素,后面的元素就要往前移動,對應(yīng)的時間復(fù)雜度就是O(n)。
對于隊列,我們關(guān)注的相關(guān)實現(xiàn)如下:
對于該節(jié)的相關(guān)代碼,我們新建一個package(Queue),同時為了理解方便,此時把動態(tài)數(shù)組相關(guān)代碼拷貝到該包中。
1.先創(chuàng)建一個Queue接口,里面定義上面所述的方法
package Queue; public interface Queue<E> { //獲取隊列中元素個數(shù) int getSize(); //隊列中元素是否為空 boolean isEmpty(); //入隊列 void enqueue(E e); //出隊列 E dequeue(); //獲取隊首元素 E getFront(); }
2.創(chuàng)建一個類ArrayQueue實現(xiàn)Queue接口并重寫Object類的toString()方法
package Queue; public class ArrayQueue<E> implements Queue<E> { private DynamicArray<E> array; //構(gòu)造函數(shù),傳入隊列的容量capacity構(gòu)造函數(shù) public ArrayQueue(int capacity) { array = new DynamicArray<E>(capacity); } //無參構(gòu)造函數(shù),默認(rèn)隊列的容量capacity=10 public ArrayQueue() { array = new DynamicArray<E>(); } //獲取隊列中元素數(shù)據(jù)是否為空 @Override public boolean isEmpty() { return array.isEmpty(); } //獲取隊列中元素個數(shù) @Override public int getSize() { return array.getSize(); } //獲取隊列的容量 public int getCapacity() { return array.getCapacity(); } //入隊操作 @Override public void enqueue(E e) { array.addLast(e); } //出隊操作 @Override public E dequeue() { return array.removeFirst(); } //獲取隊首元素 @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è)為隊首 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è)為隊尾 return res.toString(); } }
3.測試
新建一個TestMain類,添加一個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個元素出隊列一個 queue.dequeue(); System.out.println(queue); } } } }
對于第7行代碼是測試入隊列操作的,第10、11行代碼的意思是每添加3個元素出隊列一個元素。結(jié)果為:
對于出隊的時間復(fù)雜度為O(n)的解釋:
由于實現(xiàn)數(shù)組隊列的底層是動態(tài)數(shù)組,入隊操作就是通過數(shù)組下標(biāo)一個個順序追加,不需要移動元素,但是如果刪除隊頭元素(removeFirst()方法),后面的元素就要往前移動,對應(yīng)的時間復(fù)雜度就是O(n)。這樣當(dāng)有數(shù)組中有大量數(shù)據(jù)時性能肯定是不好的,下一節(jié)我們將進(jìn)行改進(jìn),使得出隊的時間復(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緩存操作技巧匯總》
希望本文所述對大家java程序設(shè)計有所幫助。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。