[数据结构与算法-01]稀疏数组和队列
本文共 6346 字，大约阅读时间需要 21 分钟。
文章目录
1、稀疏数组（SparseArray）
1.1 需求场景
存在一个黑白棋盘，需要对棋盘数据进行存储和读取。
粗暴的解决方案：把棋盘看成是一个二维数组。 存在的问题：该二维数组存在大量的默认值0，因此记录了很多没有意义的数据。 比较优雅的解决方案：使用稀疏数组对棋盘数组进行压缩。 1.2 基本介绍
当一个数组中大部分元素为默认值时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是： 1、记录数组的行列数和不同取值数目； 2、把具有不同值的元素的行列以及取值记录在一个小规模的数组张，从而压缩信息；1.3 应用实例
1、使用稀疏数组，保存前面的二维棋盘数组；
2、把稀疏数组还原成棋盘数组。1.4 稀疏数组工具类
package cn.klb.datastructures.sparsearray;/** * @Author: Konglibin * @Description: 稀疏矩阵的使用 * @Date: Create in 2020/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: Konglibin * @Description: * @Date: Create in 2020/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: Konglibin * @Description:使用数组模拟队列 * @Date: Create in 2020/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: Konglibin * @Description: * @Date: Create in 2020/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(); }} 转载地址：http://zbv.baihongyu.com/
你可能感兴趣的文章