稀疏数组与队列

1、前言

1.1 数据结构和算法的重要性

算法是程序的灵魂，优秀的程序可以在海量数据计算时，依然保持高速计算。

一般来讲 程序会使用了内存计算框架(比如Spark)和缓存技术(比如Redis等)来优化程序,再深入的思考一下，这些计算框架和缓存技术， 它的核心功能是哪个部分呢？

拿实际工作经历来说, 在Unix下开发服务器程序，功能是要支持上千万人同时在线， 在上线前，做内测，一切OK,可上线后，服务器就支撑不住了, 公司的CTO对代码进行优化，再次上线，坚如磐石。你就能感受到程序是有灵魂的，就是算法。

目前程序员面试的门槛越来越高，很多一线IT公司(大厂)，都会有数据结构和算法面试题(负责的告诉你，肯定有的)。

如果你不想永远都是代码工人,那就花时间来研究下数据结构和算法。

1.2 数据结构和算法的关系

数据data结构(structure)是一门研究组织数据方式的学科，有了编程语言也就有了数据结构.学好数据结构可以编写出更加漂亮,更加有效率的代码。
要学习好数据结构就要多多考虑如何将生活中遇到的问题,用程序去实现解决。
程序 = 数据结构 + 算法
数据结构是算法的基础, 换言之，想要学好算法，需要把数据结构学到位

1.3 数据结构的基本结构

线性结构和非线性结构
数据结构包括：线性结构和非线性结构。

线性结构

• 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。
• 线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。
  - 顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的。
  - 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。
• 线性结构常见的有：数组、队列、链表和栈，后面会详细叙述。

非线性结构

非线性结构包括：二维数组，多维数组，广义表，树结构，图结构。

2、稀疏数组

2.1 稀疏数组的应用场景

先看一个实际的需求

​ 1. 编写的五子棋程序中，有存盘退出和续上盘的功能。

分析问题:
因为该二维数组的很多值是默认值0, 因此记录了很多没有意义的数据.->稀疏数组。

2.2 稀疏数组的介绍和说明

2.2.1 稀疏数组基本介绍

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

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

2.2.2 稀疏数组举例说明

2.3 二维数组转稀疏数组过程

1. 将原始稀疏数组用二维数组存储，需要n行m列的数组,记录n*m个数据;
2. 如果使用稀疏数组存储,在稀疏数组的
   2.1 第一行第一列记录原始数组总行数,
   2.2 第一行第二列记录原始数组的总列数
   2.3 第一行第三列记录原始数组非零值的个数,
3. 在稀疏数组的第二行开始的每一行分别记录每一个非零值的行值、列值、具体数据大小,
4. 使用稀疏数组即可将原始数组由n行n列n*m个值的二维数组, 转换为一个空间较小的二维数组。

2.4 稀疏数组转换的思路分析及实现

应用实例

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

1、二维数组 转 稀疏数组的思路

1. 遍历 原始的二维数组，得到有效数据的个数 sum
2. 根据sum 就可以创建 稀疏数组 sparseArr int[sum+1] [3]
3. 将二维数组的有效数据数据存入到 稀疏数组 (稀疏数组每行分别记录原始数组 行、列、值)

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

1. 先读取稀疏数组的第一行，根据第一行的数据,创建原始的二维数组，如图的 chessArr2 = int [11][11]
2. 在读取稀疏数组后几行的数据，并赋给原始的二维数组,即可.

