队列
是一种先进先出的的存储结构,在很多场景中适用例如银行排队系统,也就是说但凡涉及排队的都离不开队列。
但是线性队列会有假溢出的缺陷,因此引入循环队列。
队列一般有几个常用方法,1.判断为空;2.判断为满;3.加入元素;4删除元素;下面将从这四个方法入手来学习循环队列
本文只讲循环队列----留空法,假设你已经了解队列的一些基础知识
首先我们来看一张图---此队列全长为6,那我们就用 maxSize 表示吧。
编辑
添加图片注释,不超过 140 字(可选)
1、判断为空
刚开始从图中我们能很简单的看出,队列的判断为空的条件,那就是 rear==front
那么现在我们进行元素的加入,假定加入元素rear= rear+1,删除元素front = front +1;如下图所示,我们进行一定元素的加入此时rear = 3;
编辑
添加图片注释,不超过 140 字(可选)
当我们进行元素加满时,此时 rear = 0 front = 1(将上图的a进行删除,front +1)那我们可以容易的判断队伍满的条件(rear +1 == front) (假设为这个公式)
此时你是否有很多问号??,加入一个元素rear+1 ,那么如图所示,在加入元素满一个循环后,rear 怎么变为0呢? 那么我们加入元素不是rear = rear +1 ;
而是
rear = (rear+1)% maxSize;
那么在加入元素满一个循环之后不就可以一直可以从下标 0-5 之间了。
到此加入元素公式已经搞定为: rear = (rear+1)% maxSize;
编辑
添加图片注释,不超过 140 字(可选)
那么经历过以上问题,删除元素不应该也是这样吗?当满一圈后front = front+1时,就会造成下标不对应
因此我们对加入元素的公式进行改进: front= (front+1)% maxSize;
到此元素删除的公式已经完成:front= (front+1)% maxSize;
那么此时我们来看看判断队伍满,我们上面假设队伍满的条件(rear +1 == front) 这样行不行呢?
答案是不行的?为什么呢? 因为我们加入元素公式为:rear =(rear +1) % maxSize;
删除元素公式为:front= (front+1)% maxSize;
当我们在第一圈时,队列加满元素时:rear =5 front = 0; 利用这个判断为满的公式
(rear +1 == front) 此时rear + 1=6 front ==0 显然不相等
进行改进为:((rear +1)% maxSize == front)
综上
判断为空: rear==front
加入元素: rear = (rear+1)% maxSize;
删除元素:front= (front+1)% maxSize;
判断为满:((rear +1)% maxSize == front);
那么队伍长度怎么看呢?
留下公式 自己证明:
(maxSize +rear -front)%maxSize
过程就是看,加入元素不够一圈时候队长为多少,加入元素超过一圈后队长为多少;
代码
class ArrayQueue1 {
private int MaxSize;
private int front;
private int rear;
private int[] arr;
//创建队列的构造器
public ArrayQueue1(int maxSize) {
MaxSize = maxSize;
arr = new int[maxSize];
front = 0;
rear = 0;
}
public boolean isFull() {
return (rear + 1) % MaxSize == front;
}
public boolean isEmpty() {
return front == rear;
}
public void addQueue(int n) {
//判断队列满
if (isFull()) {
System.out.println("队列满,不能加入数据");
return;
}
arr[rear] = n;
rear = (rear + 1) % MaxSize;
}
// 获取队列的数据
public int getQueue() {
if (isEmpty()) {
// 抛出异常
throw new RuntimeException("队列为空,不能取出数据");
}
// front 指向队列的第一个元素
// front 后移
int value = arr[front];
front = (front + 1) % MaxSize;
return value;
}
//显示队列的所有数据
public void showQueue() {
//遍历
if (isEmpty()) {
System.out.println("队列为空");
return;
}
// 从front开始遍历
for (int i = front; i < front + size(); i++) {
System.out.printf("arr[%d]=%d\n", i % MaxSize, arr[i % MaxSize]);
}
}
// 显示队列的头数据,不是取出数据
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空,不能查看头数据");
}
return arr[front];
}
//求出当前队列有效数据
public int size() {
return (rear + MaxSize - front) % MaxSize;
}
}