Java数据结构--稀疏数组和队列

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

这里写目录标题

前言
初始Java数据结构

线性结构
非线性结构

什么是稀疏数组？
稀疏数组实例
队列

改进前
改进后（循环队列）

前言

这个月更新Java版本的数据结构
再次巩固下Java基础，多写一些优质的代码
文章参考尚硅谷Java数据结构

初始Java数据结构

程序=数据结构+算法
数据结构是算法的基础,换言之，想要学好算法，需要把数据结构学到位。

线性结构

1)线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系

2)线性结构有两种不同的存储结构，即顺序存储结构(数组)和链式存储结构(链表)。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的

3)链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息

4)线性结构常见的有:数组、队列、链表和栈

非线性结构

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

什么是稀疏数组？

当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:
1)记录数组一共有几行几列，有多少个不同的值
2)把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

稀疏数组实例

Java数据结构--稀疏数组和队列_链表

使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)

把稀疏数组存盘，并且可以从新恢复原来的二维数组数

队列

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

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

Java数据结构--稀疏数组和队列_数据结构_02

return语句主要有两个用途：一方面用来表示一个方法返回的值，另一方面是指它导致该方法退出，并返回那个值。

Java数据结构--稀疏数组和队列_数据结构_03

改进前

当我们将数据存入队列时称为”addQueue”, addQueue的处理需要有两个步骤:思路分析
1)将尾指针往后移: rear+1 ，当front == rear[空]
2)若尾指针rear小于队列的最大下标 maxSize-1,则将数据存入rear所指的数组元素中,否则无法存入数据。rear==maxSize - 1[队列满]

package com.caq.java;

import org.junit.Test;

import java.util.Scanner;

/**
 * 使用数组模拟队列--编写一个ArrayQueue类
 *
 * @Date 2021/12/7 15:18
 * @Version 1.0
 */
public class ArrayQueueDemo {

    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("Please input s、e、a、g、h");
            System.out.println("s显示队列");
            System.out.println("e退出程序");
            System.out.println("a添加数据");
            System.out.println("g取出数据");
            System.out.println("h查看队列头的数据");
            key = scanner.next().charAt(0);//next()不能得到带有空格的字符
            switch (key){
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("输出一个数");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int queue1 = queue.getQueue();
                        System.out.println("取出的数据是:"+queue1);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                        //如果队列为空，则出现异常，和我们前面写的方法中的抛出异常消息对应
                        // 返回此throwable的详细消息字符串
                        // 我们只需要对它进行打印即可
                    }
                    break;
                case 'h':
                    try {
                        int res = queue.headQueue();
                        System.out.println("队列头的数据是："+ res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                        //如果队列为空，则出现异常，和我们前面写的方法中的抛出异常消息对应
                        // 返回此throwable的详细消息字符串
                        // 打印的是headQueue()方法可能出现的异常
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }

//    @Test
//    public void test2() {
//        int[] ints = new int[5];
//        ints[0] = 1;
//        ints[1] = 2;
//        ints[2] = 2;
//        for (int i : ints) {
//            System.out.println(i);
//        }
//    }

}

class ArrayQueue {
    private int maxSize;//表示数组的最大容量
    private int front;//队列头
    private int rear;//队列尾
    private int[] arr;//模拟队列

    //判断队列是否满
    public boolean isFull() {
        return rear == maxSize - 1;
    }

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

    //创建队列的构造器
    public ArrayQueue(int arrMaxSize) {
        this.maxSize = arrMaxSize;
        this.arr = new int[maxSize];
        front = -1; //指向队列头部，分析出front是指向队列头的前一个位置
        rear = -1;  //指向队列尾，指向列尾的数据（既就是队列最后一个数据）
    }



    //添加数据到队列
    public void addQueue(int n) {
        //判断队列是否满
        if (isFull()) {
            System.out.println("队列满，不能加入数据！");
            return;
        }
        rear++;
        arr[rear] = n;
    }

    //获取队列的数据，出队列
    public int getQueue() {
        //判断队列是否为空
        if (isEmpty()) {
            //通过抛出异常
            throw new RuntimeException("队列空，不能取数据");
        }
        front++;  //front后移
        return arr[front];
    }

