一、稀疏数组

1、稀疏数组实际需求

编写一个五子棋程序，有存盘退出和续上盘的功能。
未命名图片.png
分析问题：因为这个二维数组中很多的默认值都是0，因此记录了很多没有意义的数据，这时就可以用到稀疏数组

2、稀疏数组基本介绍

当一个数组中大部分元素都是0，或者都是同一个值的数组时，可以使用稀疏数组来保存该数组。

稀疏数组的处理方法是：**

  1. 稀疏数组的第一行是 记录数组一共有几行几列（这里不是索引，从1开始），有多少个不同的值
  2. 把具有不同值得元素的行列及值记录在一个小规模的数组（稀疏数组）中，从而缩小程序的规模 —->
  3. ——————————>原来的二维数组是42个值，使用稀疏数组后变成27个值（节省了很大空间）
  4. 稀疏数组 永远是一个 行不确定（有效值的数量+1 = 真实行数），但是就三个列(行，列，值)的一个二维数组
  5. 稀疏数组第二行及以下 都是存放原始二维数组中 有效值的坐标（行和列分别是 下标[索引]）

未命名图片.png

3、稀疏数组的应用实例

  1. 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
  2. 把稀疏数组存盘，并且可以从新恢复原来的二维数组数
  3. 整体思路分析

4、二维数组转稀疏数组的思路：

  • 遍历原始的二维数组，得到要保存的有效的数据的个数 sum。
  • 根据sum就可以创建稀疏数组 sparseArray，
  • 创建稀疏数组： 行是有效数据+1，列永远是3 || **int[][] sparseArray = new int[sum+1][3] ;**
  • 将二维数组的 有效数据的 坐标 和 值 存入到稀疏数组中

4、稀疏数组转原始的二维数组的思路：

  • 读取到稀疏数组的第一行，读到这个原始二维数组 有几行 几列，几个有效值
  • 根据第一行的数据创建原始二维数组，**int[][] chessArray = new int[行][列];**
  • 在读取稀疏数组后几行的数据，并赋给这个原始的二维数组，【根据下标赋值】

未命名图片.png

二、稀疏数组代码实现

1、原始二维数组转换稀疏数组

  1.     //创建原始二维数组
  2.     int[][] chessArray = new int[11][11];
  3.     //给里面赋值，这个里面就是一个棋盘，有两个棋子
  4.     chessArray[1][2] = 1;
  5.     chessArray[2][3] = 2;
  6.     //查看棋盘
  7.     for (int[] ints : chessArray) {
  8.         for (int anInt : ints) {
  9.             System.out.print(anInt + "\t");
  10.         }
  11.         System.out.println("\n");
  12.     }
  13.     //现在将这个原始二维数组转换成 稀疏数组
  14.     //1.先遍历数组，找到有多少有效数据【非0的数据】
  15.     //sum：有效值数量
  16.     int sum = 0;
  17.     for (int[] ints : chessArray) {
  18.         for (int anInt : ints) {
  19.             if (anInt != 0){
  20.                 sum ++;
  21.             }
  22.         }
  23.     }
  24.     System.out.println("有效数据共有：" + sum + "个");
  25.     //得到原始二维数组的行和列
  26.     int hang = chessArray.length;
  27.     int lie = chessArray[0].length;
  28.     //2.创建稀疏数组
  29.     //稀疏数组的行永远是 有效数据的数量+1 ， 列永远是 3
  30.     int[][] sparseArray = new int[sum + 1][3];
  31.     //3.给稀疏数组里面添加数据
  32.     //分别是 原始二维数组的 行数，列数，有效数据有几个
  33.     sparseArray[0][0] = hang;
  34.     sparseArray[0][1] = lie;
  35.     sparseArray[0][2] = sum;
  36.     //4.把原始二维数组里面的数据坐标 及 数据放到 稀疏数组里面
  37.     //定义一个计数器,用来做稀疏数组的下标使用
  38.     int count = 0;
  39.     for (int i = 0; i < chessArray.length; i++){
  40.         for (int j = 0; j < chessArray[i].length; j++){
  41.             //如果原始二维数组里面的数据不为0，表示可以放到稀疏数组里面
  42.             if (chessArray[i][j] != 0){
  43.                 count++;
  44.                 // 把原始数据的行 放到 稀疏数组
  45.                 sparseArray[count][0] = i;
  46.                 //列
  47.                 sparseArray[count][1] = j;
  48.                 //有效数据
  49.                 sparseArray[count][2] = chessArray[i][j];
  50.             }
  51.         }
  52.     }
  53.     //查看稀疏数组
  54.     for (int[] ints : sparseArray) {
  55.         for (int anInt : ints) {
  56.             System.out.print(anInt + "\t");
  57.         }
  58.         System.out.println();
  59.     }

