溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章給大家介紹如何理解隊列及java實現，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。
棧和隊列是有操作限制的線性表。
隊列是一種在一端進行插入，而在另一端進行刪除的線性表。
1、隊列的插入端稱為隊尾；隊列的刪除端稱為隊頭。（好比火車進隧道）
2、隊列的插入操作稱為入隊（push），刪除操作稱為出隊（pop）。
隊列就像一列進入隧道的火車，隧道就是隊列，火車車廂就是元素，進入隧道就是從隧道的這頭（隊尾）插入元素，出隧道就是從隧道的另一頭（隊頭）刪除元素。所以是“先進先出”的特點。
類似棧有順序隊和鏈式隊兩種。
我們可以圍繞棧的4個元素來實現隊列：
2狀態：是否隊空；是否隊滿。
2操作：進隊push;出隊pop。
順序隊列的實現也可以使用數組來完成，同棧的實現一樣，只是棧是在同一端進行壓棧和進棧操作，而隊列是在一端做push，另一端做pop操作。
可以看一下下面的隊列操作示意圖：
我們在實現順序棧時使用頭指針“front”和尾指針“rear”分別進行出隊和入隊操作，但普通的隊列如上圖所示，會發生“假溢出”現象，所以我們通常將數組弄成一個環狀，即隊頭和隊尾相連，這樣就形成了“循環隊列”，同時也解決了“假溢出”現象。循環隊列是改進版的順序隊列。
如圖：
對于普通隊列的push或pop我們只需要對尾指針或頭指針進行自增操作即可，但是循環隊列我們就不能單純的進行自增，當front或rear=maxSize-1時我們就不能進行自增操作了，比如一個隊列尾長度為4的數組datas[4]，那么當front或rear需要在0,1,2,3之間進行循環“推進”，以此達到循環隊列的效果。所以我們可以使用rear = （rear+1）%maxSize ；front = （front+1）%maxSize ；公式進行指針計算。
需要注意的是：隊空狀態的條件為：front = rear。而如果整個隊列全部存滿數據那么，隊滿的條件也是front = rear；所以循環隊列需要損失一個存儲空間，如下圖：
解決了這些問題我們就可以很輕松地實現循環隊列了：
1 package test;
2
3 public class SqQueue<T>{
4 private T[] datas;//使用數組作為隊列的容器
5 private int maxSize;//隊列的容量
6 private int front;//頭指針
7 private int rear;//尾指針
8
9 //初始化隊列
10 public SqQueue(int maxSize){
11 if(maxSize<1){
12 maxSize = 1;
13 }
14 this.maxSize = maxSize;
15 this.front = 0;
16 this.rear = 0;
17 this.datas = (T[])new Object[this.maxSize];
18 }
19
20 //兩個狀態:隊空&隊滿
21 public boolean isNull(){
22 if(this.front == this.rear)
23 return true;
24 else
25 return false;
26 }
27
28 public boolean isFull(){
29 if((rear+1)%this.maxSize==front)
30 return true;
31 else
32 return false;
33 }
34
35 //初始化隊列
36 public void initQueue(){
37 this.front = 0;
38 this.front = 0;
39 }
40
41 //兩個操作:進隊&出隊
42 public boolean push(T data){
43 if(isFull())
44 return false;//隊滿則無法進隊
45 else{
46 datas[rear] = data;//進隊
47 rear = (rear+1) % maxSize;//隊尾指針+1.
48 return true;
49 }
50 }
51 public T pop(){
52 if(isNull())
53 return null;//對空無法出隊
54 else{
55 T popData = datas[front++];//出隊
56 front = (front+1) % maxSize;//隊頭指針+1
57 return popData;
58 }
59 }
60
61 //get()
62 public T[] getDatas() {
63 return datas;
64 }
65
66 public int getMaxSize() {
67 return maxSize;
68 }
69
70 public int getFront() {
71 return front;
72 }
73
74 public int getRear() {
75 return rear;
76 }
77 }測試：
1 package test;
2
3 import org.junit.Test;
4
5 public class testQueue {
6
7 @Test
8 public void fun(){
9 SqQueue<Character> queue = new SqQueue<Character>(4);
10
11 //判斷
12 System.out.println("隊列是否為空："+queue.isNull());
13
14 //入隊A,B,C
15 queue.push('A');
16 queue.push('B');
17 queue.push('C');
18
19 System.out.println("隊列是否為滿："+queue.isFull());
20
21 //出隊
22 Character data = queue.pop();
23 System.out.println("出隊："+data);
24 }
25 } 
如圖所示：
鏈隊的實現很簡單，只要理解了鏈表的操作和隊列的特點即可。
1 package test;
2
3 public class LinkQueue<T>{
4 private QNode<T> front;//隊頭指針
5 private QNode<T> rear;//隊尾指針
6 private int maxSize;//為了便于操作，使用這個變量表示鏈隊的數據容量
7
8 //初始化
9 public LinkQueue(){
10 this.front = new QNode<T>();
11 this.rear = new QNode<T>();
12 this.maxSize = 0;
13 }
14
15 //初始化隊列
16 public void initQueue(){
17 front.next = null;
18 rear.next = null;
19 maxSize = 0;
20 }
21
22 //隊空判斷
23 public boolean isNull(){
24 if(front.next==null || rear.next==null)
25 return true;
26 else
27 return false;
28 }
29
30 //進隊
31 public void push(QNode<T> node){
32 if(isNull()){
33 //第一次
34 front.next = node;
35 rear.next = node;
36 maxSize++;
37 }
38 else{
39 node.next = front.next;
40 front.next = node;
41 maxSize++;
42 }
43 }
44 //出隊
45 public QNode<T> pop(){
46 if(isNull())
47 return null;//隊為空時，無法出隊
48 else if(maxSize==1){
49 //隊只有一個元素時直接初始化即可
50 QNode<T> node = front.next;
51 initQueue();
52 return node;
53 }
54 else{
55 //準備工作
56 QNode<T> p = front;//使用p指針來遍歷隊列
57 for(int i=1;i<maxSize-1;i++)
58 p = p.next;
59 //pop
60 QNode<T> node = rear.next;
61 rear.next = p.next;
62 maxSize--;
63 return node;
64 }
65 }
66
67 }
68
69 //鏈隊結點
70 class QNode<T>{
71 private T data;//數據域
72 public QNode<T> next;//指針域
73
74 //初始化1
75 public QNode(){
76 this.data = null;
77 this.next = null;
78 }
79 //初始化2
80 public QNode(T data){
81 this.data = data;
82 this.next = null;
83 }
84
85 public T getData() {
86 return data;
87 }
88 public void setData(T data) {
89 this.data = data;
90 }
91
92 }測試：
1 package test;
2
3 import org.junit.Test;
4
5 public class testQueue {
6
7 @Test
8 public void fun(){
9 LinkQueue<Integer> lq = new LinkQueue<Integer>();
10
11 System.out.println("隊列是否為空："+lq.isNull());
12
13 //依次插入1、2、3、4
14 lq.push(new QNode<Integer>(1));
15 lq.push(new QNode<Integer>(2));
16 lq.push(new QNode<Integer>(3));
17 lq.push(new QNode<Integer>(4));
18
19 //依次出隊
20 System.out.println("依次出隊：");
21 while(!lq.isNull()){
22 System.out.println(lq.pop().getData());
23 }
24
25 }
26 }
關于如何理解隊列及java實現就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
