【Java数据结构和算法】003-稀疏数组和队列

冷不防 2023-10-05 12:49 84阅读 0赞

# **目录** #

一、稀疏数组sparsearray

1、一个实际的应用场景

编写的五子棋程序中，有存盘退出和续上盘的功能：

问题分析：

2、稀疏数组基本介绍

稀疏数组的处理方法：

3、稀疏数组案例

4、稀疏数组转换的思路

5、二维数组与稀疏数组互转

二维数组转稀疏数组思路分析：

稀疏数组转二维数组思路分析：

6、稀疏数组与二位数组互转代码实现

二维数组转稀疏数组：

稀疏数组转二维数组：

二、队列

1、队列的一个使用场景：银行排队

2、队列介绍

示意图：

3、数组模拟队列的思路分析

数组模拟队列：

思路分析：

代码演示：

运行结果：

4、数组模拟环形队列的思路分析

数组模拟环形队列：

分析说明：

图示：

代码演示：

运行结果：

--------------------

# 一、稀疏数组sparsearray #

## 1、一个实际的应用场景 ##

### 编写的五子棋程序中，有存盘退出和续上盘的功能： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70][]

### 问题分析： ###

因为该二维数组的很多值是默认值0, 因此记录了很多没有意义的数据，我们这个时候可以使用稀疏数组实现对二维数组的压缩；

## 2、稀疏数组基本介绍 ##

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组；

### 稀疏数组的处理方法： ###

①记录数组一共有几行几列，有多少个不同的值 把具有不同值的元素的行列及值；

②记录在一个小规模的数组（稀疏数组）中，从而缩小程序的规模；

## 3、稀疏数组案例 ##

（这个真不错，只是在对数组进行读写的时候需要额外的一步转换操作，这是值得的！）

//首元素 ：行数、列数、元素个数
    //其他元素：第几行、第几列、值是什么

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 1][]

## 4、稀疏数组转换的思路 ##

①使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)；

②把稀疏数组存盘，并且可以重新恢复原来的二维数组数；

③整体思路分析：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 2][]

## 5、二维数组与稀疏数组互转 ##

### 二维数组转稀疏数组思路分析： ###

第一步：遍历原二维数组，得到有效数据的个数sum（用来确定首元素的行、列、有效值数量）；

第二步：根据sum创建稀疏数组，行为sum+1行，列为3列；

第三步：将二位数组的有效数据，存到稀疏数组；

### 稀疏数组转二维数组思路分析： ###

第一步：根据稀疏数组的首元素确定二维数组的行、列和稀疏数组的长度；

第二步：根据已知的行列创建二维数组；

第三步：根据稀疏数组的长度遍历稀疏数组，确定二维数组的元素，赋值给二维数组；

## 6、稀疏数组与二位数组互转代码实现 ##

### 二维数组转稀疏数组： ###

**代码演示：**

package com.zb.ds;
    
    //二维数组转稀疏数组
    public class SparseArray {
        public static void main(String[] args) {
            //创建并初始化二维数组
            int[][] nums = new int[4][4];
            nums[0] = new int[]{0,0,0,0};
            nums[1] = new int[]{0,2,0,0};
            nums[2] = new int[]{0,0,7,0};
            nums[3] = new int[]{0,0,0,0};
            //将这个二维数组转换成稀疏数组
            //1、获得二维数组有效元素的个数
            int sum = 0;
            for (int[] num : nums) {
                for (int i : num) {
                    if (i != 0) {
                        //有效数据
                        sum++;
                    }
                }
            }
            //2、创建稀疏数组
            int[][] sparseArray = new int[sum+1][3];
            //3、将二维数组的有效元素存到稀疏数组
            //首元素
            sparseArray[0] = new int[]{nums.length,nums[0].length,sum};
            int sNum = 0;
            //其他元素
            for (int i = 0; i < nums.length; i++) {
                for (int j = 0; j < nums[i].length; j++) {
                    if(nums[i][j]!=0){
                        sNum++;
                        sparseArray[sNum] = new int[]{i,j,nums[i][j]};
                    }
                }
            }
            //输出二维数组
            System.out.println("二维数组：");
            for (int[] num : nums) {
                for (int i : num) {
                    System.out.print(i + " ");
                }
                System.out.println();
            }
            //输出稀疏数组
            System.out.println("稀疏数组：");
            for (int[] ints : sparseArray) {
                for (int anInt : ints) {
                    System.out.print(anInt + " ");
                }
                System.out.println();
            }
        }
    }

