2.稀疏数组和队列 ================ 2.1.稀疏 sparsearray 数组 ------------------------- 2.1.1.基本介绍 ~~~~~~~~~~~~~~ 当一个数组中大部分元素为０，或者为同一个数值时，可以使用稀疏数组来保存该数组。 稀疏数组的处理方法是: \* 记录数组一共有几行几列，有多少个不同的值 \* 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模 2.1.2.实际需求 ~~~~~~~~~~~~~~ .. image:: _static/2.稀疏数组与队列/2.1.1_1.png 2.1.3.应用案例 ~~~~~~~~~~~~~~ 1. 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等) 2. 把稀疏数组存盘，并且可以从新恢复原来的二维数组数 3. 整体思路分析 4. 代码实现 .. code:: java package com.tuling.sparse; /** * * @ClassName SparseDemo * @Description 稀疏数组 * @Author 北京图灵学院 */ public class SparseDemo { public static void main(String[] args) { // ------------------- 1、准备原始数据 ------------------- int sourceArray[][] = new int[9][7]; sourceArray[1][1] = 23; sourceArray[2][6] = 8; sourceArray[2][2] = 11; sourceArray[4][3] = 14; sourceArray[4][6] = 76; sourceArray[5][4] = 44; sourceArray[6][0] = 43; sourceArray[8][5] = 32; System.out.println("原始的二维数组为:"); for (int[] row : sourceArray) { for (int data : row) { System.out.print(data + "\t"); } System.out.println(); } System.out.println(); System.out.println(); // ------------------- 2、将原始二维数组用稀疏数组存储 ------------------- int[][] sparseArray = arrayToSparse(sourceArray); System.out.println("转换后的稀疏数组为："); for (int[] row : sparseArray) { for (int data : row) { System.out.print(data + "\t"); } System.out.println(); } System.out.println(); System.out.println(); // ------------------- 3、将稀疏数组还原为二维数组 ------------------- int[][] sourceArr2 = sparseToArray(sparseArray); System.out.println("还原后的二维数组为："); for (int[] row : sourceArr2) { for (int data : row) { System.out.print(data + "\t"); } System.out.println(); } } /** * 将原始二维数组转换为稀疏数组 * 思路： * 1、先遍历原始的二维数组，获取到有效数据的个数 * 2、根据有效数据的个数，创建对应的稀疏数组。 int sparse[][] = new int[sum+1][3] * 3、遍历原始二维数组，将有效数据存入到稀疏数组中。 * @param sourceArray * @return */ public static int[][] arrayToSparse(int[][] sourceArray){ //定义一个变量，记录有效数据个数 int sum = 0; //1、遍历原始二维数组，获取有效数据个数 for (int i = 0; i < sourceArray.length; i++) { for (int j = 0; j < sourceArray[i].length; j++) { if(sourceArray[i][j] != 0) { //条件成立，说明该位置为有效数据。 sum++; } } } //2.根据有效数据的个数，创建对应的稀疏数组。 int sparseArr[][] = new int[sum+1][3]; //为稀疏数组的第一行赋值 sparseArr[0][0] = sourceArray.length; sparseArr[0][1] = sourceArray[0].length; sparseArr[0][2] = sum; //3.遍历原始二维数组，将有效数据存入到稀疏数组中。 //定义一个变量，记录当前为稀疏数组的第几行。 int count = 0; for (int i = 0; i < sourceArray.length; i++) { for (int j = 0; j < sourceArray[i].length; j++) { if(sourceArray[i][j] != 0) { count++; sparseArr[count][0] = i; sparseArr[count][1] = j; sparseArr[count][2] = sourceArray[i][j]; } } } return sparseArr; } /** * 将稀疏数组还原为原始二维数组 * 思路： * 1、根据稀疏数组第一行的数据值，创建二维数组 * 2、遍历稀疏数组，将数据插入到二维数组中。 * 3、return * @param sparseArr * @return */ public static int[][] sparseToArray(int[][] sparseArr){ //根据稀疏数组的第一行，创建二维数组 //sparseArr[0][0] //sparseArr[0][1] int sourceArr[][] = new int[sparseArr[0][0]][sparseArr[0][1]]; //2.从 1 下标位置开始遍历稀疏数组，将数据插入到二维数组中。 for (int i = 1; i < sparseArr.length; i++) { for (int j = 0; j < sparseArr[i].length; j++) { sourceArr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][j]; } } return sourceArr; } } 2.2.队列 -------- 2.2.1.队列的介绍 ~~~~~~~~~~~~~~~~ 队列以一种先入先出（FIFO）的线性表，还有一种先入后出的线性表（FILO）叫做栈。 教科书上有明确的定义与描述。类似于现实中排队时的队列（队尾进，队头出），队列只在线性表两端进行操作，插入元素的一端称为表尾，删除（取出）元素的一端称为表头。分别对应于 入队和出队操作。 存储结构： \* 线性存储结构，称为顺序队列，使用数组实现 \* 链式存储结构，称为链队，使用链表实现。 2.2.1.1.图解入队操作 ^^^^^^^^^^^^^^^^^^^^ .. image:: _static/2.稀疏数组与队列/2.2.1.1_1.png .. image:: _static/2.稀疏数组与队列/2.2.1.1_2.png .. image:: _static/2.稀疏数组与队列/2.2.1.1_3.png .. image:: _static/2.稀疏数组与队列/2.2.1.1_4.png .. image:: _static/2.稀疏数组与队列/2.2.1.1_5.png .. image:: _static/2.稀疏数组与队列/2.2.1.1_6.png 2.2.1.2.图解出队操作 ^^^^^^^^^^^^^^^^^^^^ .. image:: _static/2.稀疏数组与队列/2.2.1.2_1.png .. image:: _static/2.稀疏数组与队列/2.2.1.2_2.png .. image:: _static/2.稀疏数组与队列/2.2.1.2_3.png .. image:: _static/2.稀疏数组与队列/2.2.1.2_4.png 2.2.2.队列的使用场景 ~~~~~~~~~~~~~~~~~~~~ 2.2.3.数组模拟顺序队列 ~~~~~~~~~~~~~~~~~~~~~~ 代码实现： .. code:: java /** * All rights Reserved, Designed By https://www.tulingxueyuan.com/ * @Title: ArrayQueue.java * @Package com.tuling.queue * @Description: * @author: 北京图灵学院 * @date: 2019年11月13日 下午12:22:03 * @version V1.0 * @Copyright: */ package com.tuling.queue; /** * @ClassName ArrayQueue * @Description * @Author 北京图灵学院 */ public class ArrayQueue { //该数组用来模拟队列，存储数据 private Integer[] arr; //该变量用来指向队列头 private int front; //该变量用来指向队列尾 private int rear; /** * * @param queueSize:队列的初始容量 */ public ArrayQueue(int queueSize) { if(queueSize < 0) { throw new IllegalArgumentException("初始化容量不能小于0！"); } arr = new Integer[queueSize]; front = 0; rear = 0; } /** * * @Title: addQueue * @Description: 入队操作 * 1、判断队列是否已满 * 2、如果队列未满，队列头不变，想队列尾下标位置插入数据，同时，尾指针 + 1 * @param: num * @return: void * @throws */ public void addQueue(int num) { if(isFull()) { throw new IllegalArgumentException("队列已满！"); } //执行到这里，说明队列未满，可以入队操作。 arr[rear] = num; //注意：记得尾指针 + 1 rear++; } /** * * @Title: isFull * @Description:判断队列是否已满 * @param: * @return: boolean * @throws */ public boolean isFull() { return rear == arr.length; } /** * * @Title: getQueue * @Description:出队操作 * 1、先判断一下当前队列是否为空 * 2、出队操作的是头指针，出队一个元素，队列头+1 * @param: * @return: int * @throws */ public int getQueue() { if(isEmpty()) { throw new IllegalArgumentException("队列为空！"); } return arr[front++]; } /** * * @Title: showHead * @Description:显示当前队列的队列头，不执行出队操作。 * @param: * @return: void * @throws */ public void showHead() { if(isEmpty()) { throw new IllegalArgumentException("队列为空！"); } System.out.println("当前队列的队列头为：" + arr[front]); } /** * * @Title: show * @Description:显示队列中的所有数据 * @param: * @return: void * @throws */ public void show() { //先判断一下队列是否为空！ if(isEmpty()) { throw new IllegalArgumentException("队列为空！"); } for(int i = front; i < rear; i++) { System.out.println(i + " --> " + arr[i]); } } /** * * @Title: isEmpty * @Description:判断当前队列是否为空。 * @param: * @return: boolean * @throws */ public boolean isEmpty() { return front == rear; } } 测试代码如下： .. code:: java /** * All rights Reserved, Designed By https://www.tulingxueyuan.com/ * @Title: ArrayQueueDemo.java * @Package com.tuling.queue * @Description: * @author: 北京图灵学院 * @date: 2019年11月13日 下午12:31:17 * @version V1.0 * @Copyright: */ package com.tuling.queue; /** * @ClassName ArrayQueueDemo * @Description * @Author 北京图灵学院 */ public class ArrayQueueDemo { /** * @Title: main * @Description: * @param: args * @return: void * @throws */ public static void main(String[] args) { ArrayQueue aq = new ArrayQueue(5); System.out.println("------------------------1、入队操作------------------------"); aq.addQueue(5); aq.addQueue(8); aq.addQueue(7); aq.addQueue(2); aq.addQueue(9); // aq.addQueue(92); aq.show(); System.out.println("------------------------2、出队操作------------------------"); System.out.println("出队：" + aq.getQueue()); aq.showHead(); System.out.println("出队：" + aq.getQueue()); aq.showHead(); System.out.println("出队：" + aq.getQueue()); aq.showHead(); System.out.println("出队：" + aq.getQueue()); aq.showHead(); System.out.println("出队：" + aq.getQueue()); aq.showHead(); } } 2.2.4.顺序队列的溢出现象 ~~~~~~~~~~~~~~~~~~~~~~~~ - **"下溢"**\ 现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。 - **"真上溢"**\ 现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。 - **"假上溢"**\ 现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远 远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。 2.2.5.数组模拟环形队列 ~~~~~~~~~~~~~~~~~~~~~~ 为了解决顺序队列中“假上溢”的现象，同时更好的利用内存空间，我们将其实现为环形队列。 2.2.5.1.理解环形队列 ^^^^^^^^^^^^^^^^^^^^ 首先我们要说明的是循环队列仍然是基于数组实现的。但是为了形象化的说明问题，我们如下图所示 .. image:: _static/2.稀疏数组与队列/2.2.5_1.png 1. 图中有两个指针(其实就是两个整数型变量，因为在这里有指示作用，所以这里理解为指针)front、rear,一个指示队头，一个指示队尾。 2. rear和front互相追赶着，这个追赶过程就是队列添加和删除的过程，如果rear追到head说明队列满了，如果front追到rear说明队列为空。 3. 我们把它掰弯，用的是求余，这样两个值就不会跑出最大范围，并且可以实现弯曲的效果，所以说对于循环队列我们必须给定最大值。这其实是我们臆想的，我们要做的就是利用循环来解决空间浪费的问题。 2.2.5.2.环形队列的实现过程 ^^^^^^^^^^^^^^^^^^^^^^^^^^ - 当添加一个元素时,(rear+1)%MAXQSIZE; //理解为什么求余？ - 当删除一个元素时,(front+1)%MAXQSIZE；//理解为什么求余？ - 当rear=front的时候，队列可能是满，也可能是空。 - 因为存在满和空两种情况，我们需要分别判断： - 满：当队列添加元素到rear的下一个元素是head的时候，也就是转圈子要碰头了，我们就认为队列满了。(rear+1)%MAXSIZE=Q.front - 空：当队列删除元素到head=rear的时候，我们认为队列空了。rear==front,不一定为0 2.2.5.3.环形队列代码实现 ^^^^^^^^^^^^^^^^^^^^^^^^ CircularQueue.java 类代码如下： .. code:: java /** * All rights Reserved, Designed By https://www.tulingxueyuan.com/ * @Title: CircularQueue.java * @Package com.tuling.circular * @Description: * @author: 北京图灵学院 * @date: 2019年11月13日 下午5:13:16 * @version V1.0 * @Copyright: */ package com.tuling.circular; /** * @ClassName CircularQueue * @Description * @Author 北京图灵学院 */ public class CircularQueue { //该数组模拟环形队列，存储数据 private Integer[] arr; //该变量指向队头 private int front; //该变量指向队尾 private int rear; //该变量表示当前队列的最大容量 private int maxSize; //该变量表示当前队列有效数据的个数 private int elementCount; /** * * @param queueSize:队列的初始容量 */ public CircularQueue(int queueSize) { if(queueSize < 0) { throw new IllegalArgumentException("初始化容量不能小于0！"); } arr = new Integer[queueSize]; maxSize = queueSize; front = 0; rear = 0; elementCount=0; } /** * * @Title: addQueue * @Description:入队操作 * 思路： * 1、判断队列是否已满 * 2、向队尾插入数据 * 3、将有效数据的个数 + 1 * @param: num * @return: void * @throws */ public void addQueue(int num) { if(isFull()) { throw new IllegalArgumentException("队列已满！"); } //队列未满，可以继续入队操作 //想队尾插入数据 arr[rear] = num; //移动尾指针 rear = (rear + 1) % maxSize; elementCount+=1; } /** * * @Title: isFull * @Description:判断当前队列是否已满 * 判满条件： * 1、空出一个元素位置，区别队列判空的条件 * 2、保证队尾指针的范围在数组下标范围内，解决方案：对Maxsize取余 * (rear + 1) % maxSize == front * @param: * @return: boolean * @throws */ public boolean isFull() { return (rear + 1) % maxSize == front; } /** * * @Title: showQueue * @Description:显示队列当中的所有数据 * @param: * @return: void * @throws */ public void showQueue() { if(isEmpty()) { throw new IllegalArgumentException("队列为空！"); } for(int i = front; i < (front+elementCount);i++) { System.out.println((i%maxSize) + " --> " + arr[i%maxSize]); } } /** * * @Title: isEmpty * @Description:判断当前队列是否为空 * @param: * @return: boolean * @throws */ public boolean isEmpty() { return front == rear; } /** * * @Title: getQueue * @Description: 出队操作 * 思路：出队需要操作队头后移，还需要注意队头的值范围。 * 1、先用一个临时变量存储当前队头 * 2、将队头后移 * front = (front + 1) % maxSize * 3、将有效数据个数 -1 * 4、return * @param: * @return: int * @throws */ public int getQueue() { if(isEmpty()) { throw new IllegalArgumentException("队列为空！"); } int tempHead = arr[front]; front = (front + 1) % maxSize; elementCount-=1; return tempHead; } /** * * @Title: showHead * @Description:显示当前队列头，不进行出队操作 * @param: * @return: void * @throws */ public void showHead() { if(isEmpty()) { throw new IllegalArgumentException("队列为空！"); } System.out.println("当前队列的队列头为：" + front + " --> " + arr[front]); } } 测试代码如下： .. code:: java /** * All rights Reserved, Designed By https://www.tulingxueyuan.com/ * @Title: CircularQueueDemo.java * @Package com.tuling.circular * @Description: * @author: 北京图灵学院 * @date: 2019年11月13日 下午5:30:43 * @version V1.0 * @Copyright: */ package com.tuling.circular; /** * @ClassName CircularQueueDemo * @Description * @Author 北京图灵学院 */ public class CircularQueueDemo { /** * @Title: main * @Description: * @param: @param args * @return: void * @throws */ public static void main(String[] args) { CircularQueue cq = new CircularQueue(5); System.out.println("--------------------------1.入队操作-----------------------------"); cq.addQueue(5); cq.addQueue(8); cq.addQueue(7); cq.addQueue(2); // cq.addQueue(9); cq.showQueue(); System.out.println("--------------------------2.入队操作-----------------------------"); System.out.println("出队：" + cq.getQueue()); cq.showHead(); System.out.println("出队：" + cq.getQueue()); cq.showHead(); System.out.println("出队：" + cq.getQueue()); cq.showHead(); System.out.println("出队：" + cq.getQueue()); System.out.println("--------------------------3.入队操作-----------------------------"); cq.addQueue(5); cq.addQueue(8); cq.addQueue(7); cq.addQueue(2); cq.showQueue(); } }