一、稀疏数组

完整代码：
SparseArray.java

实际需求

QQ截图20200719103317.jpg

稀疏数组的介绍说明

作用说明：就是对于一些大部分元素为0的数组，可以转化为稀疏数组来记录原数组的信息，从而达到减少空间存储的功能。
数组描述：稀疏数组分为多行三列，第一行记录的是数组的行数、列数以及不为0的元素个数，接着将不为0的元素的行列位置以及元素值依次放在第一行之后的012位置上。

QQ截图20200719103448.jpg
QQ截图20200719103457.jpg

应用实例以及代码思路

QQ截图20200719103608.jpg
QQ截图20200719104035.jpg
QQ截图20200719103615.jpg

代码过程(说明+整体过程)

说明：
① 这个类具有创建初始数组的方法，将数组打印的方法，将稀疏数组转换为二维数组打印的方法，对于打印数组可以重复进行利用。
② 整体就是，二维数组 —> 稀疏数组 —> 二维数组 打印输出。
③ 对于其中的存储到硬盘使用到了ObjectOutputStream、ObjectInputStream来进行存储与读取，使用到了IO流中序列化与反序列化的操作。

  1. package com.mjj.test;
  3. import java.io.FileInputStream;
  4. import java.io.FileOutputStream;
  5. import java.io.ObjectInputStream;
  6. import java.io.ObjectOutputStream;
  8. public class SparseArray {
  9.     public static void main(String[] args) throws Exception{
  10.         int chessarr[][] = createArr();
  11.         //System.out.println("初始创建的数组：");
  12.         //printArr(chessarr);
  13.         //使用num来获取二维数组中非0的个数
  14.         int num=0;
  15.         for(int []a:chessarr) {
  16.             for(int ele:a) {
  17.                 if(ele!=0) {
  18.                     num++;
  19.                 }
  20.             }
  21.         }
  23.         //创建稀疏数组:开辟空间
  24.         int [][]sparseArray = new int[num+1][3];
  25.         //给稀疏数组的第一行赋值：原始数组行数、列数、以及不为0数
  26.         sparseArray[0][0] = 11;
  27.         sparseArray[0][1] = 11;
  28.         sparseArray[0][2] = num;
  30.         int len = 0;
  31.         for(int i=0;i<chessarr.length;i++) {
  32.             for(int j=0;j<chessarr[i].length;j++) {
  33.                 if(chessarr[i][j]!=0) {
  34.                     len++;
  35.                     sparseArray[len][0] = i;
  36.                     sparseArray[len][1] = j;
  37.                     sparseArray[len][2] = chessarr[i][j];
  38.                 }
  39.             }
  40.         }
  41.         System.out.println("打印稀疏数组：");
  42.         printArr(sparseArray);
  43.         System.out.println();
  45.         //保存到磁盘
  46.         ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("sparseArr.data"));
  47.         oos.writeObject(sparseArray);
  49.         //从磁盘中读取稀疏数组
  50.         ObjectInputStream ois = new ObjectInputStream(new FileInputStream("sparseArr.data"));
  51.         Object readObject = ois.readObject();
  52.         int [][]sparseArr2 = (int[][]) readObject;
  53.         System.out.println("打印一下从磁盘转换的数组：");
  54.         printArr(sparseArr2);
  57. //        //获取稀疏数组转回的二维数组并打印
  58. //        int[][] chessarr2 = transferArr(sparseArray);
  59. //        System.out.println("打印出由稀疏数组转化的棋盘：");
  60. //        printArr(chessarr2);
  63.     }
  65.     //创建原来数组
  66.     public static int[][] createArr() {
  67.         int[][] chessarr = new int[11][11];
  68.         chessarr[1][2] = 1;
  69.         chessarr[2][3] = 2;
  70.         chessarr[4][5] = 2;
  71.         return chessarr;
  72.     }
  74.     // 将二维数组打印
  75.     public static void printArr(int arr[][]) {
  76.         for (int[] a : arr) {
  77.             for (int ele : a) {
  78.                 System.out.print(ele + "\t");
  79.             }
  80.             System.out.println();
  81.         }
  82.     }
  84.     //将传入的稀疏数组转为对应数组传出
  85.     public static int[][] transferArr(int sparseArr[][]){
  86.         //开辟新的数组
  87.         int arr[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
  88.         for(int i=1;i<=sparseArr[0][2];i++) {
  89.             arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2]; 
  90.         }
  91.         return arr;
  92.     }
  93. }