**运行结果：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 3][]

### 稀疏数组转二维数组： ###

**代码演示：**

package com.zb.ds;
    
    //二维数组转稀疏数组
    public class SparseArray {
        public static void main(String[] args) {
            //创建并初始化二维数组
            int[][] nums = new int[4][4];
            nums[0] = new int[]{0,0,0,0};
            nums[1] = new int[]{0,2,0,0};
            nums[2] = new int[]{0,0,7,0};
            nums[3] = new int[]{0,0,0,0};
            //将这个二维数组转换成稀疏数组
            //1、获得二维数组有效元素的个数
            int sum = 0;
            for (int[] num : nums) {
                for (int i : num) {
                    if (i != 0) {
                        //有效数据
                        sum++;
                    }
                }
            }
            //2、创建稀疏数组
            int[][] sparseArray = new int[sum+1][3];
            //3、将二维数组的有效元素存到稀疏数组
            //首元素
            sparseArray[0] = new int[]{nums.length,nums[0].length,sum};
            int sNum = 0;
            //其他元素
            for (int i = 0; i < nums.length; i++) {
                for (int j = 0; j < nums[i].length; j++) {
                    if(nums[i][j]!=0){
                        sNum++;
                        sparseArray[sNum] = new int[]{i,j,nums[i][j]};
                    }
                }
            }
            //好的，上面已经将二维数组转化成稀疏数组了，我们就利用这个稀疏数组来演示稀疏数组转化成二维数组的操作
            //1、通过稀疏数组的第一行元素，创建二维数组
            int[][] nums1 = new int[sparseArray[0][0]][sparseArray[0][1]];
            //2、遍历稀疏数组，将对应的值存入二维数组
            for (int i = 1; i < sparseArray.length; i++) {
                nums1[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
            }
            //输出二维数组
            System.out.println("二维数组：");
            for (int[] num : nums) {
                for (int i : num) {
                    System.out.print(i + " ");
                }
                System.out.println();
            }
            //输出稀疏数组
            System.out.println("稀疏数组：");
            for (int[] ints : sparseArray) {
                for (int anInt : ints) {
                    System.out.print(anInt + " ");
                }
                System.out.println();
            }
            //再次输出二维数组
            System.out.println("二维数组：");
            for (int[] num : nums1) {
                for (int i : num) {
                    System.out.print(i + " ");
                }
                System.out.println();
            }
        }
    }

**运行结果：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 4][]

# 二、队列 #

## 1、队列的一个使用场景：银行排队 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 5][]

## 2、队列介绍 ##

①队列是一个**有序列表**，可以用**数组**或是**链表**来实现；

②遵循**先入先出**的原则；

### 示意图： ###

(使用数组模拟队列示意图：空——>添加数据——>取出数据)

添加数据是在队列的尾部添加，取数据是在队列的首部取，也即是**先入先出**；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 6][]

## 3、数组模拟队列的思路分析 ##

### 数组模拟队列： ###

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

因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 7][]

### 思路分析： ###

当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：

第一步：将尾指针往后移：rear+1 , 当front == rear 【空】（判断当前队列是否是空队列，如果是就没办法存入）；

第二步：若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。 rear == maxSize - 1\[队列满\]（如果但钱队列已经满了，那也无法存入数据）；

### 代码演示： ###

