社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
环形队列
队列是一种常用的数据结构,这种结构保证了数据是按照“先进先出”的原则进行操作的,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,即最先进去的元素也是最先出来的元素.环形队列是一种特殊的队列结构,保证了元素也是先进先出的,但与一般队列的区别是,他们是环形的,即队列头部的上个元素是队列尾部,通常是容纳元素数固定的一个闭环。
应用场景
整体思路
设置一个固定长度为maxSize的数组,设置一个记录数组下次插入数据的 下标rear,一个数组下次删除数据的下标front,通过每次插入删除移动一位rear或front的值
rear和front必须考虑取模,当rear指向数组最后一个位置继续添加时,此时认为一轮添加的循环结束,此时rear = (rear + 1) % maxSize;当front指向数组最后一个位置继续获取数据时,此时认为一轮获取的循环结束,此时front = (front + 1) % maxSize;
设置一个判断rear和front是否为同一轮的标记flag,同一轮为true,不是同一轮为false
图解
代码思路分析
front:front的初始值为0,指向队列将要取出数据的位置
rear:rear初始值为0,指向队列将要添加数据的位置
maxSize :数组的长度
flag:初始值为true,添加数据和获取数据在同一次循环中,此时rear>=front,当rear执行完一轮之后将flag设置为false,此时rear<=front,当获取完一次完整的数据后,即开始第二轮循环后,front再次设置为0,同时设置flag为false
只有当rear == front时,队列添加和获取的数组下标相同,所以此时队列为空的或者是满的,如果rear 和front是同一轮循环,说明数组是空的,否则数组是满的
队列为空的条件: flag && rear == front
队列满的条件: !flag && rear == front
队列中有效的数据的个数 int size = flag ? rear - front : rear + maxSize - front
代码实现
public static void main(String[] args) {
System.out.println("数组模拟环形队列:");
CircleArrayQueue arrayQueue = new CircleArrayQueue(4);
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 'e':
loop = false;
scanner.close();
System.out.println("程序退出!");
break;
case 'a':
System.out.println("输入一个数");
int value = scanner.nextInt();
arrayQueue.addQueue(value);
break;
case 'g':
int res = arrayQueue.getQueue();
System.out.println("取出的数据是: " + res);
break;
case 'h':
int head = arrayQueue.heanQueue();
System.out.println("第一个数据是: " + head);
break;
default:
break;
}
System.out.println();
}
}
class CircleArrayQueue {
private int maxSize; //表示数组最大容量
private int front; //front变量指向队列的第一个元素,front的初始值为0
private int rear; //rear变量指向队列的最后一个元素,rear初始值为0
private int[] arr; //该数组用于存放数据,模拟队列
boolean flag; //判断标记:true则为同一轮,false则开始了新的一轮循环
//创建队列构造器
public CircleArrayQueue(int arrayMaxSize) {
maxSize = arrayMaxSize;
arr = new int[arrayMaxSize];
front = 0; //指向队列将要取出数据的位置
rear = 0; //指向队列将要添加数据的位置
flag = true; //标记为true,用来判断rear和front是不是在同一轮中,即rear是否开始了下一轮的循环添加
}
/**
* 判断队列是否满
*/
public boolean isFull() {
/*
* 当flag为false时说明下一次添加数据将会是下一轮循环,当rear和front一样时,
* 说明rear队列添加数据的位置与获取数据的位置相同,此时队列是满的
*/
return !flag && rear == front;
}
/**
* 判断队列是否为空
*/
public boolean isEmpty() {
/*
* flag为true说明添加数据和获取数据在同一轮循环中,此时队列添加数据的位置与获取数据的位置相同
* 说明队列是空的
*/
return flag && rear == front;
}
/**
* 添加队列数据
*/
public void addQueue(int n) {
if (isFull()) {
System.out.println("队列满了,不能添加数据!");
return;
}
//将rear后移,这里必须考虑取模
arr[rear] = n;
rear = (rear + 1) % maxSize;
//若果rear取模后为0,说明队列开始了新的循环
if (rear == 0) flag = false;
}
/**
* 获取队列的数据,出队列
*/
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空,不能获取数据!");
}
//这里需要分析出front指向队列的第一个元素
//1.先把front对应的值保存到一个临时变量
//2.将front后移,考虑取模
//3.将临时保存的变量返回
int val = arr[front];
front = (front + 1) % maxSize;
//如果front取模后为0,说明队列里添加和获取在同一轮循环中
if (front ==0 ) flag = true;
return val;
}
/**
* 显示队列所有数据
*/
public void showQueue() {
//遍历
if(isEmpty()) {
System.out.println("队列是空的,没有数据!");
return;
}
//思路,从front开始遍历
int size = size();
for (int i = front; i < front + size; i++) {
System.out.print(arr[i % maxSize] + " ");
}
}
/**
* 显示队列的头数据
*/
public int heanQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空,不能获取数据!");
}
return arr[front];
}
//求出当前数据有效数据个数
public int size() {
return flag ? rear - front : rear + maxSize - front;
}
}
------此文章总结改造来自韩顺平老师讲解的java数据结构与算法
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!