Kafka Filecoin maven golang爬虫 Gradle xamarin 建造师报考条件 vue路由 后台管理页面模板 后台界面 java两个数组合并 git显示所有远程分支 mysql设置自增初始值 js对象添加元素 oracle连接字符串 mysql查询结果拼接 matlab图像滤波 linuxmysql启动命令 linux启动数据库 python搭建环境 怎么配置java环境 java文件重命名 java时间类型 java包名 java日期格式化 java字符串函数 java获取url参数 内存整理工具 微信签名一句话至自己 马赛克软件 eml文件阅读器下载 raid0教程 在线手册 地下城怎么双开 ip切换软件 ps蒙版抠图详细教程 dnf瞎子传说套选择 hdcp是什么 3dmax布尔运算 ssh框架原理及流程
当前位置: 首页 > 学习教程  > 编程语言

数据结构与算法之数组和队列

2020/11/4 15:05:20 文章标签:

应用实例 以上图片分析: 因为该二维数组的很多值是默认值0,因此记录了很多没有意义的数据 稀疏数组 基本介绍 ➢ 使用场景:单一个数组中大部分元素为0,或为同一个值时,可以 使用稀疏数组来存储 ➢ 处理方法&#xf…

应用实例
在这里插入图片描述
以上图片分析:
因为该二维数组的很多值是默认值0,因此记录了很多没有意义的数据

稀疏数组

基本介绍
➢ 使用场景:单一个数组中大部分元素为0,或为同一个值时,可以 使用稀疏数组来存储
➢ 处理方法:1.记录数组一共有几行几列,有多少个不同值
2.把具有不同值得元素得行和列记录在一共小规模的数组中
举例子了解稀疏数组
在这里插入图片描述
题:使用稀疏数组来保留类似前面的二维数组
思路:
➢ 1. 遍历原始的二维数组,得到有效数据的个数sum
➢ 2. 根据sum就可以创建稀疏数组sparseArr int[sum+1][3]
➢ 3. 将二维数组的有效数据存入到稀疏数组 在这里插入图片描述
代码实现