package com.zb.ds;
    
    //数组模拟队列
    public class ArrayQueue {
        public static void main(String[] args) {
            //创建队列
            ArrayQ q = new ArrayQ(3);
            //判断队列是否为空
            System.out.println(q.isEmpty());
            //添加元素到队列
            q.addQueue(100);
            q.addQueue(99);
            q.addQueue(1000);
            //判断队列是否满
            System.out.println(q.isFull());
            //取出一个元素
            System.out.println(q.getQueue());
            //偷窥首元素：首元素从100变成了99，因为上面已经把100取出来了！
            System.out.println(q.headQueue());
            //显示队列所有元素
            q.show();
            //再添加一个元素
            q.addQueue(101);
            //再取三个元素
            System.out.println(q.getQueue());
            System.out.println(q.getQueue());
            System.out.println(q.getQueue());
    
        }
    }
    class ArrayQ{
        private final int maxSize;//数组最大容量
        private int front;//队首
        private int rear;//队尾
        private final int[] arr;//数组
    
        //队列的构造器
        public ArrayQ(int maxSize) {
            this.maxSize = maxSize;
            arr = new int[maxSize];
            front = -1;//队首前面那个下标
            rear = -1;//队尾下标
        }
    
        //判断队列是否满
        public boolean isFull(){
            return rear == maxSize-1;
        }
    
        //判断队列是否空
        public boolean isEmpty(){
            return front == rear;
        }
    
        //添加数据到队列
        public void addQueue(int num){
            //判断队列是否满
            if(isFull()){
                //队列满了
                System.out.println("添加数据失败，队列满了！");
                return;
            }
            rear++;
            arr[rear] = num;
        }
    
        //从队列取出数据
        public int getQueue(){
            //判断是否为空
            if(isEmpty()){
                throw new RuntimeException("队列为空！");
            }
            front++;
            return arr[front];
        }
    
        //显示队列的所有数据
        public void show(){
            //遍历
            if(isEmpty()){
                System.out.println("队列为空！");
                return;
            }
            for (int value : arr) {
                System.out.println(value);
            }
        }
    
        //显示队列头数据
        public int headQueue(){
            if(isEmpty()){
                throw new RuntimeException("队列为空！");
            }
            return arr[front+1];
        }
    
    }

### 运行结果： ###

true
    true
    100
    99
    100
    99
    1000
    添加数据失败，队列满了！
    99
    1000
    Exception in thread "main" java.lang.RuntimeException: 队列为空！
    	at com.zb.ds.ArrayQ.getQueue(ArrayQueue.java:71)
    	at com.zb.ds.ArrayQueue.main(ArrayQueue.java:27)

## 4、数组模拟环形队列的思路分析 ##

### 数组模拟环形队列： ###

前面的数组模拟队列里面的数组只用了一次，很浪费，数组模拟环形队列是对前面的数组模拟队列的优化，充分利用数组. 因此将数组看做是一个环形的(通过取模的方 式来实现即可)；

### 分析说明： ###

①尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定，这个在做判断队列满的 时候需要注意 (rear + 1) % maxSize == front+1 \[满\]（**这个要在非空的基础上才成立，如果为空直接返回false**）；

②rear == front \[空\]；

③front和rear默认为-1，front为队首元素的前一个下标，rear为队尾元素下标；

### 图示： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 8][]

### 代码演示： ###

（我们在之前代码的基础上进行修改，被坑了，但还是解决了！）

