本文實(shí)例講述了java基于鏈表實(shí)現(xiàn)隊(duì)列。分享給大家供大家參考，具體如下：

在開(kāi)始棧的實(shí)現(xiàn)之前，我們?cè)賮?lái)看看關(guān)于鏈表的只在頭部進(jìn)行的增加、刪除、查找操作，時(shí)間復(fù)雜度均為O(1)。

對(duì)于隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，需要在線性結(jié)構(gòu)的一端插入元素，另外一端刪除元素。因此此時(shí)基于鏈表來(lái)實(shí)現(xiàn)隊(duì)列，則有一端的時(shí)間復(fù)雜度為O(n)。因此我們不能使用之前已經(jīng)實(shí)現(xiàn)的鏈表結(jié)構(gòu)，我們需要改進(jìn)我們的鏈表。思路如下：

1.參考在鏈表頭部刪除、增加元素的時(shí)間復(fù)雜度為O(1)的思路，我們?cè)阪湵淼奈膊吭O(shè)立一個(gè)Node型的變量tail來(lái)記錄鏈表的尾部在哪，此時(shí)再head端和tail端添加元素都是及其簡(jiǎn)單的，在head端刪除元素也是及其簡(jiǎn)單的，但對(duì)于在tail端刪除元素時(shí)，是無(wú)法在時(shí)間復(fù)雜度為O(1)的情況進(jìn)行的，也就是從tail端刪除元素時(shí)不容易的。

2.只在頭部head刪除元素（隊(duì)首），在尾部tail端添加元素（隊(duì)尾）。

3.由于在基于鏈表實(shí)現(xiàn)隊(duì)列時(shí)不涉及到操作鏈表中間元素，此時(shí)我們改進(jìn)的鏈表中，不在使用虛擬頭節(jié)，因此也就可能造成在沒(méi)有虛擬頭節(jié)點(diǎn)的情況下，鏈表為空。

前言，在寫(xiě)本小節(jié)之前，我們已經(jīng)實(shí)現(xiàn)了一個(gè)基于靜態(tài)數(shù)組的隊(duì)列，轉(zhuǎn)到查看。此處我們實(shí)現(xiàn)基于鏈表的隊(duì)列。

在實(shí)現(xiàn)基于靜態(tài)數(shù)組的隊(duì)列的時(shí)候，我們已經(jīng)新建了一個(gè)package，此時(shí)我們?cè)谠損ackage下新建一個(gè)LinkedListQueue類，用來(lái)實(shí)現(xiàn)Queue接口，目錄結(jié)構(gòu)為：

1.Queue接口代碼

package Queue;public interface Queue<E> { //獲取隊(duì)列中元素個(gè)數(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 LinkedListQueue<E> implements Queue<E> { //將Node節(jié)點(diǎn)設(shè)計(jì)成私有的類中類 private class Node<E> { public E e; public Node next; //兩個(gè)參數(shù)的構(gòu)造函數(shù) public Node(E e, Node next) { this.e = e; this.next = next; } //一個(gè)參數(shù)的構(gòu)造函數(shù) public Node(E e) { this.e = e; this.next = null; } //無(wú)參構(gòu)造函數(shù) public Node() { this(null, null); } @Override public String toString() { return e.toString(); } } private Node<E> head, tail; private int size; //顯示初始化 public LinkedListQueue() { head = null; tail = null; size = 0; } //獲取隊(duì)列中節(jié)點(diǎn)個(gè)數(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<E> retNode = head; head = head.next; retNode.next = null; if (head == null) {//當(dāng)鏈表只有一個(gè)元素時(shí) tail = null; } size--; return retNode.e; } //獲取隊(duì)首元素 @Override public E getFront() { if (isEmpty()) { throw new IllegalArgumentException('鏈表為空'); } return head.e; } //為了便于測(cè)試，重寫(xiě)object類toString()方法 @Override public String toString() { StringBuilder res = new StringBuilder(); res.append('Queue: front '); Node<E> cur = head; while (cur != null) { res.append(cur + '->'); cur = cur.next; } res.append('NULL tail'); return res.toString(); }}

3.為了便于測(cè)試，在LinkedListQueue類中添加一個(gè)main函數(shù)

//測(cè)試用例 public static void main(String[] args) { LinkedListQueue<Integer> queue = new LinkedListQueue<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); } } }

4.結(jié)果為

結(jié)果分析：每進(jìn)隊(duì)3個(gè)元素出隊(duì)列一個(gè)。

關(guān)于本小節(jié)，若您覺(jué)得還行、還過(guò)得去，記得給個(gè)推薦哦~，謝謝?。?/p>

本節(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緩存操作技巧匯總》

希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。