import java.util.NoSuchElementException;
public class LinkedQueue<T> {
private class Node{
private Node next;
private T element;
Node(Node next, T element) {
this.next = next;
this.element = element;
}
}
private int size;
private Node headPointer;//指向鏈表頭結(jié)點(diǎn)的指針跋破；
private Node tailPointer;//指向鏈表尾結(jié)點(diǎn)的指針炬灭；
public LinkedQueue() {
Node blankNode=new Node(null,null);//什么也不存儲(chǔ)的頭結(jié)點(diǎn)茬射，用于初始化鏈表唆貌，并同時(shí)被頭指針和尾指針引用宣渗。
headPointer=blankNode;
tailPointer=blankNode;
size=0;
}
public void add(T element) {
Node newNode=new Node(null,element);
tailPointer.next=newNode;
tailPointer=newNode;
size++;
}
public T remove() {
if (isEmpty()){
throw new NoSuchElementException("隊(duì)列為空级历！");
}
T answer;
Node first=headPointer.next;//headPointer引用blankNode饱搏，就是是頭結(jié)點(diǎn)，他的下一項(xiàng)才是真正的鏈表的第一個(gè)結(jié)點(diǎn)颅筋。
answer=first.element;
headPointer.next=first.next;
first.next=null;
size--;
return answer;
}
public boolean isEmpty() {
return size==0;//return headPointer==tailPointer;
}
public int size(){
return size;
}
public T peek(){
if (isEmpty()){
throw new NoSuchElementException("隊(duì)列為空宙暇！");
}
return headPointer.next.element;
}
@Override
public String toString() {
if (isEmpty()){
return "[]";
}
StringBuilder sb=new StringBuilder("[");
Node cursor=headPointer.next;//指向第一個(gè)有意義的結(jié)點(diǎn)。
for (int i=0;i<size;i++){
sb.append(cursor.element.toString());
if (i!=size-1){
sb.append(",");
}
cursor=cursor.next;
}
sb.append("]");
return sb.toString();
}
}
public class Main {
public static void main(String[] args) throws Throwable {
LinkedQueue<String> q=new LinkedQueue<>();
q.add("1");
q.add("2");
q.add("3");
System.out.println(q);//[1,2,3]
q.remove();
q.remove();
System.out.println(q);//[3]
q.add("4");
q.add("5");
q.add("6");
q.add("7");
System.out.println(q);//[3,4,5,6,7]
}
分解著一個(gè)一個(gè)方法來(lái)看如何用鏈表實(shí)現(xiàn)隊(duì)列：
1. 構(gòu)造方法
//構(gòu)造函數(shù)初始化鏈表
//將全局變量指向一個(gè)blankNode頭結(jié)點(diǎn)议泵，這個(gè)頭結(jié)點(diǎn)什么也不做占贫，只是用來(lái)標(biāo)記這是鏈表的開(kāi)頭。
//方便操作
public LinkedQueue() {
Node blankNode=new Node(null,null);//什么也不存儲(chǔ)的頭結(jié)點(diǎn)先口，用于初始化鏈表型奥，并同時(shí)被頭指針和尾指針引用瞳收。
headPointer=blankNode;
tailPointer=blankNode;
size=0;
}
2. add
public void add(T element) {
Node newNode=new Node(null,element);//行1
tailPointer.next=newNode;//行2
tailPointer=newNode;//行3
size++;
}
//下面用圖描述每行代碼做了什么
-
行1：
-
行2：
-
行3：
那么當(dāng)調(diào)用了需多次add方法之后，就應(yīng)該是這個(gè)樣子：
image.png
3. remove
public T remove() {
if (isEmpty()){
throw new NoSuchElementException("隊(duì)列為空厢汹！");
}
T answer;
Node first=headPointer.next;//headPointer引用blankNode螟深，就是是頭結(jié)點(diǎn)，他的下一項(xiàng)才是真正的鏈表的第一個(gè)結(jié)點(diǎn)烫葬。
answer=first.element;
headPointer.next=first.next;//行1
first.next=null;//行2
size--;
return answer;
}
出隊(duì)的操作界弧，直接看圖
-
行1：
-
行2：