public class sparseArray {
    public static void main(String[] args) {
        /*棋盘稀疏数组压缩保存
        1.创建8*8棋盘*/
        int chessArray[][]=new int[8][8];
        chessArray[2][2]=1;//黑棋
        chessArray[3][3]=1;
        chessArray[4][4]=1;
        chessArray[2][3]=2;//白棋
        chessArray[2][4]=2;
        chessArray[3][4]=2;

        int sum=0;
        //打印且遍历二维数组
        System.out.println("原始数组"+chessArray.length+"*"+chessArray[0].length);
        for (int[] row:chessArray){
            for (int data: row){
                if (data != 0) { sum++; }
                System.out.print(data+"\t");
            }
            System.out.println();
        }
        System.out.println("棋子的数量："+sum);//有棋子的数量

        //创建稀疏数组且为其第一行赋初值
        int sparseArray1[][]=new int[sum+1][3];
        sparseArray1[0][0]=8;//行
        sparseArray1[0][1]=8;//列
        sparseArray1[0][2]=sum;//个数

        //遍历二维数组，将非0数值存放到sparArray1中
        //原始数组 转 稀疏数组
        int count=0;
        for (int i=0;i<8;i++){
            for (int j=0;j<8;j++){
                if (chessArray[i][j]!=0){
                    count++; //count记录行数
                    sparseArray1[count][0]=i;
                    sparseArray1[count][1]=j;
                    sparseArray1[count][2]=chessArray[i][j];
                }
            }
        }

        System.out.println("稀疏数组");
        for (int[] row:sparseArray1){
            for (int data: row){
                System.out.print(data+"\t");
            }
            System.out.println();
        }

        //稀疏数组 转棋盘数组
        int r=sparseArray1[0][0];
        int c= sparseArray1[0][1];
        int chessArray2[][]=new int[r][c];//根据第一行的值创建原始数组大小

        for (int i=1;i<sum+1;i++){ //分别读取稀疏数组数据 赋值给 原始数组
                int row,col;
                row=sparseArray1[i][0];
                col=sparseArray1[i][1];
               chessArray2[row][col]=sparseArray1[i][2];
        }
        /*for (int i=1;i<sparseArray1.length;i++){
            chessArray2[sparseArray1[i][0]][sparseArray1[i][1]]=sparseArray1[i][2];
        }*/
        System.out.println("原始数组");
        sparseArray.print(chessArray2);

    }

    //打印棋盘
    public static void print(int Array[][]){
        for (int i=0;i<Array.length;i++){
            for (int j=0;j<Array[0].length;j++){
                System.out.print(Array[i][j]+"\t");
            }
            System.out.println();
        }
    }
}

3、队列

3.1 队列的应用场景和介绍

队列的一个使用场景
排队打饭、高速收费站出入口，单向隧道行驶

• 银行排队的案例:
  

3.1.1队列介绍

• 队列是一个有序列表，可以用数组或是链表来实现。

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

示意图：(使用数组模拟队列示意图)

队列初始的情况

1. Queue–>代表类Queue
2. rear -->代表队尾，初始化为-1
3. front–>代表队首，初始化为-1
4. MaxSize-1–>队列的最大容量(从0开始计数，需减一)

图二：向队列增加数据的情况

• 当数据增加时rear变大，front不变

图三：从队列取数据的情况

• 当数据取出时front变大，rear不变

3.2 数组模拟队列的思路分析及实现

3.2.1 数组模拟队列

• 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。

• 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而 rear则是随着数据输入而改变，
  如图所示:

3.2.1 数组添加队列思路分析

当我们将数据入队列、出队列时 的处理需要有两个步骤：

入队列

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

public class ArrayQueue {
    public static void main(String[] args) {
       Queue q= new Queue(3);
        char key=' ';
        Scanner sc=new Scanner(System.in);
        while (true){
            System.out.print("s(show):显示队列");
            System.out.print("a(add):添加队列");
            System.out.print("g(get):取出数据");
            System.out.print("h(head):查看队列头部");
            System.out.print("e(eixt):退出程序");
            key=sc.next().charAt(0);
            switch (key){
                case 's':
                    q.showQueue();
                    break;
                case 'a':
                    System.out.println("请输入一个数");
                    int value=sc.nextInt();
                    q.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res=q.getQueue();
                        System.out.println("取出的数据是"+res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                 case 'h':
                     try {
                         int head=q.headQueue();
                         System.out.println("头数据是"+head);
                     }catch (Exception e){
                         System.out.println(e.getMessage());
                     }
                    break;
                case 'e':
                    System.exit(0);
                default:
                    break;

            }
        }
    }
}

class Queue{
    private int maxSize;
    private  int front;
    private  int rear;
    private int[] arr;

