第二章 稀疏数组和队列

2.1 稀疏数组（SparseArray）

2.1.1 场景需求

问题： 编写一个五子棋程序，其中有存盘退出和续上盘的功能。

方案： 可以使用二维数组解决上述问题，但因为二维数组的很多值是默认零值，因此记录了很多没有意义的数据，可以使用稀疏数组来解决无效数据的问题。

2.1.2 基本介绍

所谓稀疏数组就是指，数组中大部分的内容值都未被使用（或都为零），在数组中仅有少部分的空间被有效使用，因此造成内存空间的浪费，为了节省内存空间，并且不影响数组中原有的内容值，我们可以采用一种压缩的方式来表示数组的内容。

稀疏数组的处理方法是:

记录数组一共有几行几列，有多少个不同的值。把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。

假设有一个9*7的数组，其内容如下： 在此数组中共有63个空间，但却只使用了5个元素，造成58个元素空间的浪费，所以可以使用稀疏数组重新来定义这个数组： 其中在稀疏数组中，第一部分所记录的是原数组的列数和行数以及元素使用的个数，第二部分所记录的是原数组中元素的位置和内容，经过压缩之后，原来需要声明大小为63的数组，在使用压缩后只需要声明大小为18的数组。

2.1.3 应用实例

可以使用稀疏数组来保存类似前面的二维数组(棋盘、地图等等)，并把稀疏数组存入磁盘，就可以实现存盘退出和续上盘的功能。

整体思路分析：

原始数组转稀疏数组：

遍历原始的二维数组，得到有效数据的个数sum。根据有效数据的个数常见稀疏数组 int[][] sparses = new int[sum + 1][3]。将二维数组中的有效数据存入到稀疏数组中。

稀疏数组转原始数组：

读取稀疏数组的第一行，创建原始二维数组 int[][] sourceArrays = new int[sparses[0][0]][sparses[0][1]]。读取稀疏数组后续的数据，并赋值给原始二维数组。

2.1.4 代码实现

