1. 2.稀疏数组和队列¶
1.1. 2.1.稀疏 sparsearray 数组¶
1.1.1. 2.1.1.基本介绍¶
当一个数组中大部分元素为０，或者为同一个数值时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是: * 记录数组一共有几行几列，有多少个不同的值 * 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
1.1.2. 2.1.2.实际需求¶
1.1.3. 2.1.3.应用案例¶
- 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
- 把稀疏数组存盘，并且可以从新恢复原来的二维数组数
- 整体思路分析
- 代码实现
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;
}
}
1.2. 2.2.队列¶
1.2.1. 2.2.1.队列的介绍¶
队列以一种先入先出（FIFO）的线性表，还有一种先入后出的线性表（FILO）叫做栈。 教科书上有明确的定义与描述。类似于现实中排队时的队列（队尾进，队头出），队列只在线性表两端进行操作，插入元素的一端称为表尾，删除（取出）元素的一端称为表头。分别对应于 入队和出队操作。
存储结构： * 线性存储结构，称为顺序队列，使用数组实现 * 链式存储结构，称为链队，使用链表实现。
1.2.2. 2.2.2.队列的使用场景¶
1.2.3. 2.2.3.数组模拟顺序队列¶
代码实现：
/**
* 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;
}
}
测试代码如下：
/**
* 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();
}
}
1.2.4. 2.2.4.顺序队列的溢出现象¶
- “下溢”现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
- “真上溢”现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
- “假上溢”现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远 远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为”假上溢”现象。
1.2.5. 2.2.5.数组模拟环形队列¶
为了解决顺序队列中“假上溢”的现象，同时更好的利用内存空间，我们将其实现为环形队列。
1.2.5.1. 2.2.5.1.理解环形队列¶
首先我们要说明的是循环队列仍然是基于数组实现的。但是为了形象化的说明问题，我们如下图所示
- 图中有两个指针(其实就是两个整数型变量，因为在这里有指示作用，所以这里理解为指针)front、rear,一个指示队头，一个指示队尾。
- rear和front互相追赶着，这个追赶过程就是队列添加和删除的过程，如果rear追到head说明队列满了，如果front追到rear说明队列为空。
- 我们把它掰弯，用的是求余，这样两个值就不会跑出最大范围，并且可以实现弯曲的效果，所以说对于循环队列我们必须给定最大值。这其实是我们臆想的，我们要做的就是利用循环来解决空间浪费的问题。
1.2.5.2. 2.2.5.2.环形队列的实现过程¶
- 当添加一个元素时,(rear+1)%MAXQSIZE; //理解为什么求余？
- 当删除一个元素时,(front+1)%MAXQSIZE；//理解为什么求余？
- 当rear=front的时候，队列可能是满，也可能是空。
- 因为存在满和空两种情况，我们需要分别判断：
- 满：当队列添加元素到rear的下一个元素是head的时候，也就是转圈子要碰头了，我们就认为队列满了。(rear+1)%MAXSIZE=Q.front
- 空：当队列删除元素到head=rear的时候，我们认为队列空了。rear==front,不一定为0
- 因为存在满和空两种情况，我们需要分别判断：
1.2.5.3. 2.2.5.3.环形队列代码实现¶
CircularQueue.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]);
}
}
测试代码如下：
/**
* 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();
}
}