    //创建队列构造器
    public Queue(int arrMaxSize){
        maxSize=arrMaxSize;
        arr=new int[maxSize];
        front=-1;//指向队列头部，队列头前一个位置
        rear=-1;//指向队列尾部，队列尾的位置
    }
    //判断队列满
    public boolean isFull(){
        return rear==maxSize-1;
    }
    //判断队列空
    public boolean isEmpty(){
        return front==rear;
    }
    //添加队列
    public void addQueue(int n){
        if(isFull()){
            System.out.println("队列已满，不能添加数据");
            return;
        }
        rear++;
        arr[rear]=n;
    }
    //获取队列数据 出队列
    public int getQueue(){
        if (isEmpty()){
            throw  new RuntimeException("队列空");
        }
        front++;
        return arr[front];
    }
    //显示队列数据
    public void showQueue(){
        if(isEmpty()){
            System.out.println("队列空");
            return;
        }
        /*for (int i =0; i <arr.length; i++) {
            if(arr[i]!=0){
                System.out.println("arr["+i+"]="+arr[i]);
            }
        }*/
        for (int i =front; i <= rear; i++) {
                System.out.println("arr["+i+"]="+arr[i]);
        }
    }
    //显示队列头数据
    public int headQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列空，没有数据");
        }
        return arr[front+1];

    }

}

问题分析并优化

1. 目前数组使用一次就不能用，无法达到复用的效果；

2. 将这个数组使用算法，改进成一个环形的队列取模：%

具体如下：

4、环形队列

4.1 数组模拟环形队列思路分析

对前面的数组模拟队列的优化，充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可)

分析说明：

• 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,
  这个在做判断队列满的时候需要注意 (rear + 1) % maxSize == front 满]

• rear == front [空]

• 测试示意图：

思路如下:

1. front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 front 的初始值 = 0
2. rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定. rear 的初始值 = 0
3. 当队列满时，条件是 (rear + 1) % maxSize == front 【满】
4. 对队列为空的条件， rear == front 空
5. 当我们这样分析， 队列中有效的数据的个数 (rear + maxSize - front) % maxSize // rear = 1 front = 0
6. 综上，就可以在原来的队列上修改得到，一个环形队列。

4.2 数组模拟环形队列及实现

public class CirckeQueue {
    public static void main(String[] args) {
        CircleArray q= new CircleArray(4);//有效数据是3
        char key=' ';
        Scanner sc=new Scanner(System.in);
        while (true){
            System.out.print("s(show):显示队列");
            System.out.print("a(add):添加队列");
            System.out.print("g(get):取出数据");
            System.out.print("h(head):查看队列头部");
            System.out.print("e(eixt):退出程序");
            key=sc.next().charAt(0);
            switch (key){
                case 's':
                    q.showQueue();
                    break;
                case 'a':
                    System.out.println("请输入一个数");
                    int value=sc.nextInt();
                    q.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res=q.getQueue();
                        System.out.println("取出的数据是"+res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int head=q.headQueue();
                        System.out.println("头数据是"+head);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    System.out.println("程序退出");
                    System.exit(0);
                default:
                    break;

            }
        }

    }
}

class CircleArray{
    private int maxSize;
    private  int front; // front 的初始值为0 front 队列头,front 就指向队列的第一个元素
    private  int rear;//rear 的初始值 = 0 队列尾,rear指向队列的最后一个元素的后一个位置
    private int[] arr;


    //创建队列构造器
    public CircleArray(int arrMaxSize){
        maxSize=arrMaxSize;
        arr=new int[maxSize];
        front=0;//指向队列头部，队列头的位置
        rear=0;//指向队列尾部，队列尾后一个位置
    }
    //判断队列满
    public boolean isFull(){
        return (rear+1)%maxSize==front;
    }
    //判断队列空
    public boolean isEmpty(){
        return front==rear;
    }
    //添加队列
    public void addQueue(int n){
        if(isFull()){
            System.out.println("队列已满");
            return;
        }
        arr[rear]=n;//直接加入
        rear=(rear+1)%maxSize;//rear后移需考虑取模
    }
    //获取队列数据 出队列
    public int getQueue(){
        if (isEmpty()){
            throw  new RuntimeException("队列空");
        }
        int temp=arr[front];
        front=(front+1)%maxSize;
        return temp;
    }
    //显示队列数据
    public void showQueue(){
        if(isEmpty()){
            System.out.println("队列空，没有数据");
            return;
        }
        for (int i =front; i <front+size(); i++) {
                System.out.println("arr["+i%maxSize+"]="+arr[i % maxSize]);
        }
    }
    //求出队列有效数据
    public int size(){
        return (rear+maxSize-front)%maxSize;
    }
    //显示队列头数据
    public int headQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列空.....");
        }
        return arr[front];

    }

}