    //显示队列的所有数据
    public void showQueue() {
        //遍历
        if (isEmpty()) {
            System.out.println("队列空的，没用数据");
            return;
        }
        for (int i : arr) {
            System.out.println(i);
        }
    }

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

改进后（循环队列）

目前数组使用一次就不能用，没有达到复用的效果

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

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

2）rear == front[空]

思路如下：

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

上面的第5项其实很简单，我们只需要多带进去几个数，然后脑中想象几钟情况就可以

Java数据结构--稀疏数组和队列_链表_04

package com.caq.java;

import org.junit.Test;

import java.util.Scanner;

/**
 * 循环队列的实现（数组）
 *
 * @Date 2021/12/8 11:16
 * @Version 1.0
 */
public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        //创建环形队列
        CircleArray circleArray = new CircleArray(3);
        Scanner sc = new Scanner(System.in);
        boolean loop = true;
        char key = ' ';
        while (loop) {
            System.out.println("Please input s、e、a、g、h");
            System.out.println("s显示队列");
            System.out.println("e退出程序");
            System.out.println("a添加数据");
            System.out.println("g取出数据");
            System.out.println("h查看队列头的数据");
            key = sc.next().charAt(0);

            switch (key) {
                case 's':
                    circleArray.showQueue();
                    break;
                case 'e':
                    sc.close();
                    loop = false;
                    break;
                case 'a':
                    System.out.println("请输入你要添加的数：");
                    int a = sc.nextInt();
                    circleArray.addQueue(a);
                    break;
                case 'g':
                    try {
                        int queue = circleArray.getQueue();
                        System.out.println("取出的数是" + queue);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int i = circleArray.headQueue();
                        System.out.println("头数据为：" + i);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                default:
                    break;
            }
        }
    }

}


class CircleArray {
    private int maxSize;//表示数组的最大容量
    /**
     * 1. front变量的含义做一个调整:front就指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素front的初始值=0
     * 2. rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置.因为希望空出一个空间做为约定.rear的初始值=0
     */
    private int front;//队列头
    private int rear;//队列尾
    private int[] arr;//模拟队列

    //初始化数组
    public CircleArray(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
    }

    //判断是否为满
    public boolean isFull() {
        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("队列空，不能取数据");
        }
        /**
         这里需要分析出front是指向队列的第一个元素
         1.先把front对应的值保留到一个临时变量
         2.将front后移,考虑取模
         3.将临时保存的变量返回
         */
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;
    }

    //显示队列的所有数据
    public void showQueue() {
        //遍历
        if (isEmpty()) {
            System.out.println("队列空的，没用数据");
            return;
        }

        for (int i = front; i < front + size(); i++) {
            System.out.println("arr" + "[" + i + "]" + "=" + arr[i % maxSize]);
        }
    }

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

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

Please input s、e、a、g、h
s显示队列
e退出程序
a添加数据
g取出数据
h查看队列头的数据
a
请输入你要添加的数：
1
Please input s、e、a、g、h
s显示队列
e退出程序
a添加数据
g取出数据
h查看队列头的数据
a
请输入你要添加的数：
2
Please input s、e、a、g、h
s显示队列
e退出程序
a添加数据
g取出数据
h查看队列头的数据
s
arr[0]=1
arr[1]=2
Please input s、e、a、g、h
s显示队列
e退出程序
a添加数据
g取出数据
h查看队列头的数据
a
请输入你要添加的数：
3
队列满了，不能添加了
Please input s、e、a、g、h
s显示队列
e退出程序
a添加数据
g取出数据
h查看队列头的数据
g
取出的数是1
Please input s、e、a、g、h
s显示队列
e退出程序
a添加数据
g取出数据
h查看队列头的数据
s
arr[1]=2
Please input s、e、a、g、h
s显示队列
e退出程序
a添加数据
g取出数据
h查看队列头的数据
a
请输入你要添加的数：
3
Please input s、e、a、g、h
s显示队列
e退出程序
a添加数据
g取出数据
h查看队列头的数据
s
arr[1]=2
arr[2]=3
Please input s、e、a、g、h
s显示队列
e退出程序
a添加数据
g取出数据
h查看队列头的数据
g
取出的数是2
Please input s、e、a、g、h
s显示队列
e退出程序
a添加数据
g取出数据
h查看队列头的数据
g
取出的数是3
Please input s、e、a、g、h
s显示队列
e退出程序
a添加数据
g取出数据
h查看队列头的数据
a
请输入你要添加的数：
5
Please input s、e、a、g、h
s显示队列
e退出程序
a添加数据
g取出数据
h查看队列头的数据
a
请输入你要添加的数：
6
Please input s、e、a、g、h
s显示队列
e退出程序
a添加数据
g取出数据
h查看队列头的数据
s
arr[0]=5
arr[1]=6
Please input s、e、a、g、h
s显示队列
e退出程序
a添加数据
g取出数据
h查看队列头的数据
e

Process finished with exit code 0