未命名图片.png

2、稀疏数组转二维数组

  1.     //先获得一个稀疏数组
  2.     int[][] sparseArray = new int[3][3];
  3.     sparseArray[0][0] = 11;
  4.     sparseArray[0][1] = 11;
  5.     sparseArray[0][2] = 2;
  6.     sparseArray[1][0] = 1;
  7.     sparseArray[1][1] = 2;
  8.     sparseArray[1][2] = 1;
  9.     sparseArray[2][0] = 2;
  10.     sparseArray[2][1] = 3;
  11.     sparseArray[2][2] = 2;
  13.     //1.读取稀疏数组第一行，得到原始数组的行和列，并创建原始数组
  14.     int hang = sparseArray[0][0];
  15.     int lie = sparseArray[0][1];
  16.     int[][] chessArray = new int[hang][lie];
  18.     //2.把稀疏数组里面的值拿出来 给原始二维数组赋上
  19.     for (int i = 1; i < sparseArray.length; i++){
  20.         //稀疏数组里面第二行 前两列都是 值得下标，
  21.         chessArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
  22.     }
  24.     for (int[] ints : chessArray) {
  25.         for (int anInt : ints) {
  26.             System.out.print(anInt + "\t");
  27.         }
  28.         System.out.println();
  29.     }

未命名图片.png

三、队列

1、队列是使用场景

  • 例如 银行排队叫号
  • 先进先出，后进后出

    2、队列介绍

  1. 队列是一个有序列表，可以用数组或者是链表来实现
  2. 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
  3. 示意图：(使用数组模拟队列示意图) —————->
  4. 队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表
  5. 队列是一种先进先出（first in first out） 的线性表，简称 fifo，允许插入的那一端为队尾，允许删除的那一段叫对头

未命名图片.png

3、数组模拟队列

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

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

  1. 将尾指针往后移：rear+1, 当 front == rear 【空】 【头和尾相同时，表示此队列为空】
  2. 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。 rear ==maxSize-1[队列满] 【尾== 数组.length-1 说明队列满了】

4、普通队列出现的问题：

  1. 普通队列的缺点： 该队列只能使用一次【不能重复使用】，front 【头部下标】不会回溯，而要解决这个问题就需要使用到 环形队列
  2. 将原来的数组，使用一个算法，变成环形队列。 使用取模的方式：%

5、数组模拟环形队列思路分析：

  1. front 【头部】变量做一个调整：front就指向队列的第一个元素下标， 之前是指向-1，现在是指向0， 也就是说 arr[front] == 队列中的第一个元素 【front的初始值是 0 】
  2. rear 【尾部】变量做一个调整：rear就指向队列中的最后一个元素的后一个位置下标，因为希望空出一个空间做约定 【rear的初始值是 0】
  3. 能储存的数据量是 长度 - 1 ， 因为rear 要预留一个空的
  4. 当队列满时的条件是， **(rear + 1) % maxSize == front** 【true 则满】
    • 代数： maxSize 是 4， 长度是4，下标为 0，1，2，3 因为rear要预留出一个空间，所以按照上面的 最后一个元素的后一个位置下标 只能是 3 【下标为2 的后面一个元素的下标】
    • rear因为是指向最后一个元素的后面那个位置的下标，rear指向下标为2的元素的后面那个位置的下标，所以是3
    • 带入条件 (3 + 1) % 4 == 0; 如果当前这个环形列队中的头部变量是 0 则表示此队列满了
  5. 当队列为空的条件， rear == front 【true 则空】
  6. 按照上面分析的话，队列中有效的数据的个数是 ：**(rear + maxSize - front) % maxSize**
    • 代数：如果 rear = 1，则表示在队列中下标为 0 的位置有1个 数据【为什么是rear = 1，因为他指向最后一个元素的后一个位置的下标】
    • (1 + 3 - 0) % 3 = 1 所以等于1

四、队列代码实现

