溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了java基于鏈表實現隊列。分享給大家供大家參考，具體如下：
在開始棧的實現之前，我們再來看看關于鏈表的只在頭部進行的增加、刪除、查找操作，時間復雜度均為O(1)。
對于隊列這種數據結構，需要在線性結構的一端插入元素，另外一端刪除元素。因此此時基于鏈表來實現隊列，則有一端的時間復雜度為O(n)。因此我們不能使用之前已經實現的鏈表結構，我們需要改進我們的鏈表。思路如下：
1.參考在鏈表頭部刪除、增加元素的時間復雜度為O(1)的思路，我們在鏈表的尾部設立一個Node型的變量tail來記錄鏈表的尾部在哪，此時再head端和tail端添加元素都是及其簡單的，在head端刪除元素也是及其簡單的，但對于在tail端刪除元素時，是無法在時間復雜度為O(1)的情況進行的，也就是從tail端刪除元素時不容易的。
2.只在頭部head刪除元素（隊首），在尾部tail端添加元素（隊尾）。
3.由于在基于鏈表實現隊列時不涉及到操作鏈表中間元素，此時我們改進的鏈表中，不在使用虛擬頭節，因此也就可能造成在沒有虛擬頭節點的情況下，鏈表為空。
前言，在寫本小節之前，我們已經實現了一個基于靜態數組的隊列，轉到查看。此處我們實現基于鏈表的隊列。
在實現基于靜態數組的隊列的時候，我們已經新建了一個package，此時我們在該package下新建一個LinkedListQueue類，用來實現Queue接口，目錄結構為：
1.Queue接口代碼
package Queue;
public interface Queue<E> {
//獲取隊列中元素個數
int getSize();
//隊列中元素是否為空
boolean isEmpty();
//入隊列
void enqueue(E e);
//出隊列
public E dequeue();
//獲取隊首元素
public E getFront();
}
2.LinkedListQueue類
package Queue;
public class LinkedListQueue<E> implements Queue<E> {
//將Node節點設計成私有的類中類
private class Node<E> {
public E e;
public Node next;
//兩個參數的構造函數
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
//一個參數的構造函數
public Node(E e) {
this.e = e;
this.next = null;
}
//無參構造函數
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;
}
//獲取隊列中節點個數
@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<E> 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<E> cur = head;
while (cur != null) {
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL tail");
return res.toString();
}
}
3.為了便于測試，在LinkedListQueue類中添加一個main函數
//測試用例
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個元素出隊列一個
queue.dequeue();
System.out.println(queue);
}
}
}
4.結果為
結果分析：每進隊3個元素出隊列一個。
關于本小節，若您覺得還行、還過得去，記得給個推薦哦~，謝謝！！
本節源碼 https://github.com/FelixBin/dataStructure/blob/master/src/Queue/LinkedListQueue.java
更多關于java算法相關內容感興趣的讀者可查看本站專題：《Java數據結構與算法教程》、《Java操作DOM節點技巧總結》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
