本文實例講述了java基于鏈表實現(xiàn)隊列。分享給大家供大家參考，具體如下：
創(chuàng)新互聯(lián)建站是一家專注于成都做網(wǎng)站、成都網(wǎng)站設(shè)計與策劃設(shè)計,達茂旗網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)建站做網(wǎng)站,專注于網(wǎng)站建設(shè)10多年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:達茂旗等地區(qū)。達茂旗做網(wǎng)站價格咨詢:028-86922220
在開始棧的實現(xiàn)之前，我們再來看看關(guān)于鏈表的只在頭部進行的增加、刪除、查找操作，時間復雜度均為O(1)。
對于隊列這種數(shù)據(jù)結(jié)構(gòu)，需要在線性結(jié)構(gòu)的一端插入元素，另外一端刪除元素。因此此時基于鏈表來實現(xiàn)隊列，則有一端的時間復雜度為O(n)。因此我們不能使用之前已經(jīng)實現(xiàn)的鏈表結(jié)構(gòu)，我們需要改進我們的鏈表。思路如下：
1.參考在鏈表頭部刪除、增加元素的時間復雜度為O(1)的思路，我們在鏈表的尾部設(shè)立一個Node型的變量tail來記錄鏈表的尾部在哪，此時再head端和tail端添加元素都是及其簡單的，在head端刪除元素也是及其簡單的，但對于在tail端刪除元素時，是無法在時間復雜度為O(1)的情況進行的，也就是從tail端刪除元素時不容易的。
2.只在頭部head刪除元素（隊首），在尾部tail端添加元素（隊尾）。
3.由于在基于鏈表實現(xiàn)隊列時不涉及到操作鏈表中間元素，此時我們改進的鏈表中，不在使用虛擬頭節(jié)，因此也就可能造成在沒有虛擬頭節(jié)點的情況下，鏈表為空。
前言，在寫本小節(jié)之前，我們已經(jīng)實現(xiàn)了一個基于靜態(tài)數(shù)組的隊列，轉(zhuǎn)到查看。此處我們實現(xiàn)基于鏈表的隊列。
在實現(xiàn)基于靜態(tài)數(shù)組的隊列的時候，我們已經(jīng)新建了一個package，此時我們在該package下新建一個LinkedListQueue類，用來實現(xiàn)Queue接口，目錄結(jié)構(gòu)為：
1.Queue接口代碼
package Queue; public interface Queue{ //獲取隊列中元素個數(shù) int getSize(); //隊列中元素是否為空 boolean isEmpty(); //入隊列 void enqueue(E e); //出隊列 public E dequeue(); //獲取隊首元素 public E getFront(); }
2.LinkedListQueue類
package Queue; public class LinkedListQueueimplements Queue { //將Node節(jié)點設(shè)計成私有的類中類 private class Node { public E e; public Node next; //兩個參數(shù)的構(gòu)造函數(shù) public Node(E e, Node next) { this.e = e; this.next = next; } //一個參數(shù)的構(gòu)造函數(shù) public Node(E e) { this.e = e; this.next = null; } //無參構(gòu)造函數(shù) public Node() { this(null, null); } @Override public String toString() { return e.toString(); } } private Node head, tail; private int size; //顯示初始化 public LinkedListQueue() { head = null; tail = null; size = 0; } //獲取隊列中節(jié)點個數(shù) @Override public int getSize() { return size; } //隊列中是否為空 @Override public boolean isEmpty() { return size == 0; } //鏈表尾部進隊操作 @Override public void enqueue(E e) { if (tail == null) { tail = new Node(e); head = tail; } else { tail.next = new Node(e); tail = tail.next; } size++; } //鏈表頭部出隊操作 @Override public E dequeue() { if (isEmpty()) { throw new IllegalArgumentException("鏈表為空"); } Node retNode = head; head = head.next; retNode.next = null; if (head == null) {//當鏈表只有一個元素時 tail = null; } size--; return retNode.e; } //獲取隊首元素 @Override public E getFront() { if (isEmpty()) { throw new IllegalArgumentException("鏈表為空"); } return head.e; } //為了便于測試，重寫object類toString()方法 @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Queue: front "); Node cur = head; while (cur != null) { res.append(cur + "->"); cur = cur.next; } res.append("NULL tail"); return res.toString(); } }
3.為了便于測試，在LinkedListQueue類中添加一個main函數(shù)
重慶分公司
重慶分公司
//測試用例
public static void main(String[] args) {
LinkedListQueue queue = new LinkedListQueue();
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);
}
}
} 4.結(jié)果為
結(jié)果分析：每進隊3個元素出隊列一個。
關(guān)于本小節(jié)，若您覺得還行、還過得去，記得給個推薦哦~，謝謝??！
本節(jié)源碼 https://github.com/FelixBin/dataStructure/blob/master/src/Queue/LinkedListQueue.java
更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設(shè)計有所幫助。
