Java高级系列文章前言

本文章涉及到数据结构与算法的知识该知识属于Java高级阶段通常为学习的二阶段本系列文章涉及到的内容如下橙色框选内容

本文章核心是教学视频所以属于个人笔记非商用。

文章结构

标识

本系列文章中记录的数据结构与算法都会多多少少用到一些Java的API这些API只会一笔带过主要还是看逻辑思路。

大标题
	小标题
		文本内容和图片内容... 70%/30%
			图片说明加重
				逻辑思路和次要说明
			文本说明普通文本
				主要说明和补充

内容结构

大标题
	介绍
	英文单词关键字陈列(有时会省略)
		代码块...
	思路引入
		概率出现小标题
	思路解析
		概率出现小标题
	源码
		代码展示
		图文说明

环形队列

介绍

在先前的数组队列中我们发现取出的位置不能再使用就造成了一次性存储使用为了解决这个问题我们需要将数组队列优化为环形队列。

英文单词关键字陈列

书写习惯XxxYyyZzzJava类驼峰语法
格式英文单词 -> 中文翻译 -> 空耳个人习惯

Circle -> 环形/圆环 -> sql(比较接近的读音涩扣)

思路引入

环形顾名思义是一个圆环是可循环的结构。我们以公交车作为为例刚开始公交车前排作为是满的于是新上车的人就坐到了后排到达下一个站点后前排的乘客下车后排仍然是满的然后陆续又上来了新的乘客此处后排确实慢了但是新乘客能说公交车满了做一下趟吗当然不用新乘客直接坐在刚刚空闲的前排位置就行了

思路解析

队列Queue是只允许在一端进行插入操作而在另一端进行删除操作的线性表。
队列是一种先进先出First In First Out的线性表简称FIFO。允许插入的一端称为队尾允许删除的一堆称为队头。

循环队列

线性表有顺序存储和链式存储栈是线性表所以有着两种存储方式。同样队列作为一种特殊的线性表也同样存在这两种存储方式。我们先来看队列的顺序存储结构。
队列顺序存储的不足
如果我们只是在队尾追加一个元素则不需要移动任何元素此时队列如下复杂度为O1

如果我们添加一个数据则变为队尾添加一个数据如下图。

与栈不同的是队列元素的出列是在队头即下标为0的位置那也就意味着队列中的所有元素都得向前移动以保证队列的队头也就是下标为0的位置不为空此时时间复杂度为On。
如果这么做则出队的性能会很低我们可以让队头不需要一定在下标为0的位置下图演示了该思路。


为了避免当只有一个元素时队头和队尾重合所以引入两个指针front表示队头指针rear表示队尾下一个位置指针这样当front等于rear时此队列不是还剩一个元素而是空队列如下图所示。

假设是长度为5的数组初始状态front与rear指针均指向0的位置然后入队a1、a2、a3、a4front指针依然指向下标为0位置而rear指针指向下标为4的位置如下图所示。

出队a1,、a2则front指针向下标为2的位置rear不变如下图所示。

如果此时再入队a5那么rear指针再次后移的话rear指针应该指向哪里呢如下图所示。

问题还不止于此。假设这个队列的总个数不超过5个但目前如果接着入队的话因数组末尾元素已经占用再向后加就会产生数组越界的错误可实际上我们队列在下标0和1的地方还是空闲的。我们把这种现象叫做“假溢出”。
循环队列的定义
所以解决假溢出的办法就是后面满了就再从头开始也就是头尾相接的循环。我们把队列这种头尾相接的顺序结构称为循环队列。
刚才的例子我们可以把rear改为指向下标为0的位置这样就不会造成指针指向不明的问题了如下图所示。

接着入队a6将它放置于下标为0处rear指针想下标为1处如下图所示。

如果再次入队a7那么rear指针就与front指针重合了如下图所示。

• 此时问题又出来了我们刚才说空队列时front等于rear现在队列满时也是front等于rear那么如何判断是空还是满呢
• 办法一设置一个标志变量flag当front==rear且flag=0时为队列空当front==rear且flag=1时为队列满。
• 办法二是当队列空时条件就是front=rear当队列满时我们修改器条件保留一个元素空间。也就是说队列满时数组中还有一个空闲单元。也就是说当rear处于最后一个空位置时我们就认定队列已满不允许出现上面的指针重合的情况。

