数组环形队列
数组环形队列
背景
-
数据结构——数组环形队列
-
博主以b站尚硅谷Java数据结构与算法课进行学习
概念
- 对数据环形队列进行优化，解决普通数组队列不能重复使用数组的问题
- 通过取模来实现
思路
- 调整front变量：将front指向队列的第一个元素，front赋初值为0
- 调整rear变量： 将rear指向队列的倒数第二个位置的元素，空出来的空间位置作为约定，rear赋初值为0
- 当队列满时，（rear + 1）% maxSize = front//算法
- 当队列空时，rear==front
- 队列中有效的数据的个数（rear+maxSize-front）%maxSize//算法
修改ArrayQueue类实现
-
修改ArrayQueue类
-
代码实现
1
2
3
4
5
6
7
8
9
10
11
12class CircleArray{
private int maxSize;//表示数组的最大容量
private int front;//队列头,指向队列第一元素，赋0值
private int rear;//队列尾，指向队列倒数第二个元素，赋0值
private int[] arr;//存储队列的数组
public CircleArray(int arrMaxSize){
maxSize = arrMaxSize;
arr = new int[maxSize];
front = 0;
rear = 0;
}
}
-
-
修改isFull（）方法判断队列是否为满
-
当队列满时，（rear + 1）% maxSize = front//算法
-
代码实现
1
2
3public boolean isFull(){
return (rear+1)%maxSize == front;
}
-
-
修改isEmpty（）方法判断队列是否空
-
当队列空时，rear==front
-
代码实现
1
2
3public boolean isEmpty(){
return rear == front;
}
-
-
修改addQueue（）方法添加数据
-
先判断队列是否满，再添加数据进入队列
-
代码实现
1
2
3
4
5
6
7
8
9
10
11public void addQueue(int n){
//判断队列是否满
if(isFull()){
System.out.println("队列满了，不能再添加数据");
return;
}
//直接将数据加入
arr[rear] = n;
//将rear后移，考虑取模
rear = (rear+1)%maxSize;
}
-
-
修改getQueue（）方法获取队列，出队列
-
先判断队列是否空，若有数据，则将数据出队列
-
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15//获取队列,出队列
public int getQueue(){
//判断队列是否为空
if(isEmpty()){
//抛出异常
throw new RuntimeException("队列空，不能取数据");
}
//front是指向队列的第一个元素
// 1.将front对应的值保留到一个临时变量
// 2.将front 后移
// 3.将临时保存的变量返回
int value = arr[front];
front = (front+1)%maxSize;
return value;
}
-
-
修改showQueue（）方法显示队列所有数据
-
先判断队列是否为空，若存在数据就显示数据
-
代码实现
1
2
3
4
5
6
7
8
9
10//显示队列所有数据
public void showQueue(){
if (isEmpty()){
System.out.println("队列空没有数据");
}
//思路：从front开始遍历，遍历的多少个元素
for (int i = 0;i< front+size();i++) {//取模
System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
}
}1
2
3
4//求出当前队列有效数据的个数
public int size(){
return (rear+maxSize-front)%maxSize;//取模
}
-
-
修改headQueue（）方法显示队列头数据
-
代码实现
1
2
3
4
5
6
7//显示队列头数据
public int headQueue(){
if (isEmpty()) {
throw new RuntimeException("队列空没有数据");
}
return arr[front];//ArrayQueue中是front+1
}
-
-
CircleArrayDemo类测试
-
代码实现与ArrayQueueDemo类大体相同
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
48public class CircleArrayDemo {
public static void main(String[] args) {
System.out.println("测试环形数据队列");
CircleArray arrayQueue = new CircleArray(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':
arrayQueue.showQueue();
break;
case'a':
System.out.print("请输入一个数：");
int value = scanner.nextInt();
arrayQueue.addQueue(value);
break;
case'g':
try{
int res = arrayQueue.getQueue();
System.out.printf("取出的数据是%d\n",res);
}catch(Exception e){
System.out.println(e.getMessage());
}
break;
case'h':
try{
int res = arrayQueue.headQueue();
System.out.printf("队列头的数据是%d\n",res);
}catch(Exception e){
System.out.println(e.getMessage());
}
break;
case'e':
scanner.close();
loop = false;
break;
}
}
System.out.println("退出");
}
}
-
运行结果图
-
addQueue（）方法
-
getQueue（）方法
-
showQueue（）方法
-
headQueue（）方法