1、普通队列代码实现

  1. //此类为队列
  2. public class ArrayQueue {
  3.     private int maxSize;  //队列最大容量
  4.     private int front; //队列头部下标  最初是指向 -1
  5.     private int rear;  //队列尾部下标  没有元素则是指向 -1
  6.     private int[] arrayQueue;  //队列
  8.     //通过构造方法 来指定队列的长度，并且初始化一些成员变量
  9.     public ArrayQueue(int maxSize){
  10.         this.maxSize = maxSize;
  11.         front = -1;
  12.         rear = -1;
  13.         arrayQueue = new int[maxSize]; //创建指定大小的数组【队列】
  14.     }
  16.     //判断此队列是不是为空的方法
  17.     public boolean isEmpty(){
  18.         //如果头部下标 == 尾部下标 则表示队列中没有数据，为空
  19.         return front == rear;
  20.     }
  22.     //判断队列是否已满的方法
  23.     public boolean isFull(){
  24.         //如果尾部下标 == 数组.length - 1 则表示队列满了
  25.         return rear == maxSize - 1;
  26.     }
  28.     //往队列里面放数据的方法
  29.     public void addQueue(int n){
  30.         if (isFull()){
  31.             throw new RuntimeException("队列已满，无法加入数据");
  32.         }
  33.         //存数据从尾部存，后存后出
  34.         rear ++;  //最初是指向-1的，每添加一次数据时 自增1
  35.         arrayQueue[rear] = n;
  36.     }
  38.     //从队列里面取出数据
  39.     public int getQueue(){
  40.         if (isEmpty()){
  41.             throw new RuntimeException("队列为空，没有数据可取");
  42.         }
  43.         front ++;   //取数据是往头部取，先进先出
  44.         return arrayQueue[front];
  45.     }
  47.     //查看队列全部元素
  48.     public void showQueue(){
  49.         if (isEmpty()){
  50.             throw new RuntimeException("队列为空，没有数据展示");
  51.         }
  52.         for (int i = 0; i < maxSize; i++){
  53.             System.out.println("arr["+ i +"]:" + arrayQueue[i] + "\n");
  54.         }
  55.     }
  57.     //显示队列头部数据
  58.     public int headQueue(){
  59.         if (isEmpty()){
  60.             throw new RuntimeException("队列为空，没有数据展示");
  61.         }
  62.         return arrayQueue[front+1];
  63.     }
  64. }
  66. // -------------------------------------------------------测试
  67. public class ArrayQueueTest {
  68.     public static void main(String[] args) {
  70.         ArrayQueue queue = new ArrayQueue(3);
  72.         boolean loop = true;
  73.         Scanner scanner = new Scanner(System.in);
  75.         while (loop){
  76.             System.out.println("-------------------------------->");
  77.             System.out.println("s 查看队列中所有元素");
  78.             System.out.println("a 向队列中添加一个元素");
  79.             System.out.println("g 向队列中得到一个元素");
  80.             System.out.println("h 得到队列中的头部元素");
  81.             System.out.println("e 退出循环");
  82.             String next = scanner.next();
  83.             switch (next){
  84.                 case "s":
  85.                     try{
  86.                         queue.showQueue();
  87.                     }catch (Exception e){
  88.                         System.out.println(e.getMessage());
  89.                     }
  90.                     break;
  91.                 case "a":
  92.                     try{
  93.                         queue.addQueue(scanner.nextInt());
  94.                     }catch (Exception e){
  95.                         System.out.println(e.getMessage());
  96.                     }
  97.                     break;
  98.                 case "g":
  99.                     try{
  100.                         int queue1 = queue.getQueue();
  101.                         System.out.println("得到的元素是： " + queue1);
  102.                     }catch (Exception e){
  103.                         System.out.println(e.getMessage());
  104.                     }
  105.                     break;
  106.                 case "h":
  107.                     try{
  108.                         int queue1 = queue.headQueue();
  109.                         System.out.println("头部的元素是： " + queue1);
  110.                     }catch (Exception e){
  111.                         System.out.println(e.getMessage());
  112.                     }
  113.                     break;
  114.                 case "e":
  115.                     scanner.close();
  116.                     loop = false;
  117.                     break;
  118.             }
  119.         }
  120.         System.out.println("退出成功");
  121.     }
  122. }

