稀疏数组和队列

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

稀疏数组的处理方法

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

二维数组装稀疏数组的思路

1. 遍历原始的二位数组，得到有效数据的个数sum
2. 根据sum创建稀疏数组 sparse Arr int[sum + 1] [3]
3. 将 二维数组 的有效数据存入到稀疏数组
4. 稀疏数组转原始二维数组的思路
5. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二位数组
6. 再读取稀疏数组后几行的数据，并赋给原始的二维数组即可

• 代码实现

 public class SparseArray {
  public  static   void  main(String[] args) throws  Exception  {
      int arr[][] = new int[11][11];
      arr[1][2] = 2;
      arr[2][3] = 1;
      for (int[] ints : arr) {
          for (int item : ints) {
              System.out.print(item + "t");
          }
          System.out.println();
      }

      //将二维数组转换为稀疏数组
      int sum = 0; //用来计算有效个数
      for (int i = 0; i < 11; i++) {
          for (int j = 0; j < 11; j++) {
              if (arr[i][j] != 0) {
                   sum ++;
              }
          }
      }
      //创建稀疏数组
      int spar[][] = new int[sum+1][3];
      spar[0][0] = 11;
      spar[0][1] = 11;
      spar[0][2] = sum;

      // 计数器 ，计算查到第几个非0数据
      int count = 0;
      for (int i = 0;i<11;i++) {
          for (int j = 0;j<11;j++) {
              if(arr[i][j]!=0){
                  count++;
                  spar[count][0] = i;
                  spar[count][1] = j;
                  spar[count][2] = arr[i][j];
              }
          }
      }

      for (int[] ints : spar) {
          for (int anInt : ints) {
              System.out.print(anInt+"t");
          }
          System.out.println();
      }
      //C:UserszxyDesktop文本文件test
      String filePath = "C:\Users\zxy\Desktop\文本文件\test\map.data";
      ObjectOutputStream stream = new ObjectOutputStream(new FileOutputStream(filePath));
      stream.writeObject(spar);
      stream.close();
      System.out.println("完成序列化存储");

      //对象反序列化
      ObjectInputStream  InputStream  = new ObjectInputStream(new FileInputStream(filePath));
      int sparr[][]= (int[][]) inputStream.readObject();
      System.out.println("反序列化后的数据-------");
      //转换为二维数组
      int newarr[][] = new int[sparr[0][0]][sparr[0][1]];

      for (int i=1;i<sparr.length;i++){
          newarr[sparr[i][0]][sparr[i][1]] = sparr[i][2];
      }

      for (int[] ints : newarr) {
          for (int anInt : ints) {
              System.out.print(anInt + "t");
          }
          System.out.println();
      }

  }
}  

遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出

数组模拟环形队列思路

1. front变量指向队列的第一个元素，也就是说初始值为0
2. rear变量指向队列的 最后一个元素的后一个位置 ，因为希望空出一个空间作为约定，初始值为0
3. 当队列满时，条件是**(rear + 1) % maxSize = front 【满】**
4. 队列为空的条件， rear == front 空
5. 队列中有效的数据的个数 (rear + maxSize – front) % maxSize
6. 我们就可以得到一个环形队列

• 代码实现

 public class ArrayQueueDemo {
  public static void main(String[] args) {
      System.out.println("测试数组模拟环形队列的案例");
      //创建一个队列
      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 val = scanner.nextInt();
                  queue.addQueue(val);
                  break;
              case 'g':
                  try {
                      int res = queue.getQueue();
                      System.out.printf("取出的数据是%dn",res);
                  }catch (Exception e){
                      System.out.println(e.getMessage());
                  }
                  break;
              case 'h':
                  try {
                      int res = queue.headQueue();
                      System.out.printf("队列头的数据是%dn",res);
                  }catch (Exception e){
                      System.out.println(e.getMessage());
                  }
                  break;
              case 'e':
                  scanner.close();
                  loop = false;
                  break;
              default:
                  break;
          }
      }
  }
}

class CircleArray{
   private  int maxSize; //表示数组的最大容量
  private int front; //初始值0 指向队列的第一个元素
  private int rear; //初始值0 指向队列的最后一个元素的后一个位置
  private int[] arr; //该数组用于存放数据，模拟队列

  public CircleArray(int arrMaxSize){
      maxSize = arrMaxSize;
      arr = new int[maxSize];
  }

  //判断队列数据是否已满
  public boolean isFull(){
      //利用队列尾指针 + 1 % 数组长度的值 与 队列头指针是否在同一下标判断队列数据是否已满
      return (rear + 1) % maxSize == front;
  }

  //判断队列是否为空
  public boolean isEmpty(){
      return rear == front;
  }

  //添加数据到队列
  public void addQueue(int n){
      //判断队列是否满
      if (isFull()){
          System.out.println("队列已满，不能加入数据");
          return;
      }
      //直接将数据加入
      arr[rear] = n;
      //重新设置 尾指针 的指向——后移
      rear = (rear + 1) % maxSize;
  }

  //获取队列的数据出列
  public int getQueue(){
      //判断队列是否为空
      if(isEmpty()){
          throw new RuntimeException("队列空，不能取数据");
      }
      int value = arr[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("arr[%d]=%dn",i % maxSize,arr[i % maxSize]);
      }
  }

  //求出当前队列有效数据的个数
  public int size(){
      //rear 2
      //front 1
      //maxSize 3
      return (rear + maxSize - front) % maxSize;
  }

  //显示队列的头数据
  public int headQueue(){
      if(isEmpty()){
          throw new RuntimeException("队列空的，没有数据");
      }
      return arr[front];
  }
}