//创建一共二维数组11*11
	//0:表示没有棋子 1:表示黑子 2表示篮子
	int chessArr1[][]=new int [11][11]
	chessArr1[1][2]=1
	chessArr1[2][3]=2
	for(int [] row:chessArr1){
		for(int data:row){
			system.out.printf("%d\t",data)
		}
	}
	//	遍历二维数组得到非0数据个数
	int sum=0;
	for(int i=0;i<11;i++){//遍历行
		for(int j=0;j<11;j++){//遍历列
		if(chessArr1[i][j])!=0){
			sum ++;
			}
		}
	}
	//创建对应的稀疏数组
	int sparseArr[][]=new int[sum +1][3];
	//给稀疏数组赋值
	sparseArr[0][0]=11;
	sparseArr[0][1]=11;
	sparseArr[0][2]=sum;
	//遍历二维数组,将非0值存放到稀疏数组
	int count=0;//用于记录是第几个非0数据
	for(int i=0;i<11;i++){//遍历行
		for(int j=0;j<11;j++){//遍历列
		if(chessArr1[i][j])!=0){
			count++;
			sparseArr[count][0]=i;
			sparseArr[count][1]=j;
			sparseArr[count][2]=chessArr1[i][j];
			}
		}
	}
	//输出稀疏数组
	for(int i=0;i<sparseArr.length;i++){
		system.out.printf("%d\+%d\+%d\+\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2])
	}

题:稀疏数组转二维数组
思路:
➢1.先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,chessArr2=int[11][11]
➢ 2.在读取稀疏数组后几行的数据,并赋值给二维数组

代码实现

//1.先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组
		int chessArr2[][]=new int[sparseArr[0][0][sparseArr[0][1]];
		//2.在读取稀疏数组后几行的数据,并赋值给二维数组
		for(int i=1;i<sparseArr.length;i++){
		chessArr2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
	//输出二维数组
	for(int[]row:chessArr2){
		for(int data:row){
		system.out.printf("%d\t",data);
		}
	}

队列

官方定义:队列(quene)是允许在一端进行插入操作,而在另一端进行删除操作的线性表
在这里插入图片描述
1.队列是一个有序列表,可以用数组或是链表来实现。
2.遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出

比如春运时的标语排队走得了、走的及时、走得安全、走的舒适

在这里插入图片描述
优先排队的人, 优先处理. (买票, 结账, WC)
在这里插入图片描述
队列的插入和删除
对于栈来说,只需要一个栈顶指针就可以了。
但是对于队列来讲,需要两个指针:一个是head指针,指向队头,一个tail指针,指向队尾。
在这里插入图片描述
这里图中初始化无数据的时候队首和队尾都为-1,
当有数据增加的时候,队尾在变化,而队首没有变化,说明是队首添加数据
在这里插入图片描述
当有数据取出的时候,队首在变化,而队尾没有变化,说明是队尾去除数据

消息队列实现方式

数组模拟队列
➢队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如下图,其中maxSize是该队列的最大容量。

➢因为队列的输出、输入是分别从前后端来处理,因此需要两个变量frontrear分别记录队列前后端的下标

使用front记录队首、使用rear记录队尾

front 会随着数据输出而改变代表取出数据,而rear则是随着数据输入而改变代表添加数据

如图所示:
在这里插入图片描述
当我们将数据存入队列时称为"addQueue",思路分析如下:
1.判断队列是否满或是否为空,然后才将队尾指针rear往后移:rear+1
2.队尾指针rear小于数组长度-1可以添加,若队尾指针rear==maxSize-1则代表队列已满

编写代码如下:

//使用数组模拟队列-编写ArrayQueue类
public class ArrayQueue {

    private int maxSize; //表示数组的最大容量
    private int front; //队列头
    private int rear; //队列尾
    private int[] arr; //该数据用于存放数据,模拟队列

    //创建队列的构造器
    public ArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];//初始化数组
        front = -1; //指向队列头部,即返回即第一个数据的前一个位置
        rear = -1;//指向队列尾部,即返回队列尾的数据(即包含队列最后一个数据)
    }

    //判断队列是否已满
    public boolean isFull(){
        return rear==maxSize-1;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return rear==front;
    }
    //添加数据到队列
    public void addQueue(int n){
        //判断队列是否已满,已满不可添加
        if(isFull()){
            System.out.println("队列已满,无法添加数据");
            return ;
        }
        //后移并添加数据
        arr[++rear]=n;
    }
    //从队列取出数据
    public int getQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空,不能取出数据");
            //无需在return  因为throw有带return
        }
        //取出数据后,队头需要往后移,然后返回数据
        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]);
        }
    }
    //打印队列头部数据
    public int showheadQueue(){
        //判断队列是否为空
        if (isEmpty()) {
            throw new RuntimeException("队列为空,没有数据");
        }
        return arr[front+1];
    }
}

现在添加数据完成方法测试看看队列

 //创建一个队列
ArrayQueue arrayQueue = new ArrayQueue(3);

System.out.println("打印队列数据----------------");
arrayQueue.showQueue();//打印队列数据

System.out.println("\n添加数据:10");
arrayQueue.addQueue(10);//添加一个数据10

System.out.println("\n打印队列数据----------------");
arrayQueue.showQueue();//打印队列数据

//打印头部数据
System.out.println("\n\n显示队列队首信息:"+arrayQueue.showheadQueue());

运行结果如下:

打印队列数据----------------
队列为空,无法打印数据

添加数据:10

打印队列数据----------------
arr[0]=10    arr[1]=0    arr[2]=0    

显示队列队首信息:10

现在数据添加成功、打印数据添加成功、输出队首数据成功,那么继续添加数据看看

