使用鏈表實作佇列和之前文章使用鏈表實作堆疊的原理基本上類似，唯一不同的是把后進先出改為了先進先出
有一點不同的是相較于堆疊只需要一個first變數來保存頭節點，佇列還需要一個last變數保存尾節點，每次enqueue都在尾節點添加一個新的元素，dequeue洗掉頭節點元素
public void enqueue(Item item) {
Node oldLast = last;
last = new Node();
last.item = item;
n++;
if (n == 1) {
first = last;
} else {
oldLast.next = last;
}
}
在enqueue代碼中，注意如果此時加入的為當前佇列第一個元素，需要將其設為first和last，否則記錄之前的last，把last設為新加入元素，然后把之前的last的next設為新的last.
public Item dequeue() {
Item element = first.item;
first = first.next;
n--;
return element;
}
dequeue方法和堆疊里面的pop方法基本上一致
完整代碼及測驗資料：
import java.util.Iterator;
public class LinkedListQueue<Item> implements Iterable<Item> {
private class Node {
Item item;
Node next;
}
private int n = 0; //the length of queue
private Node first;
private Node last;
public boolean isEmpty() {
return n == 0;
}
public int size() {
return n;
}
public void enqueue(Item item) {
Node oldLast = last;
last = new Node();
last.item = item;
n++;
if (n == 1) {
first = last;
} else {
oldLast.next = last;
}
}
public Item dequeue() {
Item element = first.item;
first = first.next;
n--;
return element;
}
public Iterator<Item> iterator() {
return new ReverseLinkedListIterator();
}
private class ReverseLinkedListIterator implements Iterator<Item> {
int i = 0;
Node current = first;
public boolean hasNext() {
return i > 0;
}
public Item next() {
Item element = current.item;
if (current.next != null) {
current = current.next;
}
return element;
}
public void remove() {
// Left blank on purpose
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedListQueue<Integer> test = new LinkedListQueue<Integer>();
test.enqueue(1);
test.enqueue(2);
test.enqueue(3);
test.enqueue(4);
test.enqueue(5);
test.dequeue();
test.dequeue();
test.dequeue();
System.out.println(test.dequeue());
}
}
備注：
對于實作Iterator的解釋，查看文章《演算法學習筆記：自建集合資料型別（1）使用陣列實作下壓堆疊》
https://blog.csdn.net/Raine_Yang/article/details/119923848
對于鏈表的解釋，查看文章《演算法學習筆記：自建集合資料型別（2）使用鏈表實作下壓堆疊》
https://blog.csdn.net/Raine_Yang/article/details/119945560
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296766.html
標籤：其他
上一篇：二叉樹展開為鏈表 C語言
下一篇：windows64位搭建匯編（包含匯編dosbox , masm檔案，link檔案和debug除錯）以及debug除錯命令（dosbox除錯匯編程式的簡單使用教程）