隊列的特點(diǎn)
1.可以使用數(shù)組和鏈表兩種方式來實現(xiàn)。
2.遵循先入先出(FIFO)的規(guī)則，即先進(jìn)入的數(shù)據(jù)先出。
3.屬于有序列表。
圖解實現(xiàn)過程：
?1.定義一個固定長度的數(shù)組，長度為maxSize。
?2.設(shè)置兩個指針first = -1（指向隊列第一個數(shù)據(jù)的前一位，這樣保證在添加第一個數(shù)據(jù)以后頭指針為0，和數(shù)組的下標(biāo)一樣，且用于操作出隊）和last = -1(指向隊尾，用于操作入隊)。
?3.即first會因為出隊操作而增加，last會因為入隊操作而增加
代碼實現(xiàn)：
|
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 ;//指向隊列頭的前一個位置??！前一個位置?。〕鲫牱较?/code> private int last ;//指向隊列尾部!!即最后一個數(shù)據(jù)?。?！入隊方向 private String[] arr; //先建一個空的數(shù)組，具體長度未知，需要maxSize來確定。 //構(gòu)造器初始化隊列信息 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++; //添加數(shù)據(jù)只和末尾下標(biāo)有關(guān) arr[last] = data; return; } } //出隊 public String getQueue(){ if (isEmpty()) { //因為getQueue方法是int型，需要返回數(shù)據(jù)，如果無數(shù)據(jù)，也需要返回 //如果返回-1或者其他數(shù)據(jù)，會讓人誤解獲取到的數(shù)就是-1或者其他 //所以用拋出異常來處理 throw new RuntimeException("隊列為空，無數(shù)據(jù)~~"); } 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]); } } //獲取隊列頭數(shù)據(jù) public String headQueueData(){ if (isEmpty()){ throw new RuntimeException("無數(shù)據(jù)~~~"); } return arr[++first]; }} |
隊列缺點(diǎn)：
由于出隊操作，使得first指針上移變大，導(dǎo)致數(shù)組前面空出來的位置就不能再繼續(xù)添加數(shù)據(jù)，即不能再被重復(fù)使用，這樣一個隊列只能使用一次，內(nèi)存效率太低，所以需要使用環(huán)形隊列來優(yōu)化解決。
優(yōu)化解決——環(huán)形隊列實現(xiàn)思路
1.first指針初始默認(rèn)設(shè)置為0，指向隊列頭部，則arr[first] 就是第一個數(shù)據(jù)。
2.last指針初始默認(rèn)也為0，但是會隨著增加數(shù)據(jù)而后移。
3.隊列滿的條件：
(last + 1) % maxSize == first
?last+1是為了讓指針后移，而且如果不設(shè)置為 last+1 那么一開始的時候last為0 ， last % maxSize == 0，且first也為0，還沒加數(shù)據(jù)就滿了。
4.隊列為空的條件：
first == last
5.由于判斷是否滿的時候： last+1 ，導(dǎo)致實際上可以裝的數(shù)據(jù)比數(shù)組長度少 1
環(huán)形隊列各步驟及各方法實現(xiàn)講解
1.隊列初始化 ：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class CircleArryQueue{ private int maxSize ; //數(shù)組長度，即隊列最大容量 private int first; //頭指針，控制出隊操作 private int last; //尾指針，控制入隊操作 private int[] arr; //數(shù)組類型，可以換其他的。 //構(gòu)造器初始化信息 public CircleArryQueue(int maxSize){ this.maxSize = maxSize; this.arr = new int[maxSize]; this.first = 0; //這兩個可以不加，不叫也是默認(rèn)為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 主要是為了讓指針后移，特別是在隊列尾部添加數(shù)據(jù)的時候，本來用last也可以判斷，但*是一開始還沒加數(shù)據(jù)的時候，如果直接用last % maxSize == first，結(jié)果是true，所以為了解決指針后*移和判斷是否滿，用來last+1。其次，因為last+1可能會導(dǎo)致數(shù)組指針越界，所以用取模來控制它的范 * 圍，同時保證他會在一個固定的范圍循環(huán)變換，也利于環(huán)形隊列的實現(xiàn)。*/public boolean isFull(){ return (last + 1) % maxSize == first;} |
4.添加數(shù)據(jù)到隊列尾部：入隊
|
1
2
3
4
5
6
7
8
9
10
|
public void pushData(int data){ //先判斷是否滿了 if(isFull()){ System.out.println("隊列已經(jīng)滿啦~~"); return; } arr[last] = data; //last+1是為了后移，取模是為了避免指針越界，同時可以讓指針循環(huán) last = (last + 1) % maxSize;} |
5.取出隊首數(shù)據(jù)：出隊
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public int popData(){ if (isEmpty()) { //拋異常就可以不用返回數(shù)據(jù)了 new RuntimeException("隊列為空，沒有獲取到數(shù)據(jù)~~"); } //要先把first對應(yīng)的數(shù)組數(shù)據(jù)保存——>first后移——>返回數(shù)據(jù) int value = arr[first]; //first+1的操作和last+1是一樣的，取模也是 first = (first+1) % maxSize; System.out.println(value); return value; //如果不保存first指針 那么返回的數(shù)據(jù)就不對了 //如果直接返回數(shù)據(jù)，那first指針還沒后移 也不對，所以需要使用第三方變量 } |
6.展示隊列中所有數(shù)據(jù)：
|
1
2
3
4
5
6
7
8
9
10
|
public void showAllData(){ if (isEmpty()) { System.out.println("隊列為空，沒有數(shù)據(jù)~~"); return; } //此處i不為0，是因為有可能之前有過popData()操作，使得firs不為0，所以最好使用 //first給i動態(tài)賦值， for (int i = first; i < first+size() ; i++) { System.out.println("arr["+i%maxSize+"]"+arr[i%maxSize]); } |
7.獲取隊列中數(shù)據(jù)的總個數(shù)：
|
1
2
3
4
|
public int dataNum(){ //韓順平老師的教程上是這樣寫，但是我理解不了..........。 return (last+maxSize-first) % maxSize; } |
8.查看隊首數(shù)據(jù)但不彈出：
|
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 練習(xí);import java.util.Scanner;public class CircleArryQueue { public static void main(String[] args){ CircleQueue circleQueue = new CircleQueue(4); System.out.println("--------測試環(huán)形隊列--------"); char key = ' '; Scanner scanner = new Scanner(System.in); boolean flag = true; while (flag){ System.out.println("s(showAllData):查看隊列數(shù)據(jù)"); System.out.println("p(pushData):隊尾添加數(shù)據(jù)"); System.out.println("g(popData):彈出隊頭數(shù)據(jù)"); System.out.println("h(seefirstData)：獲取隊頭數(shù)據(jù)"); System.out.println("e(exit):退出程序"); key = scanner.next().charAt(0); switch (key){ case 's': circleQueue.showAllData(); break; case 'p': System.out.println("輸入一個數(shù)據(jù)："); 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("程序結(jié)束~~~"); }}class CircleQueue { private int maxSize ; //數(shù)組長度，即隊列最大容量 private int first; //頭指針，控制出隊操作 private int last; //尾指針，控制入隊操作 private int[] arr; //數(shù)組類型，可以換其他的。 //構(gòu)造器初始化信息 public CircleQueue(int maxSize){ this.maxSize = maxSize; this.arr = new int[maxSize]; this.first = 0; //這兩個可以不加，不叫也是默認(rèn)為0 this.last = 0; } public boolean isEmpty(){ //頭指針和尾指針一樣 則說明為空 return last == first; }/**這里的 last+1 主要是為了讓指針后移，特別是在隊列尾部添加數(shù)據(jù)的時候，本來用last也可以判斷但*是一開始還沒加數(shù)據(jù)的時候，如果直接用last % maxSize == first，結(jié)果是true，所以為了解決指針*后移和判斷是否滿，用來last+1。其次，因為last+1可能會導(dǎo)致數(shù)組指針越界，所以用取模來控制它*的范圍，同時保證他會在一個固定的范圍循環(huán)變換，也利于環(huán)形隊列的實現(xiàn)。*/ public boolean isFull(){ return (last + 1) % maxSize == first; } public void pushData(int data){ //先判斷是否滿了 if(isFull()){ System.out.println("隊列已經(jīng)滿啦~~"); return; } arr[last] = data; //last+1是為了后移，取模是為了避免指針越界，同時可以讓指針循環(huán) last = (last + 1) % maxSize; } public int popData(){ if (isEmpty()) { //拋異常就可以不用返回數(shù)據(jù)了 throw new RuntimeException("隊列為空，沒有獲取到數(shù)據(jù)~~"); } //要先把first對應(yīng)的數(shù)組數(shù)據(jù)保存——>first后移——>返回數(shù)據(jù) int value = arr[first]; //first+1的操作和last+1是一樣的，取模也是 first = (first+1) % maxSize; System.out.println(value); return value; //如果不保存first指針 那么返回的數(shù)據(jù)就不對了 //如果直接返回數(shù)據(jù)，那first指針還沒后移 也不對，所以需要使用第三方變量 } //查看所有數(shù)據(jù) public void showAllData(){ if (isEmpty()) { System.out.println("隊列為空，沒有數(shù)據(jù)~~"); } //此處i不為0，是因為有可能之前有過popData()操作，使得firs不為0，所以最好使用 //first給i動態(tài)賦值， for (int i = first; i < first+dataNum() ; i++) { System.out.println("arr["+i%maxSize+"]"+arr[i%maxSize]); } } //查看有效數(shù)據(jù)個數(shù) public int dataNum(){ //韓順平老師的教程上是這樣寫，但是我理解不了..........。 return (last+maxSize-first) % maxSize; } //查看隊列第一個數(shù)據(jù) public int seeFirstData(){ System.out.println(arr[first]); return arr[first]; }} |
最后：
部分內(nèi)容參考自B站韓順平老師java數(shù)據(jù)結(jié)構(gòu)課程
到此這篇關(guān)于Java 單向隊列及環(huán)形隊列的實現(xiàn)原理的文章就介紹到這了,更多相關(guān)Java 單向隊列及環(huán)形隊列內(nèi)容請搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：https://www.cnblogs.com/coding-996/p/12246672.html