二、队列

队列的介绍

QQ截图20200721105708.jpgQQ截图20200721105715.jpg
、

① 数组模拟队列思路(实现+问题)

完整代码：
ArrayQueue.java

数组队列说明以及代码实现

QQ截图20200721105727.jpg

说明：
① 对于队列有四个成员变量，开辟最大空间值maxsize、入列指向rear、出队指向front以及数组。(初始rear、front为-1)
② 对于队列中的方法有判断队列为空、判断队列已满、入队操作、出队操作、获取队头、展示数组信息。
判断队列为空**：rear==front
判断队列已满：rear==maxsize-1
入队操作：判断是否已满，rear+1，数组中对应下标赋值
出队操作：判断是否为空，front+1，返回下标元素
获取队头：**判断是否为空，通过front+1获取队头。

  1. package com.mjj.test;
  3. import java.util.Scanner;
  5. public class ArrayQueue {
  6.     public static void main(String[] args) {
  7.         //首先创建队列实例
  8.         MyQueue queue = new MyQueue(3);
  9.         //用于读入数据
  10.         Scanner scanner = new Scanner(System.in);
  11.         char c;
  12.         boolean flag = true;
  13.         while(flag) {
  14.             System.out.println("输入以下字符进行队列操作：");
  15.             System.out.println("s/S (show)：展示队列中的内容");
  16.             System.out.println("a/A (add)：进行入队操作");
  17.             System.out.println("o/O (out)：进行出队操作");
  18.             System.out.println("g/G (get)：获取队头");
  19.             System.out.println("e/E (exit)：退出程序");
  20.             c = scanner.next().toUpperCase().charAt(0);
  21.             switch (c) {
  22.             case 'S'://展示队列内容
  23.                 queue.showQueue();
  24.                 break;
  25.             case 'A'://进行入队操作
  26.                 int nextInt = scanner.nextInt();
  27.                 queue.addQueue(nextInt);
  28.                 break;
  29.             case 'O'://进行出队操作
  30.                 try {
  31.                     int outQueue = queue.outQueue();
  32.                     System.out.println(outQueue);
  33.                 } catch (Exception e) {
  34.                     System.out.println(e.getMessage());
  35.                 }
  36.                 break;
  37.             case 'G'://获取队头
  38.                 try {
  39.                     int queueHead = queue.getQueueHead();
  40.                     System.out.println(queueHead);
  41.                 } catch (Exception e) {
  42.                     System.out.println(e.getMessage());
  43.                 }
  44.                 break;
  45.             case 'E'://退出程序
  46.                 try {
  47.                     scanner.close();
  48.                 } catch (Exception e) {
  49.                     // TODO: handle exception
  50.                 }
  51.                 flag = false;
  52.                 System.out.println("感谢您使用，再见!");
  53.                 break;
  54.             default:
  55.                 break;
  56.             }
  57.         }
  60.     }
  61. }
  64. //使用数组来进行模拟队列
  65. class MyQueue{
  66.     private int maxsize;//用于指定数组的最大容量
  67.     private int front = -1;//用于指向出队元素的下标
  68.     private int rear = -1;//用于指向入队的下标
  69.     private int[] queue;//使用数组来进行模拟队列
  71.     //依据传入值，来对数组进行开辟空间
  72.     public MyQueue(int maxsize) {
  73.         this.maxsize = maxsize;
  74.         queue = new int[maxsize];//开辟数组控件
  75.     }
  77.     //判断队列是否为空
  78.     public boolean isEmpty() {
  79.         return front==rear;//如果两个指标都相等说明队列
  80.     }
  82.     //判断队列是否为满
  83.     public boolean isFull() {
  84.         return rear==maxsize-1;//根据开辟的最大空间与rear是否相等
  85.     }
  87.     //进行入队操作
  88.     public void addQueue(int element) {
  89.         //判断队列是否已满
  90.         if(isFull()) {
  91.             System.out.println("队列已满，无法添加数据!!!");
  92.             return;
  93.         }
  94.         rear++;
  95.         queue[rear] = element;
  96.     }
  98.     //进行出队操作
  99.     public int outQueue() {
  100.         if(isEmpty()) {
  101.             throw new RuntimeException("队列为空，无法取出数据!!!");
  102.         }
  103.         front++;
  104.         return queue[front];
  105.     }
  107.     // 查看队列中所有数据
  108.     public void showQueue() {
  109.         System.out.print("队列中的所有数据如下：");
  110.         for (int i = 0; i < maxsize; i++) {
  111.             System.out.print(queue[i] + " ");
  112.         }
  113.         System.out.println();
  114.     }
  116.     //取出队头
  117.     public int getQueueHead() {
  118.         //判断是否为空
  119.         if(isEmpty()) {
  120.             throw new RuntimeException("队列为空，无法取出队头!!!");
  121.         }
  122.         return queue[front+1];
  123.     }
  127. }

