数组队列
luffy 5/15/2023 data-structure
# 队列
# 1 队列介绍
- 队列是一个有序列表，可以用数组或是链表来实现。
- 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
# 2 数组模拟队列
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如上图, 其中 maxSize 是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front 及 rear 分别记录队列前后端的下标， front 会随着数据输出 而改变，而 rear 则是随着数据输入而改变，如队列介绍中图所示
当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：思路分析:
- 将尾指针往后移：rear+1 , 当 front == rear 【空】
- 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据
注意:front 并没有直接指向数据,而是数据前一位,所以当你要用 front 读取队列头时需要 front+1
代码实现
package com.luffy.queue;
import java.util.Scanner;
/**
* @author dreamLuffe
* @data 2023/5/12 17:49
*/
@SuppressWarnings("all")
public class ArrayQueueDemo {
public static void main(String[] args) {
//创建一个队列
ArrayQueue queue = new ArrayQueue(3);
char key = ' ';//接受用户输入
Scanner scanner = new Scanner(System.in);
boolean loop = true;
//输出一个菜单
while (loop) {
System.out.println("s(show):显示队列");
System.out.println("e(exit):退出程序");
System.out.println("a(add):添加数据到队列");
System.out.println("g(get):从队列取出数据");
System.out.println("h(head):查看队列头的数据");
key = scanner.next().charAt(0);//接受一个字符
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("输入一个数字");
int value = scanner.nextInt(); //不用再new一个新得scanner
queue.addQueue(value);
break;
case 'g':
try {
int res = queue.getQueue();
System.out.printf("取出的数据是%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int head = queue.headQueue();
System.out.printf("表头是%d\n", head);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
default:
scanner.close();//关闭不释放会有异常
loop = false;
break;
}
}
System.out.println("程序退出");
}
}
//使用数组模拟器 编写一个ArrayQueue的类
class ArrayQueue {
private int maxSize; //标识数组最大容量
private int front; //队列头
private int rear; //队列尾部
private int[] arr; //该数组用于存放数据，模拟队列
/**
* 创建队列构造器
* @param maxSize
*/
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
front = -1; //指向队列头部 front指向队列头前一个位置
rear = -1; //指向队列尾的数据（即就是队列最后一个数据）
}
/**
* 判断队列是否满
* @return
*/
public boolean isFull(){
return rear == maxSize -1;
}
/**
* 判断是否为空
* @return
*/
public boolean isEmpty(){
return rear == front;
}
/**
* 添加数据到队列
* @param n
*/
public void addQueue(int n) {
//判断队列是否满
if (isFull()) {
System.out.println("队列满,不能加入数据~~~~~~");
return;
}
rear++; //让rear 往后移动一位
arr[rear] = n; //以后移后的rear作为数组下标进行赋值
}
/**
* 获取队列的数据,出队列
* @return
*/
public int getQueue() {
//判断队列是否为空//抛出异常
if (isEmpty()) throw new RuntimeException("队列为空,不能取数据");
front++; //front后移 出队列
return arr[front];
}
/**
* 显示队列的所有数据
*/
public void showQueue() {
//遍历
if (isEmpty()) {
System.out.println("队列空的 没有数据");
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d]=%d\n", i, arr[i]);
}
}
/**
* 显示队列的头数据,注意不是取出数据
* @return
*/
public int headQueue() {
//判断
if (isEmpty()) throw new RuntimeException("队列空的,没有数据~~~~");
return arr[front + 1]; //front并没有直接指向数据,而是数据前一位,所以需要+1
}
}
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
- 问题分析与优化方向
- 目前数组使用一次就不能用， 没有达到复用的效果.
原因:取出数据时是将列表头(front++)向后移动,导致队列前面的空间并没有被释放
- 将这个数组使用算法，改进成一个环形的队列 取模：%
- 目前数组使用一次就不能用， 没有达到复用的效果.
# 3 数组模拟环形队列思路分析
对前面的数组模拟队列的优化，充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可)
分析说明:
尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的 时候需要注意 (rear + 1) % maxSize == front 满]
rear == front [空]
图解环形队列
front变量的含义做一个调整:front就指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素front的初始值=0rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置.因为希望空出一个空间做为约定 rear 的初始值=0- 当队列满时，条件是
(rear +1)%maxSize=front[满] - 对队列为空的条件，
rear== front(空) - 当我们这样分析，队列中有效的数据的个数
(rear+maxSize-front)%maxSize//rear=1front=06.我们就可以在原来的队列上修改得到，一个环形队列
# 问题
提出疑惑:为什么要先加 maxSize-->可能出现队尾 rear 小于队首 front 的情况
通过这个环形队列图(里面数字是数组下标不是数据)你应该可以很容易理解:假使队列长 8、队尾在 2 的位置、队首在 6 的位置
- 环形队列代码实现
package com.luffy.queue;
import java.util.Scanner;
/**
* @author dreamLuffe
* @data 2023/5/15 08:23
*/
public class CircleArrayQueueDemo {
public static void main(String[] args) {
//创建一个环形队列
System.out.println("创建一个环形队列");
CircleArrayQueue queue = new CircleArrayQueue(3);
char key = ' ';//接受用户输入
Scanner scanner = new Scanner(System.in);
boolean loop = true;
//输出一个菜单
while (loop) {
System.out.println("s(show):显示队列");
System.out.println("e(exit):退出程序");
System.out.println("a(add):添加数据到队列");
System.out.println("g(get):从队列取出数据");
System.out.println("h(head):查看队列头的数据");
key = scanner.next().charAt(0);//接受一个字符
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("输入一个数字");
int value = scanner.nextInt(); //不用再new一个新得scanner
queue.addQueue(value);
break;
case 'g':
try {
int res = queue.getQueue();
System.out.printf("取出的数据是%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int head = queue.headQueue();
System.out.printf("表头是%d\n", head);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
default:
scanner.close();//关闭不释放会有异常
loop = false;
break;
}
}
System.out.println("程序退出");
}
}
class CircleArrayQueue {
private int maxSize;//表示数组的最大容量
private int front; //队列头
private int rear; //队列尾部
private int[] arr;//该数据用于存放数据,模拟队列
//创建队列的构造器
public CircleArrayQueue(int arrMaxSize) {
//注意:如果要能存3个有效数据,arrMaxSize就要为`4`,因为预留了一个位置,所以需要传入的数字要+1
maxSize = arrMaxSize + 1;
arr = new int[maxSize];
/**
* 1. 此处front含义做出调整:front指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素,front的初始值为0*
* 2.此处rear含义做出调整:rear指向队列的最后一个元素的后一个位置,因为希望空出一个空间作为约定(判断栈满栈空),rear的初始值为0
*/
front = rear = 0;
}
//1. 判断队列是否满
public boolean isFull() {
//此时队满条件发生变化,因为rear预留了一个位置
return (rear + 1) % maxSize == front;
}
//2. 判断队列是否为空
public boolean isEmpty() {
return front == rear;
}
/**
* 3.获取队列的有效数量
* @return int 此函数结果用来在 遍历队列数组时防止下标越界
*/
public int getSize() {
return (rear + maxSize - front) % maxSize;
}
//4. 添加数据到队列
public void addQueue(int n) {
//判断是否队满
if (isFull()) {
System.out.println("队列满,不能加入数据~~~~~");
return;
}
arr[rear] = n;//这里需要先赋值再将rear+1,因为rear指向最后一个有效数据
//让rear后移一位,但是需要注意`%`,因为栈尾可以回到下标为`0`处,原因看我画的图
rear = (rear + 1) % maxSize;
}
//5. 获取队列数据 出队列(类似删除数组第一位)
public int getQueue() {
//判断队列是否为空,抛出异常
if (isEmpty()) {
throw new RuntimeException("队列为空,不能取数据");
}
//这里需要先将`front`的值保存下来(或者直接保存arr[front],再去return),因为front此时对应的是第一个有效数据,如果＋1后再返回,将指向错误的有效数据
int thisFront = front;
//front后移,原因与注意点同rear
front = (front + 1) % maxSize;
return arr[thisFront];
}
//6. 显示所有队列的数据
public void showQueue() {
//先判断是否为空
if (isEmpty()) {
System.out.println("队列为空,没有数据");
return;
}
/**
* 1.首先front指向队列第一位,所以要从front开始遍历
* 2.结束
*
*/
for (int i = front; i < front + getSize(); i++) {
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
}
}
//7. 显示队列的头数据,注意不是取出数据
public int headQueue() {
//判断是否为空
if (isEmpty()) {
throw new RuntimeException("队列空的,没有数据~~~~");
}
//front是直接指向队列第一位的,所以这里可以直接返回
return arr[front];
}
}
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151