01、数据结构与算法 - 实战：稀疏数组和队列
1、稀疏数组（SparseArray）
1.1 需求场景
存在一个黑白棋盘，需要对棋盘数据进行存储和读取。
粗暴的解决方案：把棋盘看成是一个二维数组。
存在的问题：该二维数组存在大量的默认值0，因此记录了很多没有意义的数据。
比较优雅的解决方案：使用稀疏数组对棋盘数组进行压缩。
1.2 基本介绍
当一个数组中大部分元素为默认值时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是：
1、记录数组的行列数和不同取值数目；
2、把具有不同值的元素的行列以及取值记录在一个小规模的数组张，从而压缩信息；
1.3 应用实例
1、使用稀疏数组，保存前面的二维棋盘数组；
2、把稀疏数组还原成棋盘数组。
1.4 稀疏数组工具类
package cn.klb.datastructures.sparsearray;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description: 稀疏矩阵的使用
* @Date: Create in 2023/3/29 17:29
* @Modified By:
*/
public class SparseArray {
/**
* 将棋盘数组转为稀疏数组
*
* @param chessArray
* @return
*/
public static int[][] chessToSparse(int[][] chessArray) {
// 获取原数组有效数字个数
int valueNums = 0;
for (int[] ints : chessArray) {
for (int i : ints) {
if (i != 0) {
valueNums++;
}
}
}
// 获取原数组的维数
int row = chessArray.length;
int col = chessArray[0].length;
// 定义初始化的稀疏数组
int[][] sparseArray = new int[valueNums + 1][3];
// 给稀疏数组赋值
sparseArray[0][0] = row;
sparseArray[0][1] = col;
sparseArray[0][2] = valueNums;
int index = 1;
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (chessArray[i][j] != 0) {
sparseArray[index][0] = i;
sparseArray[index][1] = j;
sparseArray[index][2] = chessArray[i][j];
index++;
}
}
}
return sparseArray;
}
/**
* 将稀疏数组还原成棋盘数组
*
* @param sparseArray
* @return
*/
public static int[][] sparseToChess(int[][] sparseArray) {
// 定义并初始化一个原生数组
int[][] cheeseArray = new int[sparseArray[0][0]][sparseArray[0][1]];
for (int i = 1; i < sparseArray.length; i++) {
cheeseArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
return cheeseArray;
}
/**
* 打印数组
*
* @param array
*/
public static void showArray(int[][] array) {
for (int[] ints : array) {
for (int i : ints) {
System.out.print(i + " ");
}
System.out.println();
}
}
}
1.5 测试类
package cn.klb.test.datastructurestest;
import cn.klb.datastructures.sparsearray.SparseArray;
import org.junit.Test;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description:
* @Date: Create in 2023/4/1 13:15
* @Modified By:
*/
public class SparseArrayTest {
@Test
public void testSparseArray(){
/*
创建一个棋盘二维数组 12 × 12
1 代表黑子；2代表白子
*/
int chessArr1[][] = new int[12][12];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
// 打印棋盘数组
System.out.println("-----棋盘数组1--------");
SparseArray.showArray(chessArr1);
System.out.println("-----稀疏矩阵-------");
int[][] sparseArr = SparseArray.chessToSparse(chessArr1);
SparseArray.showArray(sparseArr);
// 打印棋盘数组
System.out.println("-----棋盘数组2--------");
int[][] chessArr2 = SparseArray.sparseToChess(sparseArr);
SparseArray.showArray(chessArr2);
}
}
2、队列（Queue）
2.1 需求场景
银行排队的案例：先拿到号的人先办理业务，后拿到号的人后办理业务。
2.2 基本介绍
1、队列是一个有序列表，可以用数组或者链表来实现；
2、队列遵循“先入先出”的原则；
3、示意图：
说明：front表示队列的首位指针，rear表示队列的末位指针，初始状态front=rear=-1。没添加一个元素，rear+1；每移除一个元素，front+1，抛弃前面的一个元素。
2.3 使用数组实现队列思路
1、队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中maxSize是该队列的最大容量；
2、因为队列的输出、输入是分别从队列的首尾来处理，因此需要两个变量front以及rear分别记录队列的首位和末位的下表，front会随着队列数据的移除而改变，rear会随着队列数据的增加而改变，如图所示：
3、末尾索引rear的下一个为头索引front时表示队列满了，即这里使用队列的一个容量空出来作为约定。此时判断队列满的依据是：( rear + 1 ) % maxSize == front；
4、判断队列为空的依据：rear == front;
5、队列的有效数据个数为：(rear + maxSize - front) % maxSize
2.4 代码实现
2.4.1 数组模拟的队列类
package cn.klb.datastructures.queue;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description:使用数组模拟队列
* @Date: Create in 2023/3/29 19:47
* @Modified By:
*/
public class ArrayQueue {
private int maxSize; // 表示数组的最大容量
private int front; // 指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素
private int rear; // 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定
private int[] arr; // 用于存放队列的数据, 模拟队列
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
}
/**
* 判断队列是否满
*
* @return
*/
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
/**
* 判断队列是否为空
*
* @return
*/
public boolean isEmpty() {
return rear == front;
}
/**
* 添加数据到队列
*
* @param n
*/
public void add(int n) {
// 判断队列是已满
if (isFull()) {
System.out.println("队列满，不能加入数据~");
return;
}
//直接将数据加入
arr[rear] = n;
//将 rear 后移, 这里必须考虑取模
rear = (rear + 1) % maxSize;
}
/**
* 数据出列
*
* @return
*/
public int getQueue() {
// 判断队列是否空
if (isEmpty()) {
// 通过抛出异常
throw new RuntimeException("队列空，不能取数据");
}
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.print(arr[i % maxSize] + " ");
}
System.out.println();
}
// 求出当前队列有效数据的个数
public int size() {
return (rear + maxSize - front) % maxSize;
}
}
2.4.2 测试类
package cn.klb.test.datastructurestest;
import cn.klb.datastructures.queue.ArrayQueue;
import org.junit.Test;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description:
* @Date: Create in 2023/3/31 12:55
* @Modified By:
*/
public class ArrayQueueTest {
@Test
public void arrayQueueTest() {
ArrayQueue arrayQueue = new ArrayQueue(5);
System.out.println("-----添加：0 1 2-----");
arrayQueue.add(0);
arrayQueue.add(1);
arrayQueue.add(2);
arrayQueue.showQueue();
System.out.println("-----一位出队-----");
System.out.println("出列数字：" + arrayQueue.getQueue());
arrayQueue.showQueue();
System.out.println("-----添加：7 8-----");
arrayQueue.add(7);
arrayQueue.add(8);
arrayQueue.showQueue();
}
}