2、环形列队代码实现

  1. public class CircleQueue {
  2.     private int maxSize;  //队列最大容量
  3.     private int front; //队列头部下标  最初是指向 0
  4.     private int rear;  //队列尾部下标  没有元素则是指向 0
  5.     private int[] arrayQueue;  //队列
  7.     //通过构造方法 来指定队列的长度，并且初始化一些成员变量
  8.     public CircleQueue(int maxSize){
  9.         this.maxSize = maxSize;
  10.         arrayQueue = new int[maxSize]; //创建指定大小的数组【队列】
  11.     }
  13.     //判断此队列是不是为空的方法
  14.     public boolean isEmpty(){
  15.         //如果头部下标 == 尾部下标 则表示队列中没有数据，为空
  16.         return front == rear;
  17.     }
  19.     //判断队列是否已满的方法
  20.     public boolean isFull(){
  21.         //如果尾部下标 == 数组.length - 1 则表示队列满了
  22.         return (rear + 1) % maxSize == front ;
  23.     }
  25.     //往队列里面放数据的方法
  26.     public void addQueue(int n){
  27.         if (isFull()){
  28.             throw new RuntimeException("队列已满，无法加入数据");
  29.         }
  30.         //直接上数据放到 尾部
  31.         arrayQueue[rear] = n;
  32.         //将rear后移，因为要考虑到 如果rear在最后面位置的话，可能要往头部放
  33.         rear = (rear + 1) % maxSize;
  34.     }
  36.     //从队列里面取出数据
  37.     public int getQueue(){
  38.         if (isEmpty()){
  39.             throw new RuntimeException("队列为空，没有数据可取");
  40.         }
  42.         // 这里需要分析出 front 是指向队列的第一个元素
  43.         // 1. 先把 front 对应的值保留到一个临时变量
  44.         // 2. 将 front 后移, 考虑取模
  45.         // 3. 将临时保存的变量返回
  46.         int value = arrayQueue[front];
  47.         front = (front + 1)%maxSize;
  48.         return value;
  50.     }
  52.     //查看队列全部元素
  53.     public void showQueue() {
  54.         if (isEmpty()) {
  55.             throw new RuntimeException("队列为空，没有数据展示");
  56.         }
  58.         // 思路：从 front 开始遍历，遍历多少个元素
  59.         // 动脑筋
  60.         for (int i = front; i < front + size(); i++) {
  61.             System.out.printf("arr[%d]=%d\n", i % maxSize, arrayQueue[i % maxSize]);
  62.         }
  63.     }
  64.     //求出当前队列的有效数据
  65.     public int size(){
  66.         return (rear + maxSize - front) % maxSize;
  67.     }
  70.     //显示队列头部数据
  71.     public int headQueue(){
  72.         if (isEmpty()){
  73.             throw new RuntimeException("队列为空，没有数据展示");
  74.         }
  76.         return arrayQueue[front];
  77.     }
  78. }
  80.  //-------------------------------------------------------------------测试
  81. 下面为测试上面的那个队列
  82. public class CircleQueueTest {
  83.     public static void main(String[] args) {
  85.         CircleQueue queue = new CircleQueue(3);
  87.         boolean loop = true;
  88.         Scanner scanner = new Scanner(System.in);
  90.         while (loop){
  91.             System.out.println("-------------------------------->");
  92.             System.out.println("s 查看队列中所有元素");
  93.             System.out.println("a 向队列中添加一个元素");
  94.             System.out.println("g 向队列中得到一个元素");
  95.             System.out.println("h 得到队列中的头部元素");
  96.             System.out.println("e 退出循环");
  97.             String next = scanner.next();
  98.             switch (next){
  99.                 case "s":
  100.                     try{
  101.                         queue.showQueue();
  102.                     }catch (Exception e){
  103.                         System.out.println(e.getMessage());
  104.                     }
  105.                     break;
  106.                 case "a":
  107.                     try{
  108.                         queue.addQueue(scanner.nextInt());
  109.                     }catch (Exception e){
  110.                         System.out.println(e.getMessage());
  111.                     }
  112.                     break;
  113.                 case "g":
  114.                     try{
  115.                         int queue1 = queue.getQueue();
  116.                         System.out.println("得到的元素是： " + queue1);
  117.                     }catch (Exception e){
  118.                         System.out.println(e.getMessage());
  119.                     }
  120.                     break;
  121.                 case "h":
  122.                     try{
  123.                         int queue1 = queue.headQueue();
  124.                         System.out.println("头部的元素是： " + queue1);
  125.                     }catch (Exception e){
  126.                         System.out.println(e.getMessage());
  127.                     }
  128.                     break;
  129.                 case "e":
  130.                     scanner.close();
  131.                     loop = false;
  132.                     break;
  133.             }
  135.         }
  136.         System.out.println("退出成功");
  137.     }
  139. }