若最大尺寸为QueueSize那么队列满的条件是(rear+1) % QueueSize == front取模"%"的目的就是为了整合rear与front大小为一个问题。比如上面这个例子QueueSize = 5如果front=0而rear=4(4+1)%5=0所以此时队列满再比如如果front=2而rear=1。(1+1)%5=2所以此时队列也是满的。而对于front=2而rear=00+1%5=1,1不等于2所以此时队列并没有满。
另外当rear>front时此时队列的长度为 rear - front。但rear < front时队列长度分为两段一段是QueueSize-front另一段是0+rear0表示预留空位置加在一起队列长度为rear-front+QueueSize。因此通用计算队列长度公式为

(rear-front+QueueSize)%QueueSize

没错计算队列数据长度是rear-front+QueueSize如果计算其剩余空间则取模QueueSize即可。

源码

代码展示

package CircleArray;

public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        CircleArray circleQueue = new CircleArray(4);//队列最大为3因为预留了一位作为约定
        //约定的位置是动态变化的当取出arr[0]再添加一个数据时最后一个数据索引是arr[3]
    }
}
class CircleArray{
    private int maxSize;//表示数组的最大容量
    //front 变量的含义做一个调整front就指向队列的第一个元素也就是arr[front]
    //front 的初始值 = 0
    private int front;
    //rear 变量的含义做一个调整rear指向队列的最后一个元素的后一个位置因为希望空出一个空间作为约定
    //rear 的初始值 = 0
    private int rear;
    private int[]elementData;//实际存放数据的底层数据参考ArrayList底层的elementData
    public CircleArray(int arrMaxSize){
        maxSize = arrMaxSize;
        elementData = new int[maxSize];
        //front = 0;
        //rear =0;
    }
    //判断队列是否已满
    public boolean isFull(){
        //如果maxSize=10 ,rear = 9
        // 9+1 = 10; 10%10=0
        //rear = front = 0
        return (rear +1) % maxSize == front;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return rear == front;
    }
    //添加数据
    public void addQueue(int n){
        //判断队列是否已满
        if(isFull()){
            System.out.println("队列已满...");
            return;
        }
        //直接将数据加入即可
        elementData[rear] = n;
        //将rear后移这里必须考虑取模
        rear = (rear+1) % maxSize;//9取模10=9 10取模10=0
    }
    //获取队列的数据出队列
    public int getQueue(){
        //判断队列是否空
        if(isEmpty()){
            //抛出异常
            throw new RuntimeException("队列空不能取数据");
        }
        //这里需要分析出 front 是指向队列的第一个元素
        //1.先把 front 对应的值保存到一个临时的变量中
        //2.将 front 后移,考虑取模
        //3.将临时保存的变量返回
        int value = elementData[front];
        front = (front +1) % maxSize;//取模 防止越界
        return value;
    }
    //显示队列的所有数据
    public void showQueue() {
        //遍历elementData
        if (isEmpty()) {
            System.out.println("队列为空");
            return;
        }
        //思路从 front 开始遍历遍历多少个元素
        for (int i = front; i < front +size() ; i++) {
            System.out.printf("elementData[%d]=%d\n",i%maxSize,elementData[i%maxSize]);
        }
    }
    //求出当前队列有效数据的个数
    public int size(){
        //假设rear = 9 ; maxSize = 10; front = 5
        // 9+10-5 % 10
        //19 - 5 = 14
        //14 % 10 = 4
        return (rear + maxSize - front) % maxSize;
    }
    //显示队列头元素注意不是取出数据
    public int headQueue(){
        //判断
        if(isEmpty()){
            throw new RuntimeException("队列空的没有数据");
        }
        return elementData[front];//front本身就指向队列的第一个元素
    }
}

图文说明

上面我们说完了理论也就是说想要达成一个环形队列后如果rear>front计算公式为rear-front比如front=0rear=4按照公式4-0=4,此时表示有4个元素这是队列长度如果是计算空位置则直接用rear-front的结果去取模QueueSize假如QueueSzie是5,4%5=1表明剩余空间只有1。如果是front > rear表示已经出现了循环rear回到了取出的队列位置此时计算队列长度的公式为rear-front+QueueSize假如rear=2front=3QueueSize=5按照公式 2-3+5=4表明有4个数据队列长度如果想要求出空位置则用该表达式结果去取模QueueSize 4%5 =1表明此时只有1个空位置了。我们根据这个思路来进行代码的图文解析
1.CircleArray的创建和初始化

2.判断是否为空和是否为满方法

3.添加数据到队列方法

4.取出数据出队列方法

5.显示所有的队列以及队列大小方法和显示队列头方法



6.主方法
该环形队列是有一个空位置作为约定的所以 4个大小相当于3个实际有效位置这里没有进行实际的测试不过代码是可行的