package com.zb.ds;
    
    //数组模拟队列
    public class ArrayQueue {
        public static void main(String[] args) {
            //创建队列
            ArrayQ q = new ArrayQ(3);
            //判断队列是否为空
            System.out.println(q.isEmpty());
            //添加元素到队列
            System.out.println("添加一个元素：100");
            q.addQueue(100);
            System.out.println("添加一个元素：99");
            q.addQueue(99);
            System.out.println("添加一个元素：1000");
            q.addQueue(1000);
            System.out.println("添加一个元素：2000，这个时候会添加失败，因为满了！");
            q.addQueue(2000);
            //判断队列是否满
            System.out.println("这个时候该满了：" + q.isFull());
            //取出一个元素
            System.out.println("取出一个元素：" + q.getQueue());
            //偷窥首元素：首元素从100变成了99，因为上面已经把100取出来了！
            System.out.println("偷窥首元素：" + q.headQueue());
            //显示队列所有元素
            System.out.println("显示队列所有元素：");
            q.show();
            //再添加一个元素
            System.out.println("再添加一个元素：101");
            q.addQueue(101);
            //显示队列所有元素
            System.out.println("显示队列所有元素：");
            q.show();
            //这个时候是满的了
            System.out.println("这个时候是满的了：" + q.isFull());
            //再取三个元素
            System.out.println("再取一个元素：" + q.getQueue());
            //此时队列中有效数据的个数
            System.out.println("此时队列中有效数据的个数为：" + q.getVDN());
            System.out.println("再取一个元素：" + q.getQueue());
            System.out.println("再取一个元素：" + q.getQueue());
            System.out.println("再取一个元素：这个时候会取失败，因为空了");
            System.out.println(q.getQueue());
            //这个时候是空的了
            System.out.println("这个时候是空的了：" + q.isEmpty());
    
        }
    }
    class ArrayQ{
        private final int maxSize;//数组最大容量
        private int front;//队首
        private int rear;//队尾
        private boolean next;//rear领先front1圈
        private final int[] arr;//数组
    
        //队列的构造器
        public ArrayQ(int maxSize) {
            this.maxSize = maxSize;
            arr = new int[maxSize];
            front = -1;//队首前面那个下标
            rear = -1;//队尾下标
            next = false;
        }
    
        //判断队列是否满
        public boolean isFull(){
            if(front==-1 && rear==2){
                return true;
            }
            return front == rear && next;
        }
    
        //判断队列是否空
        public boolean isEmpty(){
            if(front==-1 && rear==-1){
                return true;
            }
            return front == rear && !next;
        }
    
        //添加数据到队列
        public void addQueue(int num){
            //判断队列是否满
            if(isFull()){
                //队列满了
                System.out.println("添加数据失败，队列满了！");
                return;
            }
            //如果队尾是2了，还要往后面+1，就理解为已经在下一圈了
            if(rear==2){
                next = true;
            }
            rear++;
            rear%=maxSize;
            arr[rear] = num;
        }
    
        //从队列取出数据
        public int getQueue(){
            //判断是否为空
            if(isEmpty()){
                throw new RuntimeException("getQueue队列为空！front：" + front + "；rear：" + rear);
            }
            //如果此时front是2了，还要往后取，就认为这一圈追平了
            if(front==2){
                next = false;
            }
            front++;
            front%=maxSize;
            return arr[front];
        }
    
        //显示队列的所有数据
        public void show(){
            //遍历
            if(isEmpty()){
                System.out.println("队列为空！front：" + front + "；rear：" + rear);
                return;
            }
            for (int value : arr) {
                System.out.println(value);
            }
        }
    
        //显示队列头数据
        public int headQueue(){
            if(isEmpty()){
                throw new RuntimeException("headQueue队列为空！front：" + front + "；rear：" + rear);
            }
            return arr[front+1];
        }
    
        //获取有效数据的个数
        public int getVDN(){
            return (rear+maxSize-front)%maxSize;
        }
    
    }

### 运行结果： ###

true
    添加一个元素：100
    添加一个元素：99
    添加一个元素：1000
    添加一个元素：2000，这个时候会添加失败，因为满了！
    添加数据失败，队列满了！
    这个时候该满了：true
    取出一个元素：100
    偷窥首元素：99
    显示队列所有元素：
    100
    99
    1000
    再添加一个元素：101
    显示队列所有元素：
    101
    99
    1000
    这个时候是满的了：true
    再取一个元素：99
    此时队列中有效数据的个数为：2
    再取一个元素：1000
    再取一个元素：101
    再取一个元素：这个时候会取失败，因为空了
    Exception in thread "main" java.lang.RuntimeException: getQueue队列为空！front：0；rear：0
    	at com.zb.ds.ArrayQ.getQueue(ArrayQueue.java:102)
    	at com.zb.ds.ArrayQueue.main(ArrayQueue.java:43)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201029172349956.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020102917282196.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201030100227700.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201030104842444.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201030105520503.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201030144040716.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201030144232762.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20201030144936168.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20201031081924941.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70