隊列的特點
1.可以使用數組和鏈表兩種方式來實現。
2.遵循先入先出(FIFO)的規則，即先進入的數據先出。
3.屬于有序列表。
圖解實現過程：
?1.定義一個固定長度的數組，長度為maxSize。
?2.設置兩個指針first = -1（指向隊列第一個數據的前一位，這樣保證在添加第一個數據以后頭指針為0，和數組的下標一樣，且用于操作出隊）和last = -1(指向隊尾，用于操作入隊)。
?3.即first會因為出隊操作而增加，last會因為入隊操作而增加
代碼實現：
|
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
84
85
86
87
88
89
90
91
92
|
package 隊列;public class ArrayQueueTest { public static void main(String[] args) { ArrayQueue arrayQueue = new ArrayQueue(3); arrayQueue.addQueue("瓊"); arrayQueue.addQueue("赟"); arrayQueue.addQueue("瓏"); arrayQueue.showAllQueueData(); System.out.println(arrayQueue.getQueue()); }}class ArrayQueue{ private int maxSize;//定義隊列的最大長度 private int first ;//指向隊列頭的前一個位置！！前一個位置！！出隊方向 private int last ;//指向隊列尾部!!即最后一個數據！！！入隊方向 private String[] arr; //先建一個空的數組，具體長度未知，需要maxSize來確定。 //構造器初始化隊列信息 public ArrayQueue(int maxSize){ this.maxSize = maxSize; this.first = -1; this.last = -1; arr = new String[maxSize]; } //判斷是否為空 public boolean isEmpty(){ if (first == last) { System.out.println("隊列為空~~"); return true; }else { System.out.println("隊列不為空~~"); return false; } } //判斷隊列是否滿 public boolean isFull(){ if (last == maxSize-1) { System.out.println("隊列已滿~~"); return true; }else { System.out.println("隊列未滿~~"); return false; } } //入隊 public void addQueue(String data){ if (last == maxSize-1){ System.out.println("隊列已滿，不能再添加！！"); return; }else { last++; //添加數據只和末尾下標有關 arr[last] = data; return; } } //出隊 public String getQueue(){ if (isEmpty()) { //因為getQueue方法是int型，需要返回數據，如果無數據，也需要返回 //如果返回-1或者其他數據，會讓人誤解獲取到的數就是-1或者其他 //所以用拋出異常來處理 throw new RuntimeException("隊列為空，無數據~~"); } else { first++; return arr[first]; } } //遍歷隊列所有信息 public void showAllQueueData(){ if (first == last){ return; } for (int i = 0; i < arr.length; i++) { System.out.println("arr["+i+"]"+"="+arr[i]); } } //獲取隊列頭數據 public String headQueueData(){ if (isEmpty()){ throw new RuntimeException("無數據~~~"); } return arr[++first]; }} |
隊列缺點：
由于出隊操作，使得first指針上移變大，導致數組前面空出來的位置就不能再繼續添加數據，即不能再被重復使用，這樣一個隊列只能使用一次，內存效率太低，所以需要使用環形隊列來優化解決。
優化解決——環形隊列實現思路
1.first指針初始默認設置為0，指向隊列頭部，則arr[first] 就是第一個數據。
2.last指針初始默認也為0，但是會隨著增加數據而后移。
3.隊列滿的條件：
(last + 1) % maxSize == first
?last+1是為了讓指針后移，而且如果不設置為 last+1 那么一開始的時候last為0 ， last % maxSize == 0，且first也為0，還沒加數據就滿了。
4.隊列為空的條件：
first == last
5.由于判斷是否滿的時候： last+1 ，導致實際上可以裝的數據比數組長度少 1
環形隊列各步驟及各方法實現講解
1.隊列初始化 ：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class CircleArryQueue{ private int maxSize ; //數組長度，即隊列最大容量 private int first; //頭指針，控制出隊操作 private int last; //尾指針，控制入隊操作 private int[] arr; //數組類型，可以換其他的。 //構造器初始化信息 public CircleArryQueue(int maxSize){ this.maxSize = maxSize; this.arr = new int[maxSize]; this.first = 0; //這兩個可以不加，不叫也是默認為0 this.last = 0; }} |
2.判斷隊列是否為空：
|
1
2
3
4
|
public boolean isEmpty(){ //頭指針和尾指針一樣 則說明為空 return last == first; } |
3.判斷隊列是否滿：
|
1
2
3
4
5
6
7
|
/**這里的 last+1 主要是為了讓指針后移，特別是在隊列尾部添加數據的時候，本來用last也可以判斷，但*是一開始還沒加數據的時候，如果直接用last % maxSize == first，結果是true，所以為了解決指針后*移和判斷是否滿，用來last+1。其次，因為last+1可能會導致數組指針越界，所以用取模來控制它的范 * 圍，同時保證他會在一個固定的范圍循環變換，也利于環形隊列的實現。*/public boolean isFull(){ return (last + 1) % maxSize == first;} |
4.添加數據到隊列尾部：入隊
|
1
2
3
4
5
6
7
8
9
10
|
public void pushData(int data){ //先判斷是否滿了 if(isFull()){ System.out.println("隊列已經滿啦~~"); return; } arr[last] = data; //last+1是為了后移，取模是為了避免指針越界，同時可以讓指針循環 last = (last + 1) % maxSize;} |
5.取出隊首數據：出隊
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public int popData(){ if (isEmpty()) { //拋異常就可以不用返回數據了 new RuntimeException("隊列為空，沒有獲取到數據~~"); } //要先把first對應的數組數據保存——>first后移——>返回數據 int value = arr[first]; //first+1的操作和last+1是一樣的，取模也是 first = (first+1) % maxSize; System.out.println(value); return value; //如果不保存first指針 那么返回的數據就不對了 //如果直接返回數據，那first指針還沒后移 也不對，所以需要使用第三方變量 } |
6.展示隊列中所有數據：
|
1
2
3
4
5
6
7
8
9
10
|
public void showAllData(){ if (isEmpty()) { System.out.println("隊列為空，沒有數據~~"); return; } //此處i不為0，是因為有可能之前有過popData()操作，使得firs不為0，所以最好使用 //first給i動態賦值， for (int i = first; i < first+size() ; i++) { System.out.println("arr["+i%maxSize+"]"+arr[i%maxSize]); } |
7.獲取隊列中數據的總個數：
|
1
2
3
4
|
public int dataNum(){ //韓順平老師的教程上是這樣寫，但是我理解不了..........。 return (last+maxSize-first) % maxSize; } |
8.查看隊首數據但不彈出：
|
1
2
3
|
public void seeFirstData(){ return arr[first];} |
全部代碼整合：
|
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
package 練習;import java.util.Scanner;public class CircleArryQueue { public static void main(String[] args){ CircleQueue circleQueue = new CircleQueue(4); System.out.println("--------測試環形隊列--------"); char key = ' '; Scanner scanner = new Scanner(System.in); boolean flag = true; while (flag){ System.out.println("s(showAllData):查看隊列數據"); System.out.println("p(pushData):隊尾添加數據"); System.out.println("g(popData):彈出隊頭數據"); System.out.println("h(seefirstData)：獲取隊頭數據"); System.out.println("e(exit):退出程序"); key = scanner.next().charAt(0); switch (key){ case 's': circleQueue.showAllData(); break; case 'p': System.out.println("輸入一個數據："); int obj = scanner.nextInt(); circleQueue.pushData(obj); break; case 'g': circleQueue.popData(); break; case 'h': circleQueue.seeFirstData(); break; case 'e': scanner.close(); flag = false; break; default: break; } } System.out.println("程序結束~~~"); }}class CircleQueue { private int maxSize ; //數組長度，即隊列最大容量 private int first; //頭指針，控制出隊操作 private int last; //尾指針，控制入隊操作 private int[] arr; //數組類型，可以換其他的。 //構造器初始化信息 public CircleQueue(int maxSize){ this.maxSize = maxSize; this.arr = new int[maxSize]; this.first = 0; //這兩個可以不加，不叫也是默認為0 this.last = 0; } public boolean isEmpty(){ //頭指針和尾指針一樣 則說明為空 return last == first; }/**這里的 last+1 主要是為了讓指針后移，特別是在隊列尾部添加數據的時候，本來用last也可以判斷但*是一開始還沒加數據的時候，如果直接用last % maxSize == first，結果是true，所以為了解決指針*后移和判斷是否滿，用來last+1。其次，因為last+1可能會導致數組指針越界，所以用取模來控制它*的范圍，同時保證他會在一個固定的范圍循環變換，也利于環形隊列的實現。*/ public boolean isFull(){ return (last + 1) % maxSize == first; } public void pushData(int data){ //先判斷是否滿了 if(isFull()){ System.out.println("隊列已經滿啦~~"); return; } arr[last] = data; //last+1是為了后移，取模是為了避免指針越界，同時可以讓指針循環 last = (last + 1) % maxSize; } public int popData(){ if (isEmpty()) { //拋異常就可以不用返回數據了 throw new RuntimeException("隊列為空，沒有獲取到數據~~"); } //要先把first對應的數組數據保存——>first后移——>返回數據 int value = arr[first]; //first+1的操作和last+1是一樣的，取模也是 first = (first+1) % maxSize; System.out.println(value); return value; //如果不保存first指針 那么返回的數據就不對了 //如果直接返回數據，那first指針還沒后移 也不對，所以需要使用第三方變量 } //查看所有數據 public void showAllData(){ if (isEmpty()) { System.out.println("隊列為空，沒有數據~~"); } //此處i不為0，是因為有可能之前有過popData()操作，使得firs不為0，所以最好使用 //first給i動態賦值， for (int i = first; i < first+dataNum() ; i++) { System.out.println("arr["+i%maxSize+"]"+arr[i%maxSize]); } } //查看有效數據個數 public int dataNum(){ //韓順平老師的教程上是這樣寫，但是我理解不了..........。 return (last+maxSize-first) % maxSize; } //查看隊列第一個數據 public int seeFirstData(){ System.out.println(arr[first]); return arr[first]; }} |
最后：
部分內容參考自B站韓順平老師java數據結構課程
到此這篇關于Java 單向隊列及環形隊列的實現原理的文章就介紹到這了,更多相關Java 單向隊列及環形隊列內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://www.cnblogs.com/coding-996/p/12246672.html