System.out.println("\n添加数据:20");
arrayQueue.addQueue(20);//添加一个数据10

System.out.println("\n添加数据:30");
arrayQueue.addQueue(30);//添加一个数据10

System.out.println("\n添加数据:40");
arrayQueue.addQueue(40);//添加一个数据10

那么打印看看会是什么结果呢?

添加数据:20

添加数据:30

添加数据:40
队列已满,无法添加数据

我们发现队列空间为三,再次添加第四个数据的时候,就会出现队列已满无法添加数据的异常

那么我们这样使用数组模拟队列,有没有问题呢?

答案是有的,即数据取出后指向队首的指针上去了,虽然之前的空间没有数据了但无法再次使用了。再次添加数据的时候显示队列已满

问题分析并优化
1.目前数组使用一次就不能再次使用,没有达到复用的效果
2.将数组使用算法,改成环形数组模拟环形队列,使用%
在这里插入图片描述
如何将数组转换成模拟循环队列呢?

思路分析如下:

1.front指针作用进行调整:front指向数组第一个元素,初始值front=0

2.rear指针作用进行调整:rear指向队列的最后一个元素后一个元素,初始值rear=0

原先rear指向的是最后一个元素,现在指向最后一个元素后一个元素为空做约定,这样队列满了之后队首数据front前面元素就为空了,在前一个元素就是队列里的最后一个元素了
在这里插入图片描述

3.当队列满时,条件是:(rear+1)%maxSize==front

原先线性数组判断满的条件为rear=maxSize-1,没有考虑复用,即现在是一个环,那么此时的条件=(rear+1)%maxSize==front
在这里插入图片描述

4.当队列为空的条件:rear==front

5.队列中有效的个数:(rear+maxSize-front)%maxSize

在这里插入图片描述
编写代码如下:

public class CircleArray {

    private int maxSize; //表示数组的最大容量
    //front 就指向队列的第一个元素,也就是说arr[ front]
    //front的初始值= 0
    private int front;
    //rear指向队列的最后一个元素的后一个位置。因为希望空出一个位置做约定区分队列满没满
    //rear的初始值= 0
    private int rear; //队列尾.
    private int[] arr; //该数据用于存放数据,模拟队列