public class SparseArrayTest { public static void main(String[] args) { // 源数组 int[][] arrays = new int[11][11]; arrays[1][2] = 1; arrays[2][3] = 2; arrays[3][4] = 1; int sum = 0; // 查看源数组 for (int[] rows : arrays) { for (int item : rows) { if (item != 0) { sum++; } System.err.printf("%d\t", item); } System.err.println(); } // 源数组转稀疏数组 System.err.println("******************************* 源数组转稀疏数组 *******************************"); int[][] sparses = new int[sum + 1][3]; sparses[0][0] = 11; sparses[0][1] = 11; sparses[0][2] = sum; // 遍历二维数组，将二维数组的有效值添加到稀疏数组中 int count = 0; for (int i = 0; i < arrays.length; i++) { int[] temp = arrays[i]; for (int j = 0; j < temp.length; j++) { if (arrays[i][j] != 0) { count++; sparses[count][0] = i; sparses[count][1] = j; sparses[count][2] = arrays[i][j]; } } } // 查看稀疏数组 for (int[] rows : sparses) { for (int item : rows) { System.err.printf("%d\t", item); } System.err.println(); } // 稀疏数组转源数组 System.err.println("******************************* 稀疏数组转源数组 *******************************"); int[][] sourceArrays = new int[sparses[0][0]][sparses[0][1]]; for (int i = 1; i < sparses.length; i++) { sourceArrays[sparses[i][0]][sparses[i][1]] = sparses[i][2]; } // 查看源数组 for (int[] rows : arrays) { for (int item : rows) { System.err.printf("%d\t", item); } System.err.println(); } } }

2.2 队列

2.2.1 场景需求

问题： 银行排队的案例。

方案： 使用队列来解决。

2.2.2 基本介绍

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。

队列是一个有序列表，可以用数组或是链表来实现，遵循先入先出的原则，即先存入队列的数据要先取出，后存入的要后取出。

2.2.3 数组模拟队列

思路分析：

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队 列的最大容量。因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front 及 rear 分别记录队列前后端的下标， front 会随着数据输出而改变，而 rear 则是随着数据输入而改变。

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

将尾指针往后移 rear+1，当 front == rear 时表示队列为空，可以存入数据。若尾指针 rear 小于队列的最大下标 maxSize-1时，则将数据存入 rear 所指的数组元素中，否则当 rear == maxSize - 1 时表示队列已满无法存入数据。

代码实现

public class ArrayQueueTest { public static void main(String[] args) { //创建一个队列 ArrayQueue queue = new ArrayQueue(3); //接收用户输入 char key; Scanner scanner = new Scanner(System.in); boolean loop = true; //输出一个菜单 while (loop) { System.out.println("s(show): 显示队列"); System.out.println("e(exit): 退出程序"); System.out.println("a(add): 添加数据到队列"); System.out.println("g(get): 从队列取出数据"); System.out.println("h(head): 查看队列头的数据"); key = scanner.next().charAt(0);//接收一个字符 switch (key) { case 's': queue.showQueue(); break; case 'a': System.out.println("输出一个数"); int value = scanner.nextInt(); queue.addQueue(value); break; case 'g': try { int item = queue.getQueue(); System.out.printf("取出的数据是%d\n", item); } catch (Exception e) { System.err.println(e.getMessage()); } break; case 'h': try { int head = queue.headQueue(); System.out.printf("队列头的数据是%d\n", head); } catch (Exception e) { System.err.println(e.getMessage()); } break; case 'e': scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出~~"); } } class ArrayQueue { // 表示数组的最大容量 private int maxSize; // 队列头 private int front; // 队列尾 private int rear; // 该数据用于存放数据, 模拟队列 private int[] array; /** * 创建队列的构造器 * * @param maxSize */ public ArrayQueue(int maxSize) { // 数组最大容量 this.maxSize = maxSize; // 指向队列头部,分析出 front 是指向队列头的前一个位置. this.front = -1; // 指向队列尾,指向队列尾的数据(即就是队列最后一个数据) this.rear = -1; // 初始化数组 this.array = new int[maxSize]; } /** * 判断队列是否满 * * @return */ public boolean isFull() { return rear == maxSize - 1; } /** * 判断队列是否为空 * * @return */ public boolean isEmpty() { return rear == front; } /** * 添加数据到队列 * * @param param */ public void addQueue(int param) { // 判断队列是否满 if (isFull()) { System.out.println("队列满,不能加入数据~"); return; } // 让 rear 后移并赋值 array[++rear] = param; } /** * 获取队列的数据 * * @return */ public int getQueue() { // 判断队列是否空 if (isEmpty()) { // 通过抛出异常 throw new RuntimeException("队列空,不能取数据"); } return array[++front]; } /** * 显示队列的所有数据 */ public void showQueue() { // 遍历 if (isEmpty()) { System.out.println("队列空的,没有数据~~"); return; } for (int i = 0; i < array.length; i++) { System.out.printf("array[%d]=%d\n", i, array[i]); } } /** * 显示队列的头数据, 注意不是取出数据 * * @return */ public int headQueue() { // 判断 if (isEmpty()) { throw new RuntimeException("队列空的,没有数据~~"); } return array[front + 1]; } }

2.2.4 数组模拟环形队列

对前面的数组模拟队列的优化，充分利用数组，因此将数组看做是一个环形的（通过取模的方式来实现即可），当尾索引的下一个为头索引时表示队列为满，即将队列容量空出一个空间作为约定 (rear + 1) % maxSize == front。

思路分析：

front 指向队列的第一个元素，也就是说 array[front]就是队列的第一个元素，front 初始值为 0rear指向队列最后一个元素的后一个位置，空出一个空间作为约定，rear 初始值为 0当队列满时的条件为 (rear + 1) % maxSize == front当队列为空时的条件为 rear == front队列中有效数据的个数 (rear + maxSize - frint) % maxSize

代码实现：

public class CircleArrayQueueTest { public static void main(String[] args) { System.out.println("测试数组模拟环形队列的案例~~~"); // 创建一个环形队列，说明设置4，其队列的有效数据最大是3 CircleArray queue = new CircleArray(4); char key = ' '; // 接收用户输入 Scanner scanner = new Scanner(System.in); boolean loop = true; // 输出一个菜单 while (loop) { System.out.println("s(show): 显示队列"); System.out.println("e(exit): 退出程序"); System.out.println("a(add): 添加数据到队列"); System.out.println("g(get): 从队列取出数据"); System.out.println("h(head): 查看队列头的数据"); key = scanner.next().charAt(0); switch (key) { case 's': queue.showQueue(); break; case 'a': System.out.println("输出一个数"); int value = scanner.nextInt(); queue.addQueue(value); break; case 'g': try { int res = queue.getQueue(); System.out.printf("取出的数据是%d\n", res); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'h': try { int res = queue.headQueue(); System.out.printf("队列头的数据是%d\n", res); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'e': scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出~~"); } } class CircleArray { // 表示数组的最大容量 private int maxSize; // front 指向队列的第一个元素，初始值 = 0 private int front; // rear 指向队列的最后一个元素的后一个位，置初始值 = 0 private int rear; // 该数据用于存放数据, 模拟队列 private int[] arrays; public CircleArray(int maxSize) { this.maxSize = maxSize; this.arrays = new int[maxSize]; } /** * 判断队列是否满 * * @return */ public boolean isFull() { return (rear + 1) % maxSize == front; } /** * 判断队列是否为空 * * @return */ public boolean isEmpty() { return rear == front; } /** * 添加数据到队列 * * @param n */ public void addQueue(int n) { // 判断队列是否满 if (isFull()) { System.out.println("队列满,不能加入数据~"); return; } // 直接将数据加入 arrays[rear] = n; // 将 rear 后移, 这里必须考虑取模 rear = (rear + 1) % maxSize; } /** * 获取队列的数据, 出队列 * * @return */ public int getQueue() { // 判断队列是否空 if (isEmpty()) { throw new RuntimeException("队列空,不能取数据"); } // 1. 先把 front 对应的值保留到一个临时变量 // 2. 将 front 后移, 考虑取模 // 3. 将临时保存的变量返回 int value = arrays[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.printf("arrays[%d]=%d\n", i % maxSize, arrays[i % maxSize]); } } /** * 求出当前队列有效数据的个数 * * @return */ public int size() { return (rear + maxSize - front) % maxSize; } /** * 显示队列的头数据, 注意不是取出数据 * * @return */ public int headQueue() { if (isEmpty()) { throw new RuntimeException("队列空的,没有数据~~"); } return arrays[front]; } }