什么是隊列結構
一種線性結構，具有特殊的運算法則【只能在一端（隊頭）刪除，在另一端（隊尾）插入】。
分類：
順序隊列結構
鏈式隊列結構
基本操作：
入隊列
出隊列
給出一些應用隊列的場景
1):當作業被送到打印機的時候，就可以按到達的順序排起來，因此每一份作業是隊列的節點。
2):售票口的人買票的順序的按照先來先買的順序售票。
3):當所有的終端被占用，由于資源有限，來訪請求需要放在一個隊列中等候。
隊列是先進先出的!
我們設置一個叫做LinkQueue<T>的泛型集合類，該類里面有 Node 作為內部類（作為節點用），它包含了泛型元素和下一個node節點的指向next（Node）。
在Linkqueue的里面設置隊列頭指針 front和隊列尾指針rear，長度size=0；我們先設置一個構造器LinkQueue()，用來初始化這兩個指針節點，當然，剛開始初始化的時候 這兩個指針僅僅是一個節點而已，里面的data是空的，我們還讓這兩個指針相等。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
//鏈的數據結構 private class Node{ public T data; public Node next; //無參構造函數 public Node(){} public Node(T data,Node next){ this.data=data; this.next=next; } } //隊列頭指針 private Node front; //隊列尾指針 private Node rear; |
|
1
2
3
4
5
|
public LinkQueue(){ Node n=new Node(null,null); n.next=null; front=rear=n;} |
當我們向該隊列添加元素的時候，就會生成一個新的節點，其data就是你要加的元素，（當添加一個節點時，該節點就是隊尾指針指向的最后的節點，一直排在最后），所以隊尾rear.next=newNode(“新創建的節點”).這是第一個節點，也是最后一個節點，所以front.next=newNode.然后我們再讓rear=newNode（不斷更新）。
|
1
2
3
4
5
6
7
8
|
public void enqueue(T data){ //創建一個節點 Node s=new Node(data,null); //將隊尾指針指向新加入的節點，將s節點插入隊尾 rear.next=s; rear=s; size++; } |
當隊列出隊的時候，還記得我們有一個Node是front.next=newNode 嗎？這就是第一個節點。先暫且把它叫做p，所以p.next=第二個節點，這時我們再把front.next=p.next;這樣頭指針就指向了第二個元素(每一次調用的時候隊列頭指針指會發生變化)。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public T dequeue(){ if(rear==front){ try { throw new Exception("堆棧為空"); } catch (Exception e) { e.printStackTrace(); } return null; }else{ //暫存隊頭元素 Node p=front.next; T x=p.data; //將隊頭元素所在節點摘鏈 front.next=p.next; //判斷出隊列長度是否為1 if(p.next==null) rear=front; //刪除節點 p=null; size--; return x; } } |
到此為止，隊列的核心操作就完畢了，剩下的比如說size(長度)，isEmpty(是否為空)，就不在說了。(因為太簡單了！)
具體源碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
public class LinkQueue<T> { //鏈的數據結構 private class Node{ public T data; public Node next; //無參構造函數 public Node(){ } public Node(T data,Node next){ this.data=data; this.next=next; } } //隊列頭指針 private Node front; //隊列尾指針 private Node rear; //隊列長度 private int size=0; public LinkQueue(){ Node n=new Node(null,null); n.next=null; front=rear=n; } /** * 隊列入隊算法 * @param data * @author WWX */ public void enqueue(T data){ //創建一個節點 Node s=new Node(data,null); //將隊尾指針指向新加入的節點，將s節點插入隊尾 rear.next=s; rear=s; size++; } /** * 隊列出隊算法 * @return * @author WWX */ public T dequeue(){ if(rear==front){ try { throw new Exception("堆棧為空"); } catch (Exception e) { e.printStackTrace(); } return null; } else{ //暫存隊頭元素 Node p=front.next; T x=p.data; //將隊頭元素所在節點摘鏈 front.next=p.next; //判斷出隊列長度是否為1 if(p.next==null) rear=front; //刪除節點 p=null; size--; return x; } } /** * 隊列長隊 * @return * @author WWX */ public int size(){ return size; } /** * 判斷隊列是否為空 * @return * @author WWX */ public Boolean isEmpty(){ return size==0; }} |
另：我曾經看過一本JavaScript數據結構書，里面講的淺顯易懂，很適合前端搞js開發的讓人理解的更為深入，在此給予推薦。如有不足之處，歡迎留言指出。
原文鏈接：https://www.cnblogs.com/coversky/p/6350086.html
