重慶分公司
重慶分公司，新征程啟航
為企業(yè)提供網(wǎng)站建設(shè)、域名注冊、服務(wù)器等服務(wù)
java鏈表應(yīng)用--基于鏈表實(shí)現(xiàn)隊(duì)列詳解（尾指針操作）
本文實(shí)例講述了java基于鏈表實(shí)現(xiàn)隊(duì)列。分享給大家供大家參考，具體如下：
創(chuàng)新互聯(lián)建站是一家專注于成都做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)與策劃設(shè)計(jì),達(dá)茂旗網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)建站做網(wǎng)站,專注于網(wǎng)站建設(shè)10多年,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:達(dá)茂旗等地區(qū)。達(dá)茂旗做網(wǎng)站價格咨詢:028-86922220
在開始棧的實(shí)現(xiàn)之前，我們再來看看關(guān)于鏈表的只在頭部進(jìn)行的增加、刪除、查找操作，時間復(fù)雜度均為O(1)。
一、鏈表改進(jìn)分析
對于隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，需要在線性結(jié)構(gòu)的一端插入元素，另外一端刪除元素。因此此時基于鏈表來實(shí)現(xiàn)隊(duì)列，則有一端的時間復(fù)雜度為O(n)。因此我們不能使用之前已經(jīng)實(shí)現(xiàn)的鏈表結(jié)構(gòu)，我們需要改進(jìn)我們的鏈表。思路如下：
1.參考在鏈表頭部刪除、增加元素的時間復(fù)雜度為O(1)的思路，我們在鏈表的尾部設(shè)立一個Node型的變量tail來記錄鏈表的尾部在哪，此時再head端和tail端添加元素都是及其簡單的，在head端刪除元素也是及其簡單的，但對于在tail端刪除元素時，是無法在時間復(fù)雜度為O(1)的情況進(jìn)行的，也就是從tail端刪除元素時不容易的。
2.只在頭部head刪除元素（隊(duì)首），在尾部tail端添加元素（隊(duì)尾）。
3.由于在基于鏈表實(shí)現(xiàn)隊(duì)列時不涉及到操作鏈表中間元素，此時我們改進(jìn)的鏈表中，不在使用虛擬頭節(jié)，因此也就可能造成在沒有虛擬頭節(jié)點(diǎn)的情況下，鏈表為空。
二、鏈表改進(jìn)代碼
前言，在寫本小節(jié)之前，我們已經(jīng)實(shí)現(xiàn)了一個基于靜態(tài)數(shù)組的隊(duì)列，轉(zhuǎn)到查看。此處我們實(shí)現(xiàn)基于鏈表的隊(duì)列。
在實(shí)現(xiàn)基于靜態(tài)數(shù)組的隊(duì)列的時候，我們已經(jīng)新建了一個package，此時我們在該package下新建一個LinkedListQueue類，用來實(shí)現(xiàn)Queue接口，目錄結(jié)構(gòu)為：
1.Queue接口代碼
package Queue; public interface Queue{ //獲取隊(duì)列中元素個數(shù) int getSize(); //隊(duì)列中元素是否為空 boolean isEmpty(); //入隊(duì)列 void enqueue(E e); //出隊(duì)列 public E dequeue(); //獲取隊(duì)首元素 public E getFront(); }
2.LinkedListQueue類
package Queue; public class LinkedListQueueimplements Queue { //將Node節(jié)點(diǎn)設(shè)計(jì)成私有的類中類 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; } //獲取隊(duì)列中節(jié)點(diǎn)個數(shù) @Override public int getSize() { return size; } //隊(duì)列中是否為空 @Override public boolean isEmpty() { return size == 0; } //鏈表尾部進(jìn)隊(duì)操作 @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++; } //鏈表頭部出隊(duì)操作 @Override public E dequeue() { if (isEmpty()) { throw new IllegalArgumentException("鏈表為空"); } Node retNode = head; head = head.next; retNode.next = null; if (head == null) {//當(dāng)鏈表只有一個元素時 tail = null; } size--; return retNode.e; } //獲取隊(duì)首元素 @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個元素出隊(duì)列一個
queue.dequeue();
System.out.println(queue);
}
}
} 4.結(jié)果為
結(jié)果分析：每進(jìn)隊(duì)3個元素出隊(duì)列一個。
關(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é)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設(shè)計(jì)有所幫助。
文章標(biāo)題：java鏈表應(yīng)用--基于鏈表實(shí)現(xiàn)隊(duì)列詳解（尾指針操作）
地址分享：http://www.xueling.net.cn/article/psdeps.html