存在空间问题(需要靠环形解决)

对于数组的空间没有能够很好的利用到，出队到一定数量时，对于之前已经出队的位置不能够很好的利用。

② 数组模拟环形队列(解决空间问题)

完整代码：
AnnularArrayQueue.java

环形队列说明(预留不预留问题、参数问题，图解问题)

对于数组解决环形队列的问题，存在着空间预留不预留的问题。
空间预留：就是说你要开辟4个空间的数组，实际上只能存放三个数据。
空间不预留：开辟4个空间，能够真实存放四个数据。

环形队列参数说明：
maxsize：开辟数组空间数量。
rear：相当于数组下标记录入队，初始设置为0，每次入队时判断队列是否已满，再插入rear位置的数据，最后加1，需要考虑数组越界问题，(rear+1)%maxsize。
front：也是数组下标记录出队，初始设置为0，每次出队时先判断队列是否为空，再移除front位置上的数据，最后+1，也要考虑数组越界问题，(front+1)%maxsize
arrr[]：也就是数组。

为什么要说预留不预留的问题，并且有什么关键点？

① 我们来看下面不预留的情况：
队列满以及队列空的说明
QQ截图20200722122323.jpg

② 我们来看下面预留的情况：解决不预留判断队列满或空的问题
队列满以及队列空的说明
QQ截图20200722124614.jpg

总结：通过图解，我们可以看到使用预留的方式可以解决不预留时判断队列满与空式子相同的问题。




**

如何解决不预留时判断队列满与空的问题？

QQ截图20200722125059.jpg
例如使用计数器：入队时count++，出队时count—，判断队列满if(count>0)，队列空if(count==0)

代码实现：(空间预留解决)

方法说明：判断队列满，判断队列空，入队，出队，获取队列中的数量、展示队列中的信息以及获取队列头部数据。