    public CircleArray(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
    }
    //判断队列是否满
    public boolean isFu1l () {
        return (rear + 1) % maxSize == front;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return rear==front;
    }
    //添加数据到队列
    public void addQueue(int n) {
    //判断队列是否满
        if (isFu1l()) {
            System.out.println("队列满,不能加入数据~");
            return;
        }
        //因为rear本身指向最后一个元素的后一个位置
        //所以直接赋值,在将rear后移
        arr[rear] = n;
        //rear往后移需要% 即使回到前面有空余的空间位置
        //因为环形队列是一个环,不能像线性数组直接++ 会造成数组越界
        rear=(rear+1)%maxSize;
        //比如说有模拟环形队列数组长度5分别为2,6,7,8
        //即下标4是rear指向最后一个元素的后一个位置
        //如果取出队列数据2,front=1 那么目前的队列数据即是  6,7,8
        //这时rear要回到下标0,不能是++等于下标4 ,所以取% 回到0
    }
    //从队列取出数据
    public int getQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空,不能取出数据");
            //无需在return  因为throw有带return
        }
        //front的含义:指向队列的第一个元素
        //1.先把front对应的值保存到临时变量
        //2.将front后移,指向新的队列第一个元素,考虑取%
        //3.将临时的变量弹出返回
        int value=arr[front];
        front=(front+1)%maxSize;
        return value;
        //比如说有模拟环形队列数组长度5分别为2,6,7,8
        //如果取出队列数据2,那么此时front需要往后移指向新的首数据
        //但是front不能++,因为如果++的话,到了最后一个元素是下标3
        //弹出后++front=4,再添加数据时,rear=下标0,而front是4会爆出异常所以需要取%
    }

    //打印队列里的数据
    public  void showQueue() {
        //判断队列是否为空
        if (isEmpty()) {
            System.out.println("队列为空,无法打印数据");
            return;
        }
        //不能像线性数组直接循环打印出数据,因为是数组模拟环形队列
        //思路:从front开始遍历,遍历到front+队列有效个数
        //循环队列从front开始到front+size(),为什么要+front?不能直接小于size()?
        //因为比如说循环队:3,5,6 初始化数据front=0 rear=3
        //那么取出数据3 此时front=1 rear=3 这时打印数据如果是直接小于size()
        //则指打印出1,2 无法打印出真正个数
        for (int i =front; i <front+size(); i++) {
            //为什么要i%maxSize  因为是环形,比如说3,5,6 初始化数据front=0 rear=3
            //此时取出数据3,5,此时front=2 rear=3,即添加数据4,1 此时front=2 rear=1
            //若i=2 此时i<5    5=2+(1 + 4 - 2) % 4;
            //若i不进行i%maxSize 则会在i++时无法回到环形头部 会++到front=5 数组越界爆出异常
            //所以需要i%maxSize回到环形头部
            System.out.printf("arr[%d]=%d\t", i % maxSize, arr[i % maxSize]);
        }
    }

    //求出当前队列有效数据的个数
    public int size() {
        //比如说环形队列空间=4 值=3,5,6
        //初始值front=0 rear=4
        //此时队列有效数据(4+3-0)%4=3 代表有效个数=3
        return (rear + maxSize - front) % maxSize;
    }
    //打印队列头部数据
    public int showheadQueue(){
        //判断队列是否为空
        if (isEmpty()) {
            throw new RuntimeException("队列为空,没有数据");
        }
        //直接返回front,因为front指向队列第一个元素
        return arr[front];
    }
}

那么现在让我们添加数据测试看看把

//创建一个队列
CircleArray arrayQueue = new CircleArray(4);

System.out.println("\n添加数据:10");
arrayQueue.addQueue(10);//添加一个数据10

System.out.println("\n打印队列数据----------------");
arrayQueue.showQueue();

运行结果如下:

添加数据:10

打印队列数据----------------
arr[0]=10

我们再加多点数据看看,并看看数组模拟环形队列有什么不一样?

System.out.println("\n添加数据:10");
arrayQueue.addQueue(10);//添加一个数据10

System.out.println("\n添加数据:20");
arrayQueue.addQueue(20);//添加一个数据20

System.out.println("\n添加数据:30");
arrayQueue.addQueue(30);//添加一个数据30

//打印头部数据
System.out.println("\n\n显示队列队首信息:"+arrayQueue.showheadQueue());

System.out.println("\n打印队列数据----------------");
arrayQueue.showQueue();

运行结果如下:
显示队列队首信息:10

打印队列数据----------------
arr[0]=10    arr[1]=20    arr[2]=30   

此时我们弹出队首再看看?

System.out.println("\n取出队列首----------------");
arrayQueue.getQueue();

System.out.println("\n打印队列数据----------------");
arrayQueue.showQueue();

运行结果如下:
取出队列首----------------

打印队列数据----------------
arr[1]=20    arr[2]=30    

此时我们能添加数据嘛?答案是可以的
它会加到哪呢?答案是:会加到下标3的位置,此时下标0就作为约定位置,因为这个约定的位置是会动态变化的!!!

System.out.println("\n添加数据:50");
arrayQueue.addQueue(50);//添加一个数据50

System.out.println("\n打印队列数据----------------");
arrayQueue.showQueue();

运行结果如下:
添加数据:50

打印队列数据----------------
arr[1]=20    arr[2]=30    arr[3]=50    

那么此时的数组即可反复利用,测试完成


本文链接: http://www.dtmao.cc/news_show_350323.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?