其中获取队列中的数量size()方法：(rear-front+maxsize)%maxsize
见下图：
QQ截图20200722144547.jpg
其余的思考下即可理解。

  1. package com.mjj.test;
  3. import java.util.Scanner;
  5. public class AnnularArrayQueue {
  6.     public static void main(String[] args) {
  7.         // 首先创建队列实例
  8.         MyAnnularQueue queue = new MyAnnularQueue(4);
  9.         // 用于读入数据
  10.         Scanner scanner = new Scanner(System.in);
  11.         char c;
  12.         boolean flag = true;
  13.         while (flag) {
  14.             System.out.println("输入以下字符进行队列操作：");
  15.             System.out.println("s/S (show)：展示队列中的内容");
  16.             System.out.println("a/A (add)：进行入队操作");
  17.             System.out.println("o/O (out)：进行出队操作");
  18.             System.out.println("g/G (get)：获取队头");
  19.             System.out.println("e/E (exit)：退出程序");
  20.             c = scanner.next().toUpperCase().charAt(0);
  21.             switch (c) {
  22.             case 'S':// 展示队列内容
  23.                 queue.showQueue();
  24.                 break;
  25.             case 'A':// 进行入队操作
  26.                 int nextInt = scanner.nextInt();
  27.                 queue.addQueue(nextInt);
  28.                 break;
  29.             case 'O':// 进行出队操作
  30.                 try {
  31.                     int outQueue = queue.outQueue();
  32.                     System.out.println(outQueue);
  33.                 } catch (Exception e) {
  34.                     System.out.println(e.getMessage());
  35.                 }
  36.                 break;
  37.             case 'G':// 获取队头
  38.                 try {
  39.                     int queueHead = queue.getQueueHead();
  40.                     System.out.println("队头数据为：" + queueHead);
  41.                 } catch (Exception e) {
  42.                     System.out.println(e.getMessage());
  43.                 }
  44.                 break;
  45.             case 'E':// 退出程序
  46.                 try {
  47.                     scanner.close();
  48.                 } catch (Exception e) {
  49.                     // TODO: handle exception
  50.                 }
  51.                 flag = false;
  52.                 System.out.println("感谢您使用，再见!");
  53.                 break;
  54.             default:
  55.                 break;
  56.             }
  57.         }
  59.     }
  60. }
  62. class MyAnnularQueue{
  63.     private int maxsize;//用于指定数组的最大容量
  64.     private int front = 0;//用于指向出队元素的下标,这是环形所以设置为1
  65.     private int rear = 0;//用于指向入队的下标
  66.     private int[] arr;//使用数组来进行模拟队列
  68.     ////依据传入值，来对数组进行开辟空间
  69.     public MyAnnularQueue(int maxsize) {
  70.         this.maxsize = maxsize;
  71.         arr = new int[maxsize];
  72.     }
  74.     //判断队列是否为空
  75.     public boolean isEmpty() {
  76.         return rear==front;
  77.     }
  79.     //判断队列是否已满
  80.     public boolean isFull() {
  81.         return (rear+1)%maxsize == front;
  82.     }
  84.     // 进行入队操作
  85.     public void addQueue(int element) {
  86.         if (isFull()) {
  87.             System.out.println("队列已满，无法入队！！！");
  88.             return;
  89.         }
  90.         arr[rear] = element;
  91.         // 需要考虑数组越界问题
  92.         rear = (rear + 1) % maxsize;
  93.         System.out.println("element:" + element + "插入成功");
  94.     }
  96.     //进行出队操作
  97.     public int outQueue() {
  98.         if(isEmpty()) {
  99.             throw new RuntimeException("队列已空，无法出队");
  100.         }
  101.         //获取出队元素，并且该位置变为0
  102.         int num = arr[front];
  103.         arr[front] = 0;
  104.         //考虑到数组越界的问题
  105.         front = (front+1)%maxsize;
  106.         return num;
  107.     }
  109.     //获取队列中已有的元素
  110.     public int size() {
  111.         //其中+maxsize是为了解决rear-front是负数的原因
  112.         return (rear-front+maxsize)%maxsize;
  113.     }
  115.     // 查看队列中所有数据
  116.     public void showQueue() {
  117.         if(isEmpty()) {
  118.             System.out.println("队列为空，无法查看数据！");
  119.             return;
  120.         }
  121.         System.out.println("队列数据如下：");
  122.         for(int i=front;i<front+size();i++) {
  123.             System.out.printf("a[%d]=%d\t",i%maxsize,arr[i%maxsize]);
  124.         }
  125.         System.out.println();
  127.     }
  129.     //取出队头
  130.     public int getQueueHead() {
  131.         if(isEmpty()) {
  132.             throw new RuntimeException("队列中数据为空，无法取出!");
  133.         }
  134.         return arr[front];
  135.     }
  138. }