数据结构笔记

文章目录

- 第一章：数据结构与算法
- 第二章：稀疏数组和队列
- - 一、稀疏sparsearray 数组
  - - （一）案例需求
    - （二）稀疏数组介绍
  - （三）应用实列
  - （四）代码实现
  - 二、队列
  - - （一）数组模拟队列
    - - 代码实现
    - （二）数组模拟环形队列
- 第三章：链表
- - 一、链表
  - - （一）链表介绍
    - - 单链表的应用实例
      - 代码实现
    - （二）面试题
  - 二、双链表
  - - （一）、双向链表的介绍
    - (二) 、应用案例
  - 三、单向环形链表应用场景
  - - （一）约瑟夫问题
    - （二）代码实现
- 第四章：栈
- 第五章：递归
- 第六章：排序算法

第一章：数据结构与算法

一、数据结构概述

数据结构包括：

线性结构：数据元素之间存在的一对一的线性关系
- 两种不同存储结构:
  - 顺序存储结构 （使用顺序表，顺序表中存储的元素是连续的，即存储的位置是连续的）
  - 链式存储结构（使用链式表，存储数据不一定是连续的，好处：利用磁盘的碎片化的空间）
- 常见结构：数组、队列、链表和栈
非线性结构：数据元素之间不一定是一对一的关系
- 常用：二位数组、多维数组、广义表、树结构、图结构

第二章：稀疏数组和队列

一、稀疏sparsearray 数组

（一）案例需求

案例：五子棋的数据的存盘和继续上次棋盘

主要解决：其盘数据的存放问题

如果用二维数组进行连续存储数据，会记录很多无意义的数据

解决办法：稀疏数组，来压缩二维数组

在这里插入图片描述

（二）稀疏数组介绍

稀疏数组适用范围：

数组中大部分的元素为0
元素为同一个值

稀疏数组处理方法：

记录数组一共几列几行、不同值的个数
不同的元素的行、列、值记录在稀疏数组中

在这里插入图片描述

（三）应用实列

稀疏数组，可以用来保存二维数组（eg：棋盘、地图等）

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

遍历二维数组，得到有效数据的个数 sum （即：知道列的个数，而行的个数是固定的3）
根据sum就可以创建稀疏数组spareseArr int[sum+1][3]
将二维数组的有效数据存入到稀疏数组

（第一行数据为：行个数、列个数、数据个数）

稀疏数组的形状：[数据个数+1,3]

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

先读取稀疏数组中第一行数据，来创建原始的二维数组
在读取稀疏数组中后几行的数据，并将值赋给二维数组中

（四）代码实现

创建DataStructures，创建package ：com.lcj.sparseArray,创建类：SparseArray

在这里插入图片描述

package com.lcj.sparseArray;
/*
* 编写时间：202208014
* 编写人员：lcj
* 编写目的：联系稀疏数组
* */
public class SparseAarray {
    public static void main(String[] args){
        // 1. 创建11*11的二维数组（棋盘）
        // 0 表示没有棋子，1表示黑棋，2表示蓝棋
        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;

        // 输出原始棋盘的数据
        for (int[] row:chessArr1){
            for (int data:row){
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
// __________________________________________________________________
        //(一)：二维数组转为稀疏数组
        // 1.先遍历二维数组，得到数据的个数 （稀疏数组 形状：[个数+1,3]）
        int count = 0;
        for(int i = 0;i < chessArr1.length;i++){
            for (int j=0;j < chessArr1[1].length;j++){
                if(chessArr1[i][j] != 0)
                    count++;
            }
        }
        System.out.println("数值的个数："+count);

        // 2.创建稀疏数组
        int sparseArray[][] = new int[count+1][3];
        // 第一行的数据
        sparseArray[0][0] = chessArr1.length;
        sparseArray[0][1] = chessArr1[1].length;
        sparseArray[0][2] = count;
        // 3.添加数值
        int a = 0; // 作用：统计不为零的数值的个数来确定，稀疏数组的行下标
        for(int i = 0;i < chessArr1.length;i++){
            for (int j=0;j < chessArr1[1].length;j++){
                if(chessArr1[i][j] != 0) {
                    a++;
                    sparseArray[a][0] = i; // 数据的行
                    sparseArray[a][1] = j; // 数据的列
                    sparseArray[a][2] = chessArr1[i][j]; // 数据值
                }
            }
        }

        // 4.输出稀疏数组
        for (int[] row : sparseArray) {
            for (int data : row) {
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
        // _____________________________________________________________________
    //（二）：稀疏数组转换为二维数组
        // 1.创建二维数组
        int chessArr2[][] = new int[sparseArray[0][0]][sparseArray[0][1]];
        //2.添加数值到二维数组中
        for (int i =1 ;i< sparseArray.length; i++){
            chessArr2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        // 3.输出二维数组
        for (int[] row : chessArr2) {
            for (int data : row) {
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }

    }
}

课后练习题：

在前面的基础上，将稀疏数组保存到磁盘中，eg：map.data
恢复原来的数组时，读取map.data进行恢复

二、队列

队列的特点：先进先出

实现方法：数组和链表

（一）数组模拟队列

在这里插入图片描述

加入数据【addQueue】的思路：

将尾指针往后移：rear+1，当front==rear [空]
若尾指针rear小于队列的最大值maxsize-1，可以将数据存入到队列中，如果等于maxsize-1，则无法进行存储数据

注意：

rear 指向队列中最后一个元素
front指向队列中第一个元素中前一个位置

代码实现

创建package：com.lcj.queue,创建类名：ArrayQueueDamon

package com.lcj.queue;

import java.util.Scanner;

/*
 * 编写时间：20220814
 * 编写人员：lcj
 * 编写目的：数组模拟队列
 * */
public class ArrayQueueDamon {
    public static void main(String[] args) {
        // 代码测试
        //创建对象
        arrayQueue Queue = new arrayQueue(3);  //最大值为3
        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 value = scanner.nextInt();
                    Queue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res = Queue.getQueu();
                        System.out.printf("取出数据：%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int res = Queue.headQueue();
                        System.out.printf("输入数据队列头部数据：%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }

                    break;
                case 'e':
                    scanner.close(); // 关闭scanner
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("退出成功");
    }
}

// 使用数组来模拟队列
class arrayQueue{
    private int maxsize; // 最大值
    private int rear;  // 队列的尾指针，
    private int front; // 队列的头指针，
    private int[] arr; // 存放数据

    // 创建队列的构造器
    public arrayQueue(int MaxSize){
        maxsize = MaxSize; // 最大值
        arr = new int[maxsize];
        rear = -1; // 指向队列尾部的数据，包含尾部数据
        front = -1; // 指向队列的头部的前一个位置，不包含尾部数据
    }

    // 判断队列是否满，满就不能插入数据，满就可以读取数据
    public boolean isFull(){
        return rear == maxsize-1;
    }

    // 判断队列是否为空，空就不能读取数据，空就能插入数据
    public boolean isEmpty(){
        return rear == front;
    }

    // 添加数据到队列
    public void addQueue(int n){
        // 判断队列是否满了
        if(isFull()){
            System.out.println("队列已经满了，不能添加数据");
            return;
        }
        rear++; // rear需要往后移动
        arr[rear] = n; //添加数据
    }

    // 获取队列的数据 （出队列）
    public int getQueu(){
        // 判断数据是否为空
        if(isEmpty()){
//            System.out.println("队列数据为空");
//            return 0;
            throw new RuntimeException("队列数据为空");
        }
        front++; //front数据后移
        return arr[front];
    }

    // 显示队列的所有数据
    public void showQueue(){
        // 判断队列是否为空
        if (isEmpty()){
//            throw new RuntimeException("队列数据为空，不能展示数据");
            System.out.println("队列数据为空，不能展示数据");
            return;
        }
        for (int i= front+1; i<=rear; i++){
            System.out.printf("arr[%d]=%d\n",i,arr[i]);
        }
    }

    //显示队列的头数据，注意不是取出数据
    public int headQueue(){
        //判断数据是否为空
        if (isEmpty()){
            throw new RuntimeException("数据为空");
        }
        return arr[front+1];
    }
}

注意：需要测试一下代码

问题：

当前这种形式的队列数据有问题，front往后移动后，front前面的数据虽然是无效数据，但是想要添加数据是无法再添加数据的，这导致资源的浪费了
队列不能重复使用，没有达到复用的效果

解决办法：

环形队列

（二）数组模拟环形队列

在这里插入图片描述

注意：

rear 变量的含义发生了变换，和数组模拟队列的不一样了，现在是指向最后一个元素的后一个位置
front 变量的含义也发生了变化，指向了队列的第一个元素，也就是说==arr[front] 的第一个元素位置==，原来是第一个元素前一个位置。
队列满的条件：(rear+1)%maxsize = front
队列为空：rear =front
队列中有效个数：(rear+maxsize-front)%maxsize

代码实现：

创建类：CircleArrayQueueDaemon

package com.lcj.queue;

import jdk.nashorn.internal.ir.CallNode;

import java.util.Scanner;

/*
* 编写人：lcj
* 编写时间：20220815
* 编写目的：学习环形队列
* */
public class CircleArrayQueueDaemon {
    public static void main(String[] args){
        //测试思考
        //创建对象
        CircleArray circleArray = new CircleArray(3);
        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):队列头部数据");
            System.out.println("n(num):队列有效数据");
            key = scanner.next().charAt(0);
            switch (key){
                case 's':
                    System.out.println("展示队列数据");
                    circleArray.showQueue();
                    break;
                case 'a':
                    System.out.println("添加数据,请输入数据");
                    int value = scanner.nextInt();
                    circleArray.addQueu(value);
                    break;
                case 'e':
                    System.out.println("退出程序");
                    loop = false; // 跳出循环
                    break;
                case 'g':
                    try {
                        System.out.println("获取队列的数据");
                        int num = circleArray.getQueue();
                        System.out.println("值："+num);
                    }catch (Exception e){
                        e.getMessage();
                    }

                    break;
                case 'h':
                    System.out.print("获取队列的头部数据:");
                    System.out.println(circleArray.getHead());
                    break;
                case 'n':
                    System.out.println("查看队列的有效数据" );
                    int size = circleArray.size();
                    System.out.println("有效数据为："+size);
                    break;
                default:
                    System.out.println("数据输入有误请重新输入");
                    break;
            }
        }
        System.out.println("程序已经退出成功");
    }
}
class CircleArray{
    private int maxsize;  // 队列长度
    private int front; // 队列的头
    private int rear; // 队列的尾
    private int[] arr; // 队列的数组

    // 创建构造器

    public CircleArray(int maxsize) {
        this.maxsize = maxsize;
        front = 0; // 指向元素第一位置
        rear = 0; // 指向元素的第二个位置，即 尾部序号+1
        arr = new int[maxsize];
    }
    // 判断是否满了
    public boolean isFull(){
        return (rear+1)%maxsize == front;
    }

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

    //添加数据，会不会添加数据导致覆盖原来的数据
    public void addQueu(int n){
        // 判断是否满
        if(isFull() && size()<maxsize){
            System.out.println("队列已满，不能添加数据");
            return;
        }
        arr[rear] = n;
//        rear++; // rear往后移动数据 erro:不能实现环形队列
        rear=(rear+1)%maxsize;// 注意：这里rear+1 == rear++
    }

    //取出数据
    public int getQueue(){
        //判断数据是否为空
        if(isEmpty()){
            throw new RuntimeException("数据为空，不能取数");
        }
        // 取出数据后，front需要往后移动，需要一个值来保存数据
        //方法一：
        int value = arr[front];
//        front++;
        front = (front+1)%maxsize; //front+1 = front++
        return value;
        //方法二：
//        front = (front+1)%maxsize;
//        return arr[(front-1)%maxsize];
    }

    // 获取数据头部
    public  int getHead(){
        return arr[front];
    }
    // 显示所有的数据
    public void showQueue(){
        //判断队列是否为空
        if(isEmpty()){
            System.out.println("队列为空");
            return;
        }
        //遍历数据,front+（rear-front+maxsize）%maxsize
        for (int i=front;i < front+(rear-front+maxsize)%maxsize;i++){        // (rear-front+maxsize)%maxsize 有效数据
            System.out.printf("arr[%d]=%d\n",i%maxsize,arr[i%maxsize]);
        }

    }

    // 数据有效个数
    public int size(){
        return (rear+maxsize-front)%maxsize;
    }

}

第三章：链表

一、链表

（一）链表介绍

链表是有序的列表

data域：数据

next域：地址

在这里插入图片描述

特点：

链表是以节点的方式来存储数据
每一个节点包含data域，next域（指向下一个节点）
链表中的数据并不一定是连续存放的
链表分为：
- 带头节点的链表（head节点：不存放具体的数据）
- 没有带头节点的链表

单链表的应用实例

eg：单链表来管理水浒传的人物图

实现：代头节点的单向链表

代码实现

创建package：linkedlist，创建类：SingleLinkedListDemo

要求一：添加英雄，直接添加到链表的尾部中

package com.lcj.linkedlist;

public class SignalLinkedList {
    public static void main(String[] args) {
        // 测试数据
        HeroNode hero1 = new HeroNode(1,"宋江","及时雨");
        HeroNode hero2 = new HeroNode(2,"宋江","及时雨");
        HeroNode hero3 = new HeroNode(3,"宋江","及时雨");

        // 创建链表管理器
        LinkedManager linkedManager = new LinkedManager();
        // 添加数据
        linkedManager.add(hero1);
        linkedManager.add(hero2);
        linkedManager.add(hero3);

        // 展示数据
        linkedManager.list();
    }

}

// 管理节点数据
class LinkedManager {
    //先创建一个头节点数据,但是并不存放数据
    private HeroNode head = new HeroNode(0, "", "");

    //添加节点到单链表中,但是数据需要添加到节点中的最后一个数据的Next为（Null）
    // 不考虑数据的编号
    public void add(HeroNode Node) {
        // 创建一个辅助指针来判断数据是否到达尾部
        HeroNode tmp = head;
        // 遍历循环
        while (true) {
            // 找最后节点数据
            if (tmp.next == null) {
                break;
            }
            // 如果没有找到最后一个节点，需要往后移动
            tmp = tmp.next;
        }
        // 退出循环的时候，就是指向最后节点，现在需要添加新的节点
        tmp.next = Node;
    }


    // 显示数据（遍历数据）
    public void list(){
        //判断链表是否为空,没有指向其他的节点
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        //头节点不能动，需要创建辅助节点遍历数据
        HeroNode tmp = head.next;
        while(true){
            //判断是否到达最后
            if(tmp == null){
//                System.out.println("最后的");
                break;
            }
            // 数据节点信息
            System.out.println(tmp);
            // 将tmp往后移动
            tmp = tmp.next;
        }
    }
}
// 创建节点数据
class HeroNode{
    public int no; // 创建序号
    public String name;//英雄名字
    public String nickname; // 昵称
    public HeroNode next; //指向下一个节点 ，值为java的引用，类似于c语言的指针

    //创建构造器

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }
// 数据进行格式，便于后期数据的展示
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

要求二：根据英雄的编号进行数据排序、修改节点值

添加数据

在这里插入图片描述

需要按照编号的顺序添加

首先找到新添加的节点位置
新的节点数据.next = tmp.next
tmp.next = 新节点

思路：

找到序号前一个位置
插入数据

//按照数据序号顺序进行添加数据
    public void addByOrder(HeroNode node){
       HeroNode tmp = head;
       // 查找序号位置时，tmp要指向插入数据的前一个位置，不是能插入数据
        boolean flag = false; // 判断需要的编号是否存在，存在就不能添加
        while(true){
            if(tmp.next == null){//找到数据链尾了
                break;
            }
            if (tmp.next.no > node.no){ //判断位置，成功就位置在tmp处

                break;
            }else if (tmp.next.no == node.no){ //说明编号存在
                flag = true;
                break;
            }
            tmp = tmp.next;
        }
        // 判断flag
        if(flag){
            System.out.println("序号存在，请重新输入数据");
        }else{

            node.next = tmp.next; //新节点的后序是tmp的后序
            tmp.next = node; // 旧节点的后序等于新节点
        }
    }

修改数据

// 修改节点的信息，根据no编号来修改，即no编号不能改
    // 根据node的no序号来进行修改
    public void update(HeroNode node){
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        //找需要修改的序号，因此需要进行遍历数据
        /* 版本一
        boolean flage = true;
        HeroNode tmp = head.next; // 创建临时的引用来遍历数据
        while (flage){
            if(tmp == null){ //到达链尾
                 break;
            }
            if (tmp.no == node.no){
                tmp.name = node.name;
                tmp.nickname = node.nickname;
                break;
            }else{
                tmp = tmp.next;

            }
        }

         */
        // 版本二
        boolean flage = false;
        HeroNode tmp = head.next; // 创建临时的引用来遍历数据
        while (true){
            if(tmp == null){ //到达链尾
                break;
            }
            if (tmp.no == node.no){
                flage = true;
                break;
            }else{
                tmp = tmp.next;

            }
        }
        // flage 为true会执行文件
        if(flage){
            tmp.name = node.name;
            tmp.nickname = node.nickname;
        }else{
            System.out.println("该节点数据没有找到");
        }
    }

删除节点

在这里插入图片描述

找到需要删除点的前一个点 tmp
tmp.next = tmp.next.next
被删除的节点，将不会有其引用指向，会被垃圾回收机制回收

// 删除节点
    //思路：找到需要删除点的前一个点 tmp；
    public void del(int no){
        HeroNode tmp = head;
        boolean flag = false;   // 标志是否找到待删除节点
        while(true){
            if(tmp.next == null){ // 位置处于数据的链尾
                break;
            }
            if(tmp.next.no == no){ //找到待删除节点的前一个节点的tmp
                flag = true;
                break;
            }
            tmp = tmp.next; //tmp后移，遍历
        }
        //判断flag
        if (flag){
            tmp.next = tmp.next.next;
        }else{
            System.out.println("该节点不存在");
        }
    }

完整代码

完整代码：添加数据（有序添加、排序添加）、修改数据、删除数据、

package com.lcj.linkedlist;

public class SignalLinkedList {
    public static void main(String[] args) {
        // 测试数据
        HeroNode hero1 = new HeroNode(1,"宋江","及时雨");
        HeroNode hero2 = new HeroNode(2,"宋江","及时雨");
        HeroNode hero3 = new HeroNode(3,"宋江","及时雨");

        // 创建链表管理器
        LinkedManager linkedManager = new LinkedManager();
        // 添加数据
//        linkedManager.add(hero1);
//        linkedManager.add(hero2);
//        linkedManager.add(hero3);

        //顺序添加数据

        linkedManager.addByOrder(hero3);
        linkedManager.addByOrder(hero2);
        linkedManager.addByOrder(hero1);

        // 展示数据
        linkedManager.list();

        System.out.println("======================================");
        // 修改节点数据
        HeroNode hero4 = new HeroNode(3,"法外张三","罗翔");
        linkedManager.update(hero4);
        linkedManager.list();// 展示数据


        // 删除节点
        linkedManager.del(1);
        System.out.println("==========删除数据后=========");
        linkedManager.list();
    }
}

// 管理节点数据
class LinkedManager {
    //先创建一个头节点数据,但是并不存放数据
    private HeroNode head = new HeroNode(0, "", "");

    //添加节点到单链表中,但是数据需要添加到节点中的最后一个数据的Next为（Null）
    // 不考虑数据的编号
    public void add(HeroNode Node) {
        // 创建一个辅助指针来判断数据是否到达尾部
        HeroNode tmp = head;
        // 遍历循环
        while (true) {
            // 找最后节点数据
            if (tmp.next == null) {
                break;
            }
            // 如果没有找到最后一个节点，需要往后移动
            tmp = tmp.next;
        }
        // 退出循环的时候，就是指向最后节点，现在需要添加新的节点
        tmp.next = Node;
    }
    // 修改节点的信息，根据no编号来修改，即no编号不能改
    // 根据node的no序号来进行修改
    public void update(HeroNode node){
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        //找需要修改的序号，因此需要进行遍历数据
        /* 版本一
        boolean flage = true;
        HeroNode tmp = head.next; // 创建临时的引用来遍历数据
        while (flage){
            if(tmp == null){ //到达链尾
                 break;
            }
            if (tmp.no == node.no){
                tmp.name = node.name;
                tmp.nickname = node.nickname;
                break;
            }else{
                tmp = tmp.next;

            }
        }

         */
        // 版本二
        boolean flage = false;
        HeroNode tmp = head.next; // 创建临时的引用来遍历数据
        while (true){
            if(tmp == null){ //到达链尾
                break;
            }
            if (tmp.no == node.no){
                flage = true;
                break;
            }else{
                tmp = tmp.next;

            }
        }
        // flage 为true会执行文件
        if(flage){
            tmp.name = node.name;
            tmp.nickname = node.nickname;
        }else{
            System.out.println("该节点数据没有找到");
        }
    }
    //按照数据序号顺序进行添加数据
    public void addByOrder(HeroNode node){
       HeroNode tmp = head;
       // 查找序号位置时，tmp要指向插入数据的前一个位置，不是能插入数据
        boolean flag = false; // 判断需要的编号是否存在，存在就不能添加
        while(true){
            if(tmp.next == null){//找到数据链尾了
                break;
            }
            if (tmp.next.no > node.no){ //判断位置，成功就位置在tmp处

                break;
            }else if (tmp.next.no == node.no){ //说明编号存在
                flag = true;
                break;
            }
            tmp = tmp.next;
        }
        // 判断flag
        if(flag){
            System.out.println("序号存在，请重新输入数据");
        }else{

            node.next = tmp.next; //新节点的后序是tmp的后序
            tmp.next = node; // 旧节点的后序等于新节点
        }
    }

    // 删除节点
    //思路：找到需要删除点的前一个点 tmp；
    public void del(int no){
        HeroNode tmp = head;
        boolean flag = false;   // 标志是否找到待删除节点
        while(true){
            if(tmp.next == null){ // 位置处于数据的链尾
                break;
            }
            if(tmp.next.no == no){ //找到待删除节点的前一个节点的tmp
                flag = true;
                break;
            }
            tmp = tmp.next; //tmp后移，遍历
        }
        //判断flag
        if (flag){
            tmp.next = tmp.next.next;
        }else{
            System.out.println("该节点不存在");
        }
    }

    // 显示数据（遍历数据）
    public void list(){
        //判断链表是否为空,没有指向其他的节点
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        //头节点不能动，需要创建辅助节点遍历数据
        HeroNode tmp = head.next;
        while(true){
            //判断是否到达最后
            if(tmp == null){
//                System.out.println("最后的");
                break;
            }
            // 数据节点信息
            System.out.println(tmp);
            // 将tmp往后移动
            tmp = tmp.next;
        }
    }
}
// 创建节点数据
class HeroNode{
    public int no; // 创建序号
    public String name;//英雄名字
    public String nickname; // 昵称
    public HeroNode next; //指向下一个节点 ，值为java的引用，类似于c语言的指针

    //创建构造器

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }
// 数据进行格式，便于后期数据的展示
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

（二）面试题

求单链表中有效节点的个数
查找单链表中的倒数第K个节点——新浪面试
单链表的反转 ——腾讯面试
从尾到头打印单链表——百度：要求（1）反向遍历（2）stack栈
合并两个有序的单链表，合并之后的链表依然有序

题一：求单链表中有效节点的个数

注意：不要将头节点也统计进去

    public void nodeNum(){
        HeroNode temp = head.next;
        int count=0;
        while(true){
            //如果到达链尾
            if(temp == null){
                break;
            }
            temp = temp.next;
            count++;
        }
        System.out.println("节点个数为："+count);
    }

题目二：查找单链表中的倒数第K个节点——新浪面试

思路：
- 先遍历一下数据，统计数据的有效个数
- 有效个数 - k，得到需要找的

public void findLastIndex(int k){
        HeroNode temp = head.next;
       	// 统计个数
    	int count=0;
        while(true){
            //如果到达链尾
            if(temp == null){
                break;
            }
            temp = temp.next;
            count++;
        }
    	// 判断k是否有效
    	if(k > count|| k<=0){
            System.out.println("超出了链表范围");
            return;
        }else{  //读取第k个值的位置
            int flag = count - k;
            HeroNode temp1 = head.next;
            for(int i=0;i<flag;i++){
               temp1 = temp1.next;
            }
            System.out.printf("序号：%d \t 名字：%s",temp1.no,temp1.name);
        }        
    }

注意：if(k > count|| k<=0)我遗漏了k<=0的问题

题目三：单链表的反转 ——腾讯面试

思路：（头插入数据）

新建一个链表，用来存储数据
将旧链表中的节点数据移动到新节点中
新链表指向旧链表的头

public static  void reversetList(HeroNode head){
        //判断链表是否为空,或者只有一个节点的，无需反转
        if (head.next == null || head.next.next ==null){
            return;
        }
        HeroNode tmp = head.next;
        HeroNode next = null;  //用来指向tmp的下一个节点数据
        HeroNode reversetHead = new HeroNode(0,"",""); //新链表的头节点数

        // 遍历链表,将旧链表中的节点数据移动到新节点中
        while(tmp != null){
            next = tmp.next ; //用于保存当前节点下一个节点数据
            tmp.next = reversetHead.next;
            reversetHead.next = tmp;
            tmp = next;  //往后移动
        }
        head.next = reversetHead.next;
    }

核心代码：

next = tmp.next ; //用于保存当前节点下一个节点数据
tmp.next = reversetHead.next;
reversetHead.next = tmp;
tmp = next; //往后移动

题目四：从尾到头打印单链表——百度：要求（1）反向遍历（2）stack栈

方法一：先将单链表进行反转操作，然后再遍历即可，但是不建议使用，破坏数据的原结构

方法二：利用栈将各个节点的数据压入到栈中，然后利用栈的先进后出特点

 //利用栈将各个节点的数据压入到栈中，然后利用栈的==先进后出==特点
    public static void reserverPrinter(HeroNode head){
        if(head.next == null){
            return;
        }
        Stack<HeroNode> stack = new Stack<>();
        HeroNode tmp = head.next;
        //数据入栈
        while (tmp != null){ //数据不能为空，为空代表到达链尾
            stack.push(tmp);//stack中添加数据push
            tmp = tmp.next;
        }

        //数据出栈
        while(stack.size()>0){
            System.out.println(stack.pop()); //pop 将数据弹出
        }
    }

题目五：合并两个有序的单链表，合并之后的链表依然有序

二、双链表

（一）、双向链表的介绍

在这里插入图片描述

双向链表添加了pre，目的：用它来指向节点的前一个节点

双向节点删除数据：

可以指向待删除的节点 temp
temp.pre.next = temp.next
temp.next.pre = temp.pre

单链表存在的问题：

单向链表查找的方向只能是一个方向，而双向链表可以向前或者向后查找
单向链表不能自我删除，需要靠辅助节点，而双向链表可以自我删除

(二) 、应用案例

实现英雄的案列

创建类：DoubleLinkedListDamon

package com.lcj.linkedlist;

public class DoubleLinkedListDaemon {
    public static void main(String[] args){

        HeroNode2 hero1 = new HeroNode2(1,"宋江","及时雨");
        HeroNode2 hero2 = new HeroNode2(8,"宋江","及时雨");
        HeroNode2 hero3 = new HeroNode2(3,"宋江","及时雨");

        //创建一个双向链表
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero3);

        //数据展示
        doubleLinkedList.list();

        // 数据修改
        System.out.println("==========数据修改============");
        HeroNode2 hero4 = new HeroNode2(3,"张三","及时雨");
        doubleLinkedList.update(hero4);
        doubleLinkedList.list();

        //数据删除
        System.out.println("==========数据删除==========");
        doubleLinkedList.del(3);
        doubleLinkedList.list();

        //添加数据
        System.out.println("===========添加数据=========");
        HeroNode2 hero5 = new HeroNode2(5,"lisi","李四");
        doubleLinkedList.add(hero5);
        doubleLinkedList.list();
    }
}
// 管理双向链表
class DoubleLinkedList{
    private HeroNode2 head = new HeroNode2(0,"","");
    // 显示数据（遍历数据）
    public void list(){
        //判断链表是否为空,没有指向其他的节点
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        //头节点不能动，需要创建辅助节点遍历数据
        HeroNode2 tmp = head.next;
        while(true){
            //判断是否到达最后
            if(tmp == null){
//                System.out.println("最后的");
                break;
            }
            // 数据节点信息
            System.out.println(tmp);
            // 将tmp往后移动
            tmp = tmp.next;
        }
    }

    //添加数据到链表的末尾
    //思路：找到链表末尾
    public void add(HeroNode2 Node) {
        // 创建一个辅助指针来判断数据是否到达尾部
        HeroNode2 tmp = head;
        // 遍历循环
        while (true) {
            // 找最后节点数据
            if (tmp.next == null) {
                break;
            }
            // 如果没有找到最后一个节点，需要往后移动
            tmp = tmp.next;
        }
        // 退出循环的时候，就是指向最后节点，现在需要添加新的节点，形成双向链
        tmp.next = Node;
        Node.pre = tmp;
    }

    //添加数据    要求：按照序号进行添加数据
    public void addByOrder(HeroNode2 node){
        HeroNode2 tmp = head;
        // 查找序号位置时，tmp要指向插入数据的前一个位置，不是能插入数据
        boolean flag = false; // 判断需要的编号是否存在，存在就不能添加
        while(true){
            if(tmp.next == null){//找到数据链尾了
                break;
            }
            if (tmp.next.no > node.no){ //判断位置，成功就位置在tmp处

                break;
            }else if (tmp.next.no == node.no){ //说明编号存在
                flag = true;
                break;
            }
            tmp = tmp.next;
        }
        // 判断flag
        if(flag){
            System.out.println("序号存在，请重新输入数据");
        }else{

            node.next = tmp.next; //新节点的后序是tmp的后序
            tmp.next = node; // 旧节点的后序等于新节点
        }
    }

    //修改节点内容
    //思路：主要是找到节点的位置
    // 根据node的no序号来进行修改，
    public void update(HeroNode2 node){
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        //找需要修改的序号，因此需要进行遍历数据
        /* 版本一
        boolean flage = true;
        HeroNode tmp = head.next; // 创建临时的引用来遍历数据
        while (flage){
            if(tmp == null){ //到达链尾
                 break;
            }
            if (tmp.no == node.no){
                tmp.name = node.name;
                tmp.nickname = node.nickname;
                break;
            }else{
                tmp = tmp.next;

            }
        }

         */
        // 版本二
        boolean flage = false;
        HeroNode2 tmp = head.next; // 创建临时的引用来遍历数据
        while (true){
            if(tmp == null){ //到达链尾
                break;
            }
            if (tmp.no == node.no){
                flage = true;
                break;
            }else{
                tmp = tmp.next;

            }
        }
        // flage 为true会执行文件
        if(flage){
            tmp.name = node.name;
            tmp.nickname = node.nickname;
        }else{
            System.out.println("该节点数据没有找到");
        }
    }

    //删除节点数
    // 只需要直接找到需要删除的节点，不需要像单链表一样找到前面的节点，再进行数据删除
    public void del(int no){

        //判断数据是否为空
        if(head.next == null){
            System.out.println("数据为空");
            return;
        }
        HeroNode2 tmp = head.next;
        boolean flag = false;   // 标志是否找到待删除节点
        while(true){
            if(tmp == null){ // 位置处于数据的链尾
                break;
            }
            if(tmp.no == no){ //找到待删除节点的前一个节点的tmp
                flag = true;
                break;
            }
            tmp = tmp.next; //tmp后移，遍历
        }
        //判断flag
        if (flag){
            tmp.pre.next = tmp.next;
            // 如果是最后一个节点，不需要执行这个，否则会出现空指针的问题
            if(tmp.next !=null) {
                tmp.next.pre = tmp.pre;
            }
        }else{
            System.out.println("该节点不存在");
class HeroNode2{
    public int no;
    public String name;
    public String nickname;
    public HeroNode2 next;  //指向下一个节点
    public HeroNode2 pre;  // 指向前一个节点

    public HeroNode2(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode2{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +

                '}';
    }

三、单向环形链表应用场景

（一）约瑟夫问题

在这里插入图片描述

人数 n=5

开始序号： k= 1

取出数据间隔 m=2

在这里插入图片描述

（二）代码实现

在这里插入图片描述

要求：

构建单向环形链表
- 创建第一个节点，通过first指向该节点，并形成环形
- 当每创建创建一个新的节点，将该节点加入到链表中
遍历环形链表
- 通过一个辅助指针 tmp ，指向first 节点
- 通过while循环进行统计，循环终止条件 tmp.next = first
创建出队列的编号序列
- 人数 n=5
  
  开始序号： k= 1
  
  取出数据间隔 m=2
- 创建辅助节点 helper，指向代删除的节点的前一个节点，注意起始位置位于环形列表的最后一个位置，报数自己也需要报一次
  
  补充：先将first 和helper 需要移动到k-1的位置
- 报数时，让first和helper 移动m-1次
- 删除节点：
  - first = first.next
  - per.next =first

创建类：Josephu

package com.lcj.linkedlist;
/*
* 编写目的：学习约瑟夫问题，了解单向环形链表
* 类似于丢手绢的游戏，只是固定了次数
* */
public class Joseph {
    public static void main(String[] args){
        // 测试
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
//        circleSingleLinkedList.addBoy(5);  // 创建5个节点
//        circleSingleLinkedList.showBody();

        //出圈测试
        int startNum = 2;
        int countNum = 2;
        int nums = 10;
        circleSingleLinkedList.addBoy(nums);
        circleSingleLinkedList.showBody();
        circleSingleLinkedList.countBoy(startNum,countNum,nums);
    }
}

//创建单向环形链表
class CircleSingleLinkedList{
    // 创建一个first节点，但是没有编号的
    private Boy first = null;

    //添加节点数据，构建成一个环形的链表
    // nums 的数量为 创建节点的个数
    public void addBoy(int nums){
        //判断nums 的个数
        if(nums < 1){
            System.out.println("输入nums的值不正确");
            return;
        }
        Boy curBoy = null; //辅助指针，帮助构建形式链表
        // 创建环形链表
        for (int i = 1; i <= nums ; i++) {
            Boy boy = new Boy(i);
            if (i==1){
                first = boy;
                first.setNext(first); // first 的后序是自己本身，这样才能构成环
                curBoy = first;
            }else{
                curBoy.setNext(boy); // 连接新的节
                boy.setNext(first); // 形成 环形
                curBoy = boy; //  将辅助节点往新的节点进行移动
            }

        }
    }

    // 遍历当前的环形链表
    public void showBody(){
        // 判断链表是否为空
        if(first == null){
            System.out.println("链表为空");
            return;
        }

        // 创建辅助节点
        Boy curBoy1 = first;
        while (true){
            System.out.printf("小朋友编号：%d\n", curBoy1.getNo());
            if (curBoy1.getNext() == first) {
                System.out.println("数据遍历完成");
                break;
            }
            curBoy1 = curBoy1.getNext();  //指针往后移动
        }
    }

/*
* startNo 是从第几个小孩开始数数
* countNum 间隔的人数
* nums 小孩人数
* */
    public void countBoy(int startNo,int countNum,int nums){
        if(first ==null || startNo <1 || startNo > nums){
            System.out.println("参数输入有误");
            return;
        }

        //创建一个辅助节点数据
        Boy helper = first;
        //将helper指向链尾，即first的前一个节点上，目的是便于删除数据
        while(true){
            if(helper.getNext() == first){ //判断helper是否到达链尾，主要是为了删除数据时，指向删除点的前一个位置
                break;
            }
            helper = helper.getNext();
        }
        // 将frist和helper的移动startNo-1的位置
        for (int i = 0; i < startNo-1; i++) {
            helper = helper.getNext();
            first = first.getNext();
        }
        // 小孩子报数，让first和helper移动countNum -1次，然后出圈（删除）
        while(true){
            if(helper == first){ // 只有一个数据，helper是在first前面的
                break;
            }
            //first和helper移动countNum -1次
            for (int i = 0; i < countNum-1; i++) {
                helper = helper.getNext();
                first = first.getNext();
            }
            //first指向节点
            System.out.printf("小孩%d出圈\n",first.getNo());
            // 删除数据
            first = first.getNext();
            helper.setNext(first);

        }
        System.out.printf("最后的节点为%d\n",first.getNo());
    }
}

//创建节点 ，名字为boy
class Boy{
    private int no; // 节点的编号
    private Boy next; // 指向下一个节点

    public Boy(int no){
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}

注意：只有一个节点可以自己指向自己

第四章：栈

在这里插入图片描述

（一）、栈介绍

栈是一种先进先出（first in last out）的有效列表
允许插入和删除的一端，为变化的一端，称为栈顶（Top），另一端固定为栈底（Bottom），

在这里插入图片描述

栈的应用

中缀表达式转后缀表达式 是面试中常考的

（二）数组模拟栈的思路分析

在这里插入图片描述

使用数组来模拟栈
定义一个top，来表示栈顶，初始化为-1
入栈的操作，当数据加入栈时，top++，stack[top]=data;
出栈的操作，int value = stack[top], top–

创建packe：com.lcj.Stack

创建class：ArrayStackDemo

package com.lcj.stack;

import com.sun.imageio.plugins.wbmp.WBMPImageReader;

import java.util.Scanner;

// 数组栈的学习
public class ArrayStackDamon {
    public static void main(String[] args){

        //数组栈测试
        ArrayStack stack = new ArrayStack(4);
        String key = "";  //输入的数据
        boolean loop = true;  //判断循环的条件
        Scanner scanner = new Scanner(System.in);
        // 测试菜单
        while(loop){
            System.out.println("输入exit:退出");
            System.out.println("输入push数据入栈");
            System.out.println("输入pop数据出栈");
            System.out.println("输入show 显示栈");
            key = scanner.next();
            switch (key){
                case "show":
                    stack.list();
                    break;
                case "push":
                    System.out.println("请输入需要插入的数据");
                    int value = scanner.nextInt();
                    stack.push(1);
                    break;
                case "exit":
                    System.out.println("退出");
                    loop = false;
                    break;
                case "pop":
                    System.out.println("数据出栈");
                    try{
                    	int v = stack.pop();
                        System.out.println("出栈的数值为"+v);
                    }catch(Exception e){
                         System.out.println(e.getMessage());
                    }
                    
                default:
                    break;
            }
        }
        System.out.println("退出成功");
    }
}

//栈
class ArrayStack{
    private int top = -1; //标记栈顶的位置
    private int maxSize;  //栈的最大长度
    private int stack[]; // 栈数组进行存储数据

    //构建器
    public ArrayStack(int maxSize){
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }

    //判断是否为空
    public boolean isEmpty(){
        return top==-1;
    }

    //判断是否栈满,即达到maxsize
    public boolean isFull(){
        return top == maxSize-1 ;// 注意：这点是从0开始计算的
    }

    //数据入栈
    public void push(int value){
        //判断是否栈满
        if (isFull()){
            System.out.println("栈满");
            return;
        }
        top++; // top指向的是有数据的栈顶
        stack[top] = value;
    }

    //数据出栈
    public int pop(){
        //判断数据是否为空
        if (isEmpty()){
            throw new RuntimeException("栈为空"); // 因为这点数据结果有类型，需要使用运行异常来解决
        }
        int value = stack[top];
        top--;
        return value;
    }

    // 遍历数据
    public void list(){
        //判断数据是否为空
        if (isEmpty()) {
            System.out.println("栈为空");
            return;
        }
        for (int i = top; i >= 0 ; i--) {
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }
    }
}

（三）练习：使用链表来模拟栈

思路一：双链表doubleLinked

创建双链表doubleLinked，两个指针：next、pre，栈顶指针：top
入栈：节点tmp 添加到链尾，前一个节点.next = tmp , 前一个节点的.next.pre = tmp
出栈：tmp.pre.next = null ,tmp.pre = null,
遍历数据

版本一：双链表实现栈

package com.lcj.stack;
/*
* 创建人：lcj
* 创建时间：2022年8月29
* 目的：用链表来实现栈
* */
public class LinkedStackDamon {
    public static void main(String[] args){
    //测试
        stack stack = new stack();
//        System.out.println(stack.topSite());  //测试topSite是否运行正常
        doubleLinked node1 = new doubleLinked(2);
        doubleLinked node2 = new doubleLinked(3);
        doubleLinked node3 = new doubleLinked(4);
        stack.add(node1);
        stack.add(node2);
        stack.add(node3);
        stack.show();
        stack.pop();
//        System.out.println(stack.topSite());
        stack.show();

    }
}

//stack
class stack{
    //创建一个first的头节点
   doubleLinked head =  new doubleLinked(1);

   //top 确定栈顶位置
    public doubleLinked topSite(){
        doubleLinked tmp = head; //创建一个辅助节点
        while (true){
            if(tmp.getNext() == null){

//                break;
//                System.out.println("1");
                return tmp;
            }
            tmp = tmp.getNext();  //往后移动
        }
    }
   //添加数据
    public void add(doubleLinked node){
        doubleLinked tmp = topSite(); //创建一个辅助节点
        tmp.setNext(node);  // 连接next
        tmp.getNext().setPre(tmp); // 将新节点的pre连接到前一节点上
//        System.out.println(tmp.getNext().getValue());
    }

    //展示数据
    public void show(){
        doubleLinked top = topSite();
        while(true){
            if (top.getPre()==null){ // 到达 head 之前
                break;
            }
            System.out.println(top.getValue());
            top = top.getPre(); //将辅助指针往前面进行移动
        }
    }
    //数据出栈
    public int pop(){
        doubleLinked top = topSite(); // 获得栈顶
        int value = top.getValue();
        top.getPre().setNext(null);
        top.setPre(null);
        System.out.println("删除");
        return value;
    }
}

// 用双链表来实现
class doubleLinked{
    private int value; // 链表中保存的值
    private doubleLinked next; //指向后序
    private doubleLinked pre; //指向前序
    private doubleLinked top; // 栈顶

    //构建对象
    public doubleLinked(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public doubleLinked getNext() {
        return next;
    }

    public void setNext(doubleLinked next) {
        this.next = next;
    }

    public doubleLinked getPre() {
        return pre;
    }

    public void setPre(doubleLinked pre) {
        this.pre = pre;
    }

    public doubleLinked getTop() {
        return top;
    }

    public void setTop(doubleLinked top) {
        this.top = top;
    }
}

版本二：双链表实现栈

package com.lcj.stack;
/*
* 创建人：lcj
* 创建时间：2022年8月29
* 目的：用链表来实现栈
* */
public class LinkedStackDamon {
    public static void main(String[] args){
    //测试
        stack stack = new stack();
//        System.out.println(stack.topSite());  //测试topSite是否运行正常
        doubleLinked node1 = new doubleLinked(2);
        doubleLinked node2 = new doubleLinked(3);
        doubleLinked node3 = new doubleLinked(4);
        stack.add(node1);
        stack.add(node2);
        stack.add(node3);
        stack.show();
        stack.pop();
//        System.out.println(stack.topSite());
        stack.show();

    }
}

//stack
class stack{
    //创建一个first的头节点
   doubleLinked head =  new doubleLinked(1);

   //top 确定栈顶位置
    public doubleLinked topSite(){
        doubleLinked tmp = head; //创建一个辅助节点
        while (true){
            if(tmp.next == null){

//                break;
//                System.out.println("top找到");
                return tmp;
            }
            tmp = tmp.next;  //往后移动
        }
    }
   //添加数据
    public void add(doubleLinked node){
        doubleLinked tmp = topSite(); //创建一个辅助节点
        tmp.next = node;  // 连接next
        tmp.next.pre = tmp; // 将新节点的pre连接到前一节点上
    }

    //展示数据
    public void show(){
        doubleLinked top = topSite();
        while(true){
            if (top.pre==null){ // 到达 head 之前
                break;
            }
            System.out.println(top.getValue());
            top = top.pre; //将辅助指针往前面进行移动
        }
    }
    //数据出栈
    public int pop(){
        doubleLinked top = topSite(); // 获得栈顶
        int value = top.getValue();
        top.pre.next = null;
        top.pre = null;
        System.out.println("删除");
        return value;
    }


}

// 用双链表来实现
class doubleLinked{
    public int value; // 链表中保存的值
    public doubleLinked next; //指向后序
    public doubleLinked pre; //指向前序
    public doubleLinked top; // 栈顶

    //构建对象
    public doubleLinked(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }
}

思想二：创建一个单链表

创建一个singalLinked
添加链表的数据tmp ：前一节点.next = tmp
数据出栈：
- 方法一：遍历数据，找到最后一个数据，缺点时间过长
- 方法二：将链表的反转，将数据出栈后，由反转回去
数据入栈：
- 思路一：直接找到链尾进行插入数据
注意：添加数据和数据出栈都需要，注意后面节点是否存在

版本三：单链表实现

package com.lcj.stack;
/*
 * 创建人：lcj
 * 创建时间：2022年8月29
 * 目的：用单链表来实现栈
 * */
public class SingalLinkedStackDaemon {
    public  static void main(String[] args){
        // 测试
        StackLinked stack1 = new StackLinked();

        //添加数据
        singalLinked Linked1 = new singalLinked(1);
        singalLinked Linked2 = new singalLinked(2);
        singalLinked Linked3 = new singalLinked(3);
        singalLinked Linked4 = new singalLinked(4);

        stack1.push(Linked1);
        stack1.push(Linked2);
        stack1.push(Linked3);
        stack1.push(Linked4);

        // 展示数据
        System.out.println("展示数据");
        stack1.show();

        //数据出栈
        System.out.println("数据出栈");
        try {
            stack1.pop();
            stack1.pop();
        }catch (Exception e){
            System.out.println(e.getMessage());
        }
        stack1.show();
    }
}

// 创建栈
class StackLinked{
    singalLinked head = new singalLinked(1); // 栈的头节点，需要保持不动
    //添加数据和数据出栈都需要，注意后面节点是否存在，即栈是否空的情况
    public boolean isEmpty(){
        return  head.next == null;
    }
    //数据入栈
    public  void push(singalLinked node){
        //判断链表是否空
        if (isEmpty()){
            head.next = node;  //直接将数据连接到node上，不需要连接后面的
            return;
        }
        // 链表为不空时
        node.next = head.next;  //  将后面连接
        head.next = node;  //将前面head连接
    }

    //数据出栈
    public int pop(){
        // 栈是否为空
        if (isEmpty()){
            throw  new RuntimeException("栈表为空");
        }
        // 栈只存在一个节点
        if (head.next.next == null ){
            head.next = null;
            return head.next.getValue();  // 返回被删除的值
        }
        int value = head.next.getValue();
        head.next = head.next.next;  // 将head连接删除的节点的后面一个
        return value;  // 返回被删除的值
    }

    //展示数据
    public void show(){
        singalLinked tmp = head;

        //判断是否空
        if (isEmpty()){
            System.out.println("栈为空");
            return;  //退出
        }
        while(true){

            //判断数据是否到达链尾
            if(tmp.next == null){
                break;
            }

            tmp = tmp.next; //往后移动
            System.out.printf("%d\n",tmp.getValue());

        }
    }
}

//创建单链表
class singalLinked{
    public int value; // value 是指栈中的值
    public singalLinked next;

    public singalLinked(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }
}

版本四：单链表实现，改变测试环境（推荐）

package com.lcj.stack;


import java.util.Scanner;

/*
 * 创建人：lcj
 * 创建时间：2022年8月29
 * 目的：用单链表来实现栈
 * */
public class SingalLinkedStackDaemon {
    public  static void main(String[] args){
        /*  测一
        // 测试
        StackLinked stack1 = new StackLinked();

        //添加数据
        singalLinked Linked1 = new singalLinked(1);
        singalLinked Linked2 = new singalLinked(2);
        singalLinked Linked3 = new singalLinked(3);
        singalLinked Linked4 = new singalLinked(4);

        stack1.push(Linked1);
        stack1.push(Linked2);
        stack1.push(Linked3);
        stack1.push(Linked4);

        // 展示数据
        System.out.println("展示数据");
        stack1.show();

        //数据出栈
        System.out.println("数据出栈");
        try {
            stack1.pop();
            stack1.pop();
        }catch (Exception e){
            System.out.println(e.getMessage());
        }
        stack1.show();

         */


        //测试二
        StackLinked stack1 = new StackLinked();

        boolean loop = true ; // 循环跳出的条件
        Scanner scanner = new Scanner(System.in);
        String key = ""; // 输入的关键字
        while(loop){
            System.out.println("输入exit退出");
            System.out.println("输入push数据入栈");
            System.out.println("输入pop数据出栈");
            System.out.println("输入show展示数据");
            key = scanner.next();
            switch (key){
                case  "exit":
                    System.out.println("退出");
                    loop = false;
                    break;
                case "push":
                    System.out.println("数据入栈");
                    System.out.println("请输入节点数据：");
                    int index = scanner.nextInt();
//                    singalLinked Linked = new singalLinked(index);
                    stack1.push(new singalLinked(index));
                    break;
                case "pop":
                    System.out.println("数据出栈");
                    int a = stack1.pop();
                    System.out.println("删除的值为："+a);
                    break;
                case "show":
                    System.out.println("展示数据");
                    stack1.show();
                    break;
                default:
                    System.out.println("输入有误");
                    break;
            }

        }
        System.out.println("退出成功");
    }
}

// 创建栈
class StackLinked{
    singalLinked head = new singalLinked(1); // 栈的头节点，需要保持不动
    //添加数据和数据出栈都需要，注意后面节点是否存在，即栈是否空的情况
    public boolean isEmpty(){
        return  head.next == null;
    }
    //数据入栈
    public  void push(singalLinked node){
        //判断链表是否空
        if (isEmpty()){
            head.next = node;  //直接将数据连接到node上，不需要连接后面的
            return;
        }
        // 链表为不空时
        node.next = head.next;  //  将后面连接
        head.next = node;  //将前面head连接
    }

    //数据出栈
    public int pop(){
        // 栈是否为空
        if (isEmpty()){
            throw  new RuntimeException("栈表为空");
        }
        // 栈只存在一个节点
        if (head.next.next == null ){
            head.next = null;
            return head.next.getValue();  // 返回被删除的值
        }
        int value = head.next.getValue();
        head.next = head.next.next;  // 将head连接删除的节点的后面一个
        return value;  // 返回被删除的值
    }

    //展示数据
    public void show(){
        singalLinked tmp = head;

        //判断是否空
        if (isEmpty()){
            System.out.println("栈为空");
            return;  //退出
        }
        while(true){

            //判断数据是否到达链尾
            if(tmp.next == null){
                break;
            }

            tmp = tmp.next; //往后移动
            System.out.printf("%d\n",tmp.getValue());

        }
    }
}

//创建单链表
class singalLinked{
    public int value; // value 是指栈中的值
    public singalLinked next;

    public singalLinked(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }
}

（四）栈实现综合案例——计算器

思路：创建两个栈，一个数栈 numStack（用于存储数值），一个符号栈 operStack（存储符号）

通过一个index来判断计算表达式中数值和符号
发现数值直接入数据栈
如果发现是符号，需要分两种情况：

3.1符号栈为空，直接添加到符号栈中

3.2符号栈已经存在了，需要判断待添加的符号和符号栈中栈顶的符号，比较优先级

3.2.1如果待入栈的符号大于栈顶的，则直接入栈

3.2.2如果待入栈的符号小于、等于栈顶的，则需要pop 两个数栈中的，与pop符号栈的中的符号进行计算，并将运算结果和待入栈的符号分别入栈
当计算表达式扫描完成后，就顺序从数据栈中和符号栈中pop出两个数值和符合，并将结果放进数据栈中
最后在数栈只有一个数字，即表达式的结果

注意：符号栈是更加栈顶特点：先进后出，因此将优先级高的后出。

创建class：calculatot

package com.lcj.stack;

import com.sun.deploy.security.SelectableSecurityManager;
import sun.font.DelegatingShape;

public class Calculator {
    public static void main(String[] args) {
        String expression = "3+2*6-2";

        //创建两个栈
        ArrayStack1 numStack = new ArrayStack1(20); //数栈
        ArrayStack1 operStack = new ArrayStack1(20); //符号栈

        //定义需要的相关变量
        int index = 0;  //用于扫描，表达式的
        int num1 = 0;
        int num2 = 0;
        int res = 0;
        int oper = 0;
        char ch = ' '; //符号保存到这里面的

        //通过while循环进行扫描表达式
        while (true){
            //依次得到expression的每一个字符
            ch = expression.substring(index,index+1).charAt(0);// substring(开始，结束)
            //判断ch的类型进行下一步的操作
            if(operStack.isOper(ch)){ //如果是运算符
                //1. 判断当前的符号栈是否为空，为空直接入栈
                if (!operStack.isEmpty()){
                    //2 如果待入栈的符号大于栈顶的，则直接入栈
                    //3 如果待入栈的符号小于、等于栈顶的
                    if (operStack.priority(ch) <= operStack.priority(operStack.peek())){
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        res = numStack.cal(num1,num2,oper);
                        //将结果入数栈
                        numStack.push(res);
                        //将符号入栈
                        operStack.push(ch);
                    } else {
                        operStack.push(ch);
                    }
                }else{ // 不为空
                    operStack.push(ch);
                }

            }else{  //数字直接入栈
                numStack.push(ch - 48); //注意：ch是字符串，在ASCII码中需要 - 48
            }
            //判断是否扫描完
            index++;
            if(expression.length() <= index){
                break;
            }
        }
        //当计算表达式扫描完成后，就**顺序从数据栈中和符号栈中pop出两个数值和符合**，并将结果放进数据栈中
        while (true){
            //判断是否计算完
            if(operStack.isEmpty()){
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = numStack.cal(num1,num2,oper);
            numStack.push(res);
        }
        System.out.println("结果为:"+numStack.pop());
    }
}
//栈
class ArrayStack1{
    private int top = -1; //标记栈顶的位置
    private int maxSize;  //栈的最大长度
    private int stack[]; // 栈数组进行存储数据

    //构建器
    public ArrayStack1(int maxSize){
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }

    //判断是否为空
    public boolean isEmpty(){
        return top==-1;
    } // top的初始位置为-1

    //判断是否栈满,即达到maxsize
    public boolean isFull(){
        return top == maxSize-1 ;// 注意：这点是从0开始计算的
    }

    //数据入栈
    public void push(int value){
        //判断是否栈满
        if (isFull()){
            System.out.println("栈满");
            return;
        }
        top++; // top指向的是有数据的栈顶
        stack[top] = value;
    }

    //数据出栈
    public int pop(){
        //判断数据是否为空
        if (isEmpty()){
            throw new RuntimeException("栈为空"); // 因为这点数据结果有类型，需要使用运行异常来解决
        }
        int value = stack[top];
        top--;
        return value;
    }

    // 遍历数据
    public void list(){
        //判断数据是否为空
        if (isEmpty()) {
            System.out.println("栈为空");
            return;
        }
        for (int i = top; i >= 0 ; i--) {
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }
    }

    //查看栈顶的值
    public int peek(){
        return stack[top];
    }
    // 符号的优先级，通过定义数值来表达符号的优先级，数值越大优先级越高
    // 目的直接将符号转换为成为数组，便于更好的进行比较优先级
    public int priority(int oper){  //oper 符号
        if(oper == '*' || oper == '/'){
            return 1;
        }else if (oper == '+' || oper == '-'){
            return 0;
        }else{
            return -1; //目前忽略了%、（）、[] 等符号
        }
    }

    //判断是否为运算符,好处：不用判断字符是否为数值
    public boolean isOper(char val){
        return val == '*' || val == '/' || val == '+' || val == '-';
    }

    //计算
    public int cal(int num1,int num2,int oper){
        int res = 0;// 返回的结果
        switch (oper){
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;  //注意有向后顺序，从栈最先出来是num1，最后出来的是num2
                break;
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;//注意有向后顺序，从栈最先出来是num1，最后出来的是num2
                break;
        }
        return res;
    }



}

缺点：只能计算数值为单个数据的，而不能计算数据为两位数的

（五）栈的三种表达式

前缀（波兰表达式）、中缀、后缀表达式（逆波兰表达式）

注意：中缀转后缀，再面试必问

前缀表达式相关知识

后缀表达式相关知识 ==>讲解了中缀表达式到后缀表达式

后缀表达式的计算

1、前缀表达式

又被称为波兰表达式，运算符位于操作数之前

eg：（3+4）x 5- 6 ==》前缀表达式：- x + 3 4 5 6

补充知识：

从右往左

2、后缀表达式

从左往右

在这里插入图片描述

注意：

通过两个栈: 符号栈s1（存储）、数据栈 s2来存储运算符和数值
从左至右扫描中缀表达式
遇到数值直接入栈s2
遇到操作符，需要分成以下情况：

4.1 如果s1为空时，直接将**符号入栈s1**中，或者为 ( 时，也是==直接入栈s2中==

4.2 不为空需要分成两种情况：

4.2.1 当待入栈的操作符，与栈顶的操作进行比较，栈顶操作符小于等于待入栈的操作符时，直接将待入栈的操作符直接入栈s1

4.2.2 当待入栈的操作符，与栈顶的操作进行比较，栈顶操作符大于等待入栈的操作符时，**需要将操作符中的栈pop出栈顶，并入栈到s2的中**

注意：待入栈还是需要和栈顶继续比较，如果待入栈大于符号栈栈顶的（满足4.2.1的条件），直接入栈。如果不满足还是需要执行4.2.2中

4.3 遇到左括号是直接入栈中，但是待入栈操作符为右括号时，需要将操作符栈的中的操作符pop出来，并pop出的操作符加入到s2中，一直都遇到操作符栈中的左操作符，停止pop。注意：左右括号去除掉，不用保存在操作符栈s1中
重复第二步到第四步，一直到表达式扫描结束。
扫描结束后，将s1中剩余的运算符依次出栈并加入到s2中
依次弹出s2，s2出栈的逆序就是后缀表达式

在这里插入图片描述

将（3+4）* 5-6 转换成后缀表达式

扫描到的元素:（3+4）*5-6	s2（栈底到栈顶）存储数据	s1(栈底到栈顶) 存储操作符	说明
(		(	s1栈为空，直接将操作符加入栈中
3	3	(	遇到数值直接加入到栈中
+	3	(+	如果直接有左括号，符号不用比较直接加入
4	3 4	(+	遇到数值直接加入到栈中
)	3 4 +		遇到右括号，需要将s1 pop出来，一直到pop都了右括号
*	3 4 +	*	s1栈为空，直接将操作符加入栈中
5	3 4 + 5	*	遇到数值直接加入到栈中
-	3 4 + 5 *	-	`- 优先级比 * 低,需要将s1 pop 出来,加入到s2中,一直比较直到待入栈大于s1的栈顶,待入可以入栈中`
6	3 4 + 5 * 6	-	扫描完后
	3 4 + 5 * 6 -		将s1全部pop到s2中

（六）逆波兰计算器

目前是个位数据

创建类：PolandNotation

方法一：通过系统提供的栈stack来实现

将后缀表达式存储到数组中，就不需要使用index进执行指向，数组遍历更加便捷

package com.lcj.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/8/30
 * @Content: 通过自带的stack来，实现逆波兰计算器
 */
public class PolandNotation {
    public static  void main(String[] args){
        //定义一个后缀表达式
        // （3+4）*5-6  =》 3 4 + 5 * 6 -
        String suffixExpression = "3 4 + 5 * 6 -"; //通过空格进行分割，便于后面分割

        //将"3 4 + 5 * 6 -" 放进ArrayList中
        List<String> rpnList = getListString(suffixExpression);

        //计算结果为：
        int res = cal(rpnList);
        System.out.println("计算结果为："+res);
    }

    //将后缀表达式放进到ArrayList中
    public static List<String> getListString(String expression){
        //将表达式：expression进行分割
       String[] split = expression.split(" ");
        List<String> list = new ArrayList<>();
        for (String s : split) {
            list.add(s);
        }
        return list;
    }

    //完成计算
    public static int cal(List<String> ls){
        //创建栈
        Stack<String> stack = new Stack<String>();

        for (String item : ls) {
            if (item.matches("\\d+")){ // 用正则表达式进行判断多位数
                stack.push(item); // 数据直接入栈
            }else{  //为操作符
                //需要从stack中取出两个值，并将计算结果进入到stacke中
                int num2 = Integer.parseInt(stack.pop());  // 栈的数据是字符串的，需要转换为整数
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                switch (item){
                    case "*":
                        res = num1 * num2;
                        break;
                    case "/":
                        res = num1 / num2;
                        break;
                    case "-":
                        res = num1 - num2;
                        break;
                    case "+":
                        res = num1 + num2;
                        break;
                    default:
                        System.out.println("目前只支持* + - /");
                        break;
                }
                //将结果入栈
                stack.push(res+""); //将整数转换字符串，因为创建的是字符串的Stack
            }
        }
        //到最后stack中只有一个值，即结果
        return Integer.parseInt(stack.pop());
    }
}

注意：将数值类型的字符串转换为int ： Interget.parseInt('1');

方法二：编写一个数组栈

自己编写一个数组栈，实现中缀表达式转换为后缀表达式，再通过后缀表达式的计算

ArrayList操作方法：

add（data） 添加数据
get（index） 获取值 （eg：index 下标）
set（index，值） 修改值
remove（index） 删除值
注意: 字符串比较大小，使用== 是比较的字符串存储的内存位置是否相同，需要使用 equals进行比较

版本一：中缀表达式转为后缀表达式

实现中缀表达式转为后缀表达式

package com.lcj.stack;

import com.sun.deploy.security.SelectableSecurityManager;
import sun.java2d.opengl.OGLRenderQueue;

import java.util.ArrayList;
import java.util.List;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/8/30-17:00
 * @Content: 自己编写stack，实现：
 *          1. 将中缀表达式转换为后缀表达式，并输出后缀表达式
 *          2.计算后缀表达式的数据结果
 *   中缀表达式:（3+4）*5-6  ==> 后缀表达式：3 4 + 5 * 6 -
 */
public class PolandNotationStack {
    public static void main(String[] args){

        stackDemon stack = new stackDemon(new ArrayList<>());  //链表：存储 后缀表达式的
        String exception = "(3+4)*5-6";
//        String exception = "()";
//        stack.push("1");
//        stack.show();
//        System.out.println( stack.transform("*"));
        //将中缀表达式 转成 后缀表达
        try {
            stackDemon suffix = transsuffix(exception, stack);
            suffix.show();
            System.out.println(suffix.show());   //后缀表达式的结果
            String suffixExpection = suffix.show();
        }catch (Exception e){
            System.out.println( e.getMessage());
        }
    }
    public static stackDemon  transsuffix(String exception,stackDemon stack1){
        stackDemon stack = stack1;
        stackDemon operStack = new stackDemon(new ArrayList<>());  //存储操作符的
        String[] split = exception.split(""); //将表达式切分一个一个的
        //注意：后缀表达式是从左往右的，因此split切片出的数据，可以直接从左到右进行遍历
        for (String iteam : split) {
            // 1.如果数值直接加入
            if (iteam.matches("\\d+")){ //判断是否为多个数值，通过正则表达式
                stack.push(iteam);  //数值存储到stack中
            }else{
                //2 判断operStack 中是否为空,直接将数据入栈,或者是左括号 (
                if (operStack.isEmpty() || iteam.equals("(")) {
                    operStack.push(iteam);
                } else if (iteam.equals(")")){
                    //将operStack进行pop,一直到(
                    while (true){
                        String  oper = operStack.pop();
//                        if(operStack.pop() == "("){ // 该代码有问题，会删除多个oper
                        if (oper.equals("(")){
                            break;
                        }else{
                            stack.push(oper); // 将操作符加入到栈中
                        }
                    }
                }else{
                    //2.1 待入栈的操作符，比较栈顶操作符大小
                    //2.1.1待入栈的操作符大于栈顶操作符,直接入栈if (operStack.compare(iteam, operStack.peek())){ //num1 待入栈的操作符 ，num2：栈顶的操作符,还有为空
                    if (operStack.isEmpty() || operStack.compare(iteam, operStack.peek()) ){ //num1 待入栈的操作符 ，num2：栈顶的操作符
                        operStack.push(iteam);
                    }else if(!operStack.compare(iteam, operStack.peek())){ // 2.1.2 待入栈的操作符小于 等于 栈顶操作符,将operStack的栈顶pop出来，保存在stack中
//                        stack.push(operStack.pop());
                        //待入栈的符号需要再一次比较栈顶操作符
                        boolean loop = true;
                        while (loop) {
                            if (!operStack.isEmpty() && !operStack.compare(iteam, operStack.peek())) {  // 不能为空，空了也没有数据
                                stack.push(operStack.pop());  //一直将operStack加入到stack中去
                            }else{
                                loop = false;
                                operStack.push(iteam); //将待入栈的操作符入栈
                            }
                        }
                    }
                }
            }
        }
        //遍历完成后，将operStack中所有全部加入到stack中

//        System.out.println("测试"+operStack.show());
        String show = operStack.show();
        String[] s = show.split(" ");
        for (String s1 : s) {
            stack.push(s1);
        }
        return stack;
    }
}

//创建stack
class stackDemon{
    //创建top
    public int top = -1; // 初始位置为：-1
    //数组List<String>
    private List<String>  stack;

    public stackDemon(List<String> stack) {
        this.stack = stack;
    }
    //判断是否为空
    public  boolean isEmpty(){
        return stack.size() == 0;  //大小为0
    }
    //数据入栈
    public void push(String key){
        stack.add(key);
    }
    //数据出栈
    public String pop(){
        String value = "";
        //判断是否为空
        if (stack.size()!= 0) {
            value = stack.get(stack.size()-1);
            stack.remove(stack.size() - 1);  // 删除最后一个数据
        }
        return value;
    }
    //展示数据
    public String show(){
        int i =0;
        String suffix = "";
        for (String s : stack) {
            if(i == 0){
//                System.out.print(""+s);
                suffix += s;
                i++;
                continue;
            }
//            System.out.print(" "+s);
            suffix += " "+s;
        }
        return suffix;
    }
    // 展示栈顶的元素
    public String peek(){

        if (isEmpty()){
            throw new RuntimeException("栈为空");
        }
        return stack.get(stack.size()-1);
    }
    //操作符转换，将操作符转换成数值，便于操作符的比较优先级
    public int transform(String num1){
        int grand = 0;
        switch (num1){
            case "+":
                grand = 0;
                break;
            case "-":
                grand = 0;
                break;
            case "*":
                grand = 1;
                break;
            case "/":
                grand = 1;
                break;
            default:
                grand = -1 ; // 目的是为了让待入栈的操作符和操作符进行比较，类似于 栈顶是（ 左括号的情况
                break;
        }
        return grand;
    }

    //比较操作符的大小
    public boolean compare(String num1,String num2){  //num1 ：为待入栈的操作符  num2：为入栈的操作符
        return  transform(num1) > transform(num2);  //待入栈的操作符大于栈顶操作符
    }

    //计算
    public int cal(int num1,int num2,String ch){
        int res = 0;
        switch (ch){
            case "+":
                res = num1 + num2;
                break;
            case "-":
                res = num1 - num2;
                break;
            case "*":
                res = num1 * num2;
                break;
            case "/":
                res = num1 / num2;
                break;
        }
        return res;
    }
}

版本二：功能完整实现

package com.lcj.stack;

import java.util.ArrayList;
import java.util.List;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/8/30-17:00
 * @Content: 自己编写stack，实现：
 *          1. 将中缀表达式转换为后缀表达式，并输出后缀表达式
 *          2.计算后缀表达式的数据结果
 *   中缀表达式:（3+4）*5-6  ==> 后缀表达式：3 4 + 5 * 6 -
 */
public class PolandNotationStack {
    public static void main(String[] args){

        stackDemon stack = new stackDemon(new ArrayList<>());  //链表：存储 后缀表达式的
        String exception = "(3+4)*5-6";
        String suffixExpection = "";
//        String exception = "()";
//        stack.push("1");
//        stack.show();
//        System.out.println( stack.transform("*"));
        //将中缀表达式 转成 后缀表达
        try {
            stackDemon suffix = transsuffix(exception, stack);
            suffix.show();
            System.out.println(suffix.show());   //后缀表达式的结果
            suffixExpection = suffix.show();
        }catch (Exception e){
            System.out.println( e.getMessage());
        }

        //结果为：
        suffixCal(suffixExpection);

    }

    //将后缀表达式进行计算结果
    public static void suffixCal(String su){
        String exp = su;  //后缀表达式
        String[] s = exp.split(" ");
        int res = 0; //结果值
        ArrayList<String> list = new ArrayList<String>();
        for (String s1 : s) {
            //1.遇到数值直接将数值输入到list中
            if (s1.matches("\\d+")){  //用正则表达式中判断字符舒是否为数值
                list.add(s1);
            }else{ //不为数值时，遇到操作符需要将数值取出来
                int num2 = Integer.parseInt(list.get(list.size()-1));
                int num1 = Integer.parseInt(list.get(list.size()-2));

                switch (s1){
                    case "+":
                        res = num1 + num2;
                        break;
                    case "-":
                        res = num1 - num2;
                        break;
                    case "*":
                        res = num1 * num2;
                        break;
                    case "/":
                        res = num1 / num2;
                        break;
                }
                list.add(""+res);  //将中间结果保存在list中
            }
        }
        System.out.println(res);
    }

    //实现将中缀表达式转换为后缀表达式中
    public static stackDemon  transsuffix(String exception,stackDemon stack1){
        stackDemon stack = stack1;
        stackDemon operStack = new stackDemon(new ArrayList<>());  //存储操作符的
        String[] split = exception.split(""); //将表达式切分一个一个的
        //注意：后缀表达式是从左往右的，因此split切片出的数据，可以直接从左到右进行遍历
        for (String iteam : split) {
            // 1.如果数值直接加入
            if (iteam.matches("\\d+")){ //判断是否为多个数值，通过正则表达式
                stack.push(iteam);  //数值存储到stack中
            }else{
                //2 判断operStack 中是否为空,直接将数据入栈,或者是左括号 (
                if (operStack.isEmpty() || iteam.equals("(")) {
                    operStack.push(iteam);
                } else if (iteam.equals(")")){
                    //将operStack进行pop,一直到(
                    while (true){
                        String  oper = operStack.pop();
//                        if(operStack.pop() == "("){ // 该代码有问题，会删除多个oper
                        if (oper.equals("(")){
                            break;
                        }else{
                            stack.push(oper); // 将操作符加入到栈中
                        }
                    }
                }else{
                    //2.1 待入栈的操作符，比较栈顶操作符大小
                    //2.1.1待入栈的操作符大于栈顶操作符,直接入栈if (operStack.compare(iteam, operStack.peek())){ //num1 待入栈的操作符 ，num2：栈顶的操作符,还有为空
                    if (operStack.isEmpty() || operStack.compare(iteam, operStack.peek()) ){ //num1 待入栈的操作符 ，num2：栈顶的操作符
                        operStack.push(iteam);
                    }else if(!operStack.compare(iteam, operStack.peek())){ // 2.1.2 待入栈的操作符小于 等于 栈顶操作符,将operStack的栈顶pop出来，保存在stack中
//                        stack.push(operStack.pop());
                        //待入栈的符号需要再一次比较栈顶操作符
                        boolean loop = true;
                        while (loop) {
                            if (!operStack.isEmpty() && !operStack.compare(iteam, operStack.peek())) {  // 不能为空，空了也没有数据
                                stack.push(operStack.pop());  //一直将operStack加入到stack中去
                            }else{
                                loop = false;
                                operStack.push(iteam); //将待入栈的操作符入栈
                            }
                        }
                    }
                }
            }
        }
        //遍历完成后，将operStack中所有全部加入到stack中

//        System.out.println("测试"+operStack.show());
        String show = operStack.show();
        String[] s = show.split(" ");
        for (String s1 : s) {
            stack.push(s1);
        }
        return stack;
    }
}

//创建stack
class stackDemon{
    //创建top
    public int top = -1; // 初始位置为：-1
    //数组List<String>
    private List<String>  stack;

    public stackDemon(List<String> stack) {
        this.stack = stack;
    }
    //判断是否为空
    public  boolean isEmpty(){
        return stack.size() == 0;  //大小为0
    }
    //数据入栈
    public void push(String key){
        stack.add(key);
    }
    //数据出栈
    public String pop(){
        String value = "";
        //判断是否为空
        if (stack.size()!= 0) {
            value = stack.get(stack.size()-1);
            stack.remove(stack.size() - 1);  // 删除最后一个数据
        }
        return value;
    }
    //展示数据
    public String show(){
        int i =0;
        String suffix = "";
        for (String s : stack) {
            if(i == 0){
//                System.out.print(""+s);
                suffix += s;
                i++;
                continue;
            }
//            System.out.print(" "+s);
            suffix += " "+s;
        }
        return suffix;
    }
    // 展示栈顶的元素
    public String peek(){

        if (isEmpty()){
            throw new RuntimeException("栈为空");
        }
        return stack.get(stack.size()-1);
    }
    //操作符转换，将操作符转换成数值，便于操作符的比较优先级
    public int transform(String num1){
        int grand = 0;
        switch (num1){
            case "+":
                grand = 0;
                break;
            case "-":
                grand = 0;
                break;
            case "*":
                grand = 1;
                break;
            case "/":
                grand = 1;
                break;
            default:
                grand = -1 ; // 目的是为了让待入栈的操作符和操作符进行比较，类似于 栈顶是（ 左括号的情况
                break;
        }
        return grand;
    }

    //比较操作符的大小
    public boolean compare(String num1,String num2){  //num1 ：为待入栈的操作符  num2：为入栈的操作符
        return  transform(num1) > transform(num2);  //待入栈的操作符大于栈顶操作符
    }

    //计算
    public int cal(int num1,int num2,String ch){
        int res = 0;
        switch (ch){
            case "+":
                res = num1 + num2;
                break;
            case "-":
                res = num1 - num2;
                break;
            case "*":
                res = num1 * num2;
                break;
            case "/":
                res = num1 / num2;
                break;
        }
        return res;
    }
}

第五章：递归

（一）递归介绍

应用场景：迷宫问题（回溯）、递归（recursion）、汉罗塔、阶乘问题、8皇后问题

算法中也会使用递归 eg：快排、归并排序、二分查找、分治算法

递归：方法自己调用自己，每次调用时传入不同的变量，有助于解决复杂的问题

在这里插入图片描述

JVM组成：栈、堆、代码区（包括常量）

递归调用规则：

当程序执行到一个方法时，就会开辟一个独立的空间（栈空间）
方法的局部变量是独立的，不会相互影响的
如果方法中使用的是引用类型变量（eg：数组），就会共享该引用类型的数据
递归必须向退出的递归条件逼近，否则就死循环了
当一个方法执行完毕后，或者遇到了return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕

（二）迷宫回溯问题分析与实现

迷宫回溯问题：

在这里插入图片描述

创建package：com.lcj.recursion

创建class：MiGong

package com.lcj.recursion;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/9/2-21:17
 * @Content:
 */
public class MiGong {
    public static void main(String[] args){
        //先创建一个二维数组，模型迷宫
        //地图为8行7列的
        int[][] map = new int[8][7];

        //用1来代表是墙
        //上下墙
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }

        //左右为墙
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        //创建墙
        map[3][1] = 1;
        map[3][2] = 1;
        // 找路方法
        setWay(map,1,1);

        //输出地图
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j]+"  ");
            }
            System.out.println();
        }
//        System.out.println(map[1].length);
    }
    //使用递归回溯小球
    /*
    * 1、map :表示地图
    * 2、i，j 表示起始位置
    * 3、map[7][6] 为终点
    * 4、当map[i][j] 为 0表示 该节点没有走过，为1表示墙，2表示通路，3表示该节点已经走过，但是走不通
    * */
    public static boolean setWay(int[][] map,int i,int j){
        if(map[6][5] == 2){
            return true;
        }else{
            if (map[i][j] == 0){ // 当前的节点没有走过
                //按照的策略为：下 -> 右 ->上 ->左
                map[i][j] = 2;
                if (setWay(map,i+1,j)){
                    return true;
                }else if(setWay(map,i,j+1)){
                    return true;
                }else if(setWay(map,i-1,j)){
                    return true;
                }else if(setWay(map,i,j-1)){
                    return true;

                }else {
                    //说明该点是走不通的
                    map[i][j] = 3;
                    return false;
                }
            }else { //该map[i][j]节点 不为0,可能是1（墙）,2（已经走过）,3（死路）
                return false; //不要再走
            }
        }
    }
}

注意：谁调用，谁用值

（三）八皇后问题（回溯问题）

1、介绍

任意两个皇后都不能同时处于同一行、同一列或者同一斜线

在这里插入图片描述

用一维数组解决棋盘位置：eg:arr[8] = {0,4,7,5,2,6,1,3} // arr对应的下标表示第几行，arr[i] = val ，val表示第i+1个皇后，放在第i+1行的第val+1列中

2、代码实现

创建class：Queue8

package com.lcj.recursion;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/9/5-21:05
 * @Content:
 */
public class Queue8 {

    int max = 8;  //皇后的个数

    //定义数值array，保存皇后放置位置的结果
    int[] array = new int[max];
    static int count = 0;
    public static void main(String[] args){
        //测试
        Queue8 queue8 = new Queue8();
        queue8.check(0);  //第0行第0列开始
        System.out.printf("个数为：%d",count);

    }

    //编写一个方法，放置第n个皇后
    private void check(int n){
        if(n == max){ // n = 8
            print(); //输出结果
            return; //已经将结果放好
        }
        //依次放入皇后，并判断是否冲突
        for (int i = 0; i < max; i++) {
            //先把当前这个皇后n，放到该行的第1列中
            array[n] = i;
            if(judge(n)){  //不冲突
                check(n+1);
            }
            //如果冲突会跳转到array[n] = i 上面的，将n往后继续移动
        }
    }

    //判断是否冲突,查看当我们放置第n个皇后是否和前面的已经摆放的皇后冲突
    //同行（不需要判断，因为每次一行只有一个数值）、同列、同斜线
    private boolean judge(int n){
        for (int i = 0; i < n; i++) {
            //array[i] == array[n]  判断是否在同一列
            /*Math.abs(n-i) ==Math.abs(array[n]-array[i]) 主要是判断是否在同一条斜线上
            Math.abs 是 绝对值，n-i 是行之差，array[n]-array[i] 是列之差，值相同说明是斜线
            * */
            if (array[i] == array[n] || Math.abs(n-i) ==Math.abs(array[n]-array[i])){
                return false;
            }
        }
        return true; // 不冲突
    }

    //将皇后摆放的位置输出来
    private void print(){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println(); //换行
        count++;
    }
}

第六章：排序算法

一、排序算法

排序算法（sort Algorithm）：将数据按着一定的顺序进行排序的过程。
排序的分类：
- 内部排序：将数据加载到内存中进行排序
- 外部排序法：数量大的时候，无法加载到内存中时，用外部存储进行排序
直接插入、简单选择、冒泡排序法必须要掌握

二、算法的时间复杂度

（一）算法的评判方法

事后统计的方法

在计算运行后，再计算运行时间
- 有问题需要运行程序，但是要受到计算机硬件性能的影响
- 运行程序可能需要很长的时间
事前估算的方法——时间复杂度

通过分析算法的时间复杂度来判断那个算法比较优秀

（二）时间复杂度

1、时间频度

时间频数：一个算法花费时间与算法中语句执行次数成正比，即语句多花费时间多。

语句频数 或者 时间频数，记作T(n)：算法中语句执行的次数

特点：

忽略时间频数中的常数项

在这里插入图片描述

忽略时间频数中低次项
忽略时间频数的系数

2 、时间复杂度

时间复杂度：

2.1 算法中基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示（时间频数），若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称为f(n)是T(n)的同数量级函数。记作T(n)=O (f(n)) ,称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。

在这里插入图片描述

$T(n)=3n^2+3n+1$ ==> $T(n)=n^2$

$f(n)=n^2$

结果为：

$T(n)/f(n)=O(n^2)$

在这里插入图片描述

$O(1) < O(log_2^n)< O(n)< O(nlog_2^n)< O(n^2)< O(n^3)< O(n^k)< O(2^n)<(n!)$

在这里插入图片描述

常数阶 $O (1)$ :没有循环代码

在这里插入图片描述

（三）平均时间复杂度

1、平均时间复杂度

平均时间复杂度：所有可能的输入实例的时间平均之后的算法运行时间

2、最坏时间复杂度

最坏时间复杂度：算法运行最坏的时间复杂度，作用：相对于算法的运行时间界限，不会出现最坏的结果

在这里插入图片描述

（四）空间复杂度——空间换时间

在这里插入图片描述

三、冒泡排序算法(bubble sorting)

一共需要进行数组长度-1次排序
每一次内部排序在逐渐减少
优化：如果在排序中，没有发生交换，说明已经是有序的，直接将结果输出

（一）代码实现

创建package：com.lcj.sort

创建class：Bubble Sorting

package com.lcj.sort;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/9/13-21:10
 * @Content: 创建冒泡排序法
 */
public class BubblerSorting {
    public static void main(String[] args){
        int arr[] = {3,9,-1,10,-2};

        for(int i=0; i<arr.length-1;i++){ // 循环每次减少
            for(int j=0;j <arr.length-1-i;j++){
                int temp = 0;
                if (arr[j]<arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }

//        System.out.println(arr.toString());
        System.out.println(Arrays.toString(arr));
    }
}

升级：

如果在排序中，如果数据已经排序完成了，直接中止排序输出结果

package com.lcj.sort;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/9/13-21:10
 * @Content: 创建冒泡排序法
 */
public class BubblerSorting {
    public static void main(String[] args){
//        int arr[] = {3,9,-1,10,-2};
        int arr[] = {1,3,2,4,5};
        boolean flage = false; // 目的：判断数据是否交换，如果没有发生交换说明数据已经排序完成
        for(int i=0; i<arr.length-1;i++){ // 循环每次减少
            for(int j=0;j <arr.length-1-i;j++){
                int temp = 0;
                if (arr[j] > arr[j+1]){
                    flage = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            System.out.printf("第%d次循环",i);
            System.out.println(Arrays.toString(arr));
            if(flage == false){
                break;
            }else{
                flage = false;  //注意需要将数据转换成false
            }
        }

//        System.out.println(arr.toString());
        System.out.println(Arrays.toString(arr));
    }
}

测试：将数量达到8万条时，运行时间较长

package com.lcj.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/9/13-21:10
 * @Content: 创建冒泡排序法
 */

import java.util.Date;

public class BubblerSorting {
    public static void main(String[] args){
//        int arr[] = {3,9,-1,10,-2};
        // 测试当数据量的大的时候，执行时间的变化
        int[] arr = new int[80000];
        //添加数据
        for(int i=0; i<80000 ;i++){
            arr[i] = (int)(Math.random()*80000) ; // 生成[0,1) * 80000 范围为:[0,80000)
        }

        Date date1 = new Date(); //生成时间
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("YYYY-MM-DD hh:mm:ss"); //将时间进行格式化
//        System.out.println(date1);
        System.out.println("开始时间："+simpleDateFormat.format(date1));
        for(int i=0; i<arr.length-1;i++){ // 循环每次减少
            for(int j=0;j <arr.length-1-i;j++){
                int temp = 0;
                if (arr[j]<arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        Date date2 = new Date();
        System.out.println("结束时间："+simpleDateFormat.format(date2));

//        System.out.println(Arrays.toString(arr));  //展示全部数据
    }
}

四、选择排序算法

（一）选举排序介绍

选择排序：是从待排序的的数据中，按指定规则选出某一元素，再依次交换位置后达到排序的目的。

在这里插入图片描述

（二）代码实现

案例：将101,34,119,1，通过选择排序从==低到高进行排序==

创建class：SelectSort

时间复杂度: $O(n^2)$

package com.lcj.sort;

import java.util.Arrays;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/9/14-20:59
 * @Content:选择排序实现
 */
public class SelectSort {
    public static void main(String[] args){
        int[] arr1 = new int[]{101, 34, 119, 1};
        selectSort(arr1);
    }

    //选择排序的方法
    public static void selectSort(int[] arr){
        int temp =0;
        for (int i=0;i<arr.length-1;i++){ //选择排序中外部排序只有： 数组长度-1
            int minIndex = i; //记录最大下标
            int min = arr[minIndex];
            for (int j=i+1;j<arr.length;j++){
                if(min > arr[j]){
                    minIndex = j;
                    min = arr[minIndex];  //将最值进行更新，目前是为了确定最小值的位置
                }
            }
            //交换数据
            if(minIdex !=i){  //优化：部分情况，是后面已经排好序了，就不需要进行排序了
            	temp =min;
            	arr[minIndex] = arr[i];
            	arr[i] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
        System.out.println(Arrays.toString(arr));
    }
}

注意：先将算法简单化，再将算法复杂化，一部分一部分进行实现

五、插入排序算法

（一）介绍

插入排序属于内部排序，通过将要排序的数据插入到指定位置来达到排序的

在这里插入图片描述

（二）代码实现

创建class：IndexSort

自己实现：

版本一：

package com.lcj.sort;

import java.util.Arrays;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/9/16-22:06
 * @Content: 自己实现插入排序 ：从小到大
 */
public class IndexSort {
    public static void main(String[] args){
        int arr[] = {17,3,25,14,20,9};
        indexSorting(arr);
    }
    public static void indexSorting(int[] arr){
        int index = 0;//待插入数据的下标
        int indexNum = 0; //待插入数据
        for(int i=1;i<arr.length;i++){
            index = i; //待插入数据的下标,为第一次for循环的下标
            indexNum = arr[i];// 待插入值
            //有序表进行排序
            // 1.实现待插入数据的位置确定
            // 2.实现插入数据（需要将数据进行移动，这里主要是往后移动，因此需要找到待插入的位置）
                // 2.1插入位置的判断
            for(int j=0;j < i;j++){
                int indexLoc = 0;  //插入数据的位置
                boolean flag = false;
                //寻找插入数据的位置—暴力法
                if (arr[i]<=arr[j]){
                    indexLoc = j; //获得插入数据的位置
                    flag = true;  //可以执行后移操作
                }
                if(flag) {
                    //执行后移操作
                    for (int k =i;k>j;k--){
                        arr[k]=arr[k-1];
                    }
                    arr[j] = indexNum;
                }
            }
            System.out.printf("第%d次",i);
            System.out.println(Arrays.toString(arr));
        }
    }
}

版本二：

package com.lcj.sort;

import java.util.Arrays;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/9/16-22:06
 * @Content: 自己实现插入排序 ：从小到大
 */
public class IndexSort {
    public static void main(String[] args){
        int arr[] = {17,3,25,14,20,9};
        indexSorting(arr);
    }
    public static void indexSorting(int[] arr){
        int index = 0;//待插入数据的下标
        int indexNum = 0; //待插入数据
        for(int i=1;i<arr.length;i++){
            index = i; //待插入数据的下标,为第一次for循环的下标
            indexNum = arr[i];// 待插入值
            //有序表进行排序
            // 1.实现待插入数据的位置确定
            // 2.实现插入数据（需要将数据进行移动，这里主要是往后移动，因此需要找到待插入的位置）
                // 2.1插入位置的判断
            for(int j=0;j < i;j++){
                int indexLoc = 0;  //插入数据的位置
                boolean flag = false;
                //寻找插入数据的位置—暴力法
                if (arr[i]<=arr[j]){
                    indexLoc = j; //获得插入数据的位置
                    flag = true;  //可以执行后移操作
                }
                if(flag){
                    for(int k=j;j<=i;j++){
                        int temp =arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
            System.out.printf("第%d次",i);
            System.out.println(Arrays.toString(arr));
        }
    }
}

测试：

package com.lcj.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/9/16-22:06
 * @Content: 自己实现插入排序 ：从小到大
 */
public class IndexSort {
    public static void main(String[] args){
//        int arr[] = {17,3,25,14,20,9};
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random()*arr.length);
        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("YYYY-MM-DD hh:mm:ss");
        System.out.println("开始时间"+simpleDateFormat.format(date1));
        indexSorting(arr);

        Date date2 = new Date();
//        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("YYYY-MM-DD hh:mm:ss");
        System.out.println("开始时间"+simpleDateFormat.format(date2));

    }
    public static void indexSorting(int[] arr){
        int index = 0;//待插入数据的下标
        int indexNum = 0; //待插入数据
        for(int i=1;i<arr.length;i++){
            index = i; //待插入数据的下标,为第一次for循环的下标
            indexNum = arr[i];// 待插入值
            //有序表进行排序
            // 1.实现待插入数据的位置确定
            // 2.实现插入数据（需要将数据进行移动，这里主要是往后移动，因此需要找到待插入的位置）
                // 2.1插入位置的判断
            for(int j=0;j < i;j++){
                int indexLoc = 0;  //插入数据的位置
                boolean flag = false;
                //寻找插入数据的位置—暴力法
                if (arr[i]<=arr[j]){
                    indexLoc = j; //获得插入数据的位置
                    flag = true;  //可以执行后移操作
                }
//                if(flag) {
//                    //执行后移操作
//                    for (int k =i;k>j;k--){
//                        arr[k]=arr[k-1];
//                    }
//                    arr[j] = indexNum;
//                }
                if(flag){
                    for(int k=j;j<=i;j++){
                        int temp =arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
            }

        }
    }
}

六、希尔排序算法（shell）

在这里插入图片描述

（一）希尔排序算法介绍

希尔排序是经过改进之后的一个更高效的版本，也称为缩小增量排序

基本思想：

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰好被分成一组

在这里插入图片描述

（二）代码实现

在这里插入图片描述

方法一：交换法

package com.lcj.sort;

import java.util.Arrays;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/9/19-10:40
 * @Content:希尔排序算法，自己排序实现
 */
public class ShellSort {
    public static void main(String[] args){
        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        shellSort(arr);
    }
    //使用逐步推导的过程进行实现代码
     public static void shellSort(int[] arr){
        int temp = 0;
        for(int grap=arr.length/2; grap > 0; grap/=2){  // 分组的次数 5,2,1
//            System.out.println(grap); //测试
            for(int i=grap;i<arr.length;i++){  //循环一次是一组
                for (int j=i-grap;j>=0;j-=grap) {
                    if (arr[j] > arr[j + grap]) {
                        temp = arr[j];
                        arr[j] = arr[j + grap];
                        arr[j + grap] = temp;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(arr));
     }
}

方法二：移动法——插入法

package com.lcj.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/9/19-10:40
 * @Content:希尔排序算法，自己排序实现
 */
public class ShellSort {
    public static void main(String[] args){
        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        shellSort(arr); // 移动式

       
    }
    //使用逐步推导的过程进行实现代码
     public static void shellSort(int[] arr){
        int temp = 0;
        for(int grap=arr.length/2; grap > 0; grap/=2){  // 分组的次数 5,2,1
//          System.out.println(grap); //测试
            
            for(int i=grap;i<arr.length;i++) {  //循环一次是一组
                int j = i;//待插入数据的下标
                int insertValue = arr[i]; //待插入值
                if (arr[j] < arr[j-grap]) {  //待插入值小于之前的，说明待入数值需要在[j-grap] 之前，但是位置未确定
                    while(j-grap>=0 && insertValue <arr[j-grap] ){  //insertValue 小于 arr[j-grap]插入数据
                        //将数据往后移动
                        arr[j]= arr[j-grap];
                        j-=grap;  //将标往后移动
                    }
                    arr[j] = insertValue;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
     }

}

测试运行时间：1S

package com.lcj.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/9/19-10:40
 * @Content:希尔排序算法，自己排序实现
 */
public class ShellSort {
    public static void main(String[] args){
        //int[] arr = {8,9,1,7,2,3,5,4,6,0};
        int arr[] = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random()*arr.length);
        }
        Date date1 = new Date();
        SimpleDateFormat simple = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String dateString = simple.format(date1);
        System.out.println(dateString);
        shellSort(arr); // 移动式

        Date date2 = new Date();
        String date2String = simple.format(date2);
        System.out.println(date2String);
    }
    //使用逐步推导的过程进行实现代码
     public static void shellSort(int[] arr){
        int temp = 0;
        for(int grap=arr.length/2; grap > 0; grap/=2){  // 分组的次数 5,2,1
//          System.out.println(grap); //测试
            
            for(int i=grap;i<arr.length;i++) {  //循环一次是一组
                int j = i;//待插入数据的下标
                int insertValue = arr[i]; //待插入值
                if (arr[j] < arr[j-grap]) {  //待插入值小于之前的，说明待入数值需要在[j-grap] 之前，但是位置未确定
                    while(j-grap>=0 && insertValue <arr[j-grap] ){  //insertValue 小于 arr[j-grap]插入数据
                        //将数据往后移动
                        arr[j]= arr[j-grap];
                        j-=grap;  //将标往后移动
                    }
                    arr[j] = insertValue;
                }
            }
        }
        //System.out.println(Arrays.toString(arr));
     }

}

七、快排算法——Quicksort

（一）快排算法介绍

动画演示1

动画演示2

快排算法是对冒泡排序算法的升级。

基本思想：通过一趟排序将数据，将排序数据分成两部分，注意其他一部分要比另一部小，然后另外两部分也根据这样方式进行排序，最终实现排序数据有序。（可以采取递归实现）

在这里插入图片描述

（二）代码实现

package com.lcj.sort;

import java.util.Arrays;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/9/21-22:08
 * @Content:
 */
public class QuickSort {
    public static void main(String[] arg){
        int arr[] = {-9,78,0,23,-567,70};
        quickSort(arr,0, arr.length-1);
    }

    public static void quickSort(int[] arr,int left,int right){
        int l = left; //左下标
        int r = right; //右下标
        int pivot = arr[(left+right)/2]; //取左右的中间值，作为基准，左边是全部小于
        int temp = 0;//临时变量
        while(l < r){
            //只要arr[l] 小于 pivot ，将l向右移动一格，只要arr[l] > pivot就终止移动
            if(arr[l] < pivot){
                l+=1;
            }
            //只要arr[r] 大于 pivot ，将r向左移动一格，只要arr[r] < pivot就终止移动
            if(arr[r] > pivot ){
                r -=1;
            }

            //如果l大于r说明privot 左边的数据已经是最小的了，右边的数据是最大的了
            if(l >= r){
                break;
            }

            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //如果交换完后，发现这个arr[l] == pivot 值,相等于r--，前移
            if(arr[l] == pivot){  //注意:r指向的是交换的元素，如果不说不进行后移的话，会死循环
                r -=1;
            }
            //如果交换完后，发现这个arr[r] == pivot 值,相等于l++，后移
            if(arr[r] == pivot){
                l +=1;
            }

        }
        // 如果l==r，必须l++，r--,否则出现栈溢出,即死循环
        if (l==r){
            l += 1;
            r -= 1;
        }
        //向左递归
        if (left < r){
            quickSort(arr,left,r);
        }

        //向右递归,
        if (l < right){
            quickSort(arr,l,right);
        }
        System.out.println(Arrays.toString(arr));
    }
}

压力测试：

package com.lcj.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/9/21-22:08
 * @Content:
 */
public class QuickSort {
    public static void main(String[] arg){
//        int arr[] = {-9,78,0,23,-567,70};
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random()*80000);
        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("YYYY-MM-DD hh:mm:ss");
        System.out.println(simpleDateFormat.format(date1));
        quickSort(arr,0, arr.length-1);
        Date date = new Date();
        System.out.println(simpleDateFormat.format(date));

    }

    public static void quickSort(int[] arr,int left,int right){
        int l = left; //左下标
        int r = right; //右下标
        int pivot = arr[(left+right)/2]; //取左右的中间值，作为基准，左边是全部小于
        int temp = 0;//临时变量
        while(l < r){
            //只要arr[l] 小于 pivot ，将l向右移动一格，只要arr[l] > pivot就终止移动
            if(arr[l] < pivot){
                l+=1;
            }
            //只要arr[r] 大于 pivot ，将r向左移动一格，只要arr[r] < pivot就终止移动
            if(arr[r] > pivot ){
                r -=1;
            }

            //如果l大于r说明privot 左边的数据已经是最小的了，右边的数据是最大的了
            if(l >= r){
                break;
            }

            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //如果交换完后，发现这个arr[l] == pivot 值,相等于r--，前移
            if(arr[l] == pivot){  //注意:r指向的是交换的元素，如果不说不进行后移的话，会死循环
                r -=1;
            }
            //如果交换完后，发现这个arr[r] == pivot 值,相等于l++，后移
            if(arr[r] == pivot){
                l +=1;
            }

        }
        // 如果l==r，必须l++，r--,否则出现栈溢出,即死循环
        if (l==r){
            l += 1;
            r -= 1;
        }
        //向左递归
        if (left < r){
            quickSort(arr,left,r);
        }

        //向右递归,
        if (l < right){
            quickSort(arr,l,right);
        }
//        System.out.println(Arrays.toString(arr));
    }
}

运行时间：

2022-09-269 04:37:14
2022-09-269 04:37:14

八、归并排算法

将大问题分成小问题来解决

（一）介绍

归并排序（merge-sort）是利用归并的思想实现排序，采用经典的分治（divide-and-conquer）策略（分治问题是将问题：1.分成一些小的问题，然后递归求解，2.治：将分阶段得到的各答案“修补”在一起，即分而治之）

将84571362 按照从小到大进行排序

在这里插入图片描述

（二）代码实现

创建class：MergetSort

package com.lcj.sort;

import java.util.Arrays;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/10/13-22:09
 * @Content:归并排序算法
 */
public class MergeSort {
    public static void main(String[] args) {
        int arr[] = {8, 4, 5, 6, 1, 3, 6, 2};
        int[] temp = new int[arr.length];
        mergeSort(arr,0,arr.length - 1,temp);
        System.out.println("归并排序后"+ Arrays.toString(arr));
    }


    //分+合的算法
    public static void mergeSort(int[] arr,int left,int right,int[] temp){
        if(left < right){
            int mid = (left + right)/2;
            //向左进行递归
            mergeSort(arr,left,mid,temp);
            //向右进行递归
            mergeSort(arr,mid+1,right,temp);
            //合并
            merg(arr,left,mid,right,temp);

        }

    }
    //合并方法
    /*
    * arr:数据数值
    * left：左边有序数列的初始索引
    * right：右边有序数列的最右边索引
    * mid ：是中间索引
    * tmp：临时数组
    * */
    public static void merg(int[] arr,int left,int mid,int right,int[] tmp){
        int i = left; //初始化最左边的索引
        int j = mid +1 ;
        int t = 0 ; //临时数组的初始索引

        //第一步：先将左右两边（），按照从小到的大顺序将数据放进到临时数组中,直到一边处理完成
        // 注意：左右两边的数据分别是有序的
        while(i<=mid && j<=right){
            // 如果左边的数据小于右边时，将左边数据移动到tmp中
            if (arr[i] <= arr[j]){
                tmp[t] = arr[i];
                t += 1; //将t往后进行移动
                i += 1; // 将i往后进行移动
            }else{   // 将右边的数据大于左边的数据时
                tmp[t] = arr[j];
                t += 1;  // 将t往后进行移动
                j += 1;
            }
        }

        // 第二步：将剩下的数组依次放进到临时数组中
        while(i <= mid){  // 左边数据剩余
            tmp[t] = arr[i];
            i ++;
            t ++;
        }
        while(j <= right){  // 右边数据剩余
            tmp[t] = arr[j];
            j ++;
            t ++;
        }

        // 第三步：将临时数组数据放进arr中
        t =0;
        int tempLeft = left;

        while(tempLeft <= right){
            arr[tempLeft] = tmp[t];
            t += 1;
            tempLeft +=1;
        }

    }
}

九、基数排序

（一）基础知识

基数排序（radix sort）属于“分配式排序” ，或者称为“桶子排序”。主要是通过将数据的个位、十位等位数放进行相应的“桶”中，来达到排序的效果

基数排序属于效率高的稳定性排序
基数排序是桶排序的扩展

思路：

将所有待排序的数据，统一长度（位数短的在前面补充0），然后按照从低位到高位对数据进行排序

eg：{53,3，542,748,14，214} 进行升序排序

在这里插入图片描述

（二）代码实现

创建类：RadixSort

package com.lcj.sort;

import java.util.Arrays;

/**
 * @Version 1.0
 * @Author:lcj
 * @Date:2022/10/16-10:44
 * @Content:基数排序
 * 主要思路：
 * 1. 创建对应的10个桶，即十个数组，分别代表的是从0-9的数字
 * 2. 获取个位、十位等数据，将数据对应放进到数组中，并数据读取到原来的数组中，进行排序
 * 3. 重复第2步骤，循环次数为数据中最大值的个数
 * */
public class RadixSort {
    public static void main(String[] args){
        int arr[] = {53,3,42,748,14,214};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    //基数排序方法
    public static void radixSort(int[] arr){


        //1.通过创建二维数据，来表示桶，长度为arr.length来避免数据溢出的问题
        //通过空间换时间
        int[][] bucket = new int[10][arr.length];

        //记录每一个桶中的数量，并不是所有的桶中有数据
        // eg：bucketElementCounts[1] 存储的是bucket[1]中的数据个数
        int[] bucketElementCounts = new int[10];

        //2.获取到最大值的长度
        int max = arr[0];
        for(int i = 0;i < arr.length-1;i++){
            if(max <= arr[i]){
                max = arr[i];
            }
        }
        int maxLength = (max+"").length(); //最大值的长度，决定循环的次数
        
        // 4. 循环执行
        for(int k = 0 ,n=1;k< maxLength ;k++,n *= 10) {
            // 3，获取数据循环
            for (int i = 0; i < arr.length; i++) {//遍历所有数据,获取位数
                //取除元素的位数
                int digitOfELement = arr[i]/n % 10;
                bucket[digitOfELement][bucketElementCounts[digitOfELement]] = arr[i];
                bucketElementCounts[digitOfELement]++; //元素的个数统计需要改变
            }

            //将二维数组中的数据转移到arr中
            int index = 0; //初始化的索引下标
            for (int j = 0; j < bucketElementCounts.length; j++) {  //bucketElementCounts = 10
                if (bucketElementCounts[j] > 0) {
                    for (int l = 0; l < bucketElementCounts[j]; l++) {
                        arr[index] = bucket[j][l];  // 将二维数组的元素重新赋给arr数组中
                        index++;
                    }
                    bucketElementCounts[j] = 0 ; //注意一定要将这点的数据清为0
                }
            }
        }
    }

}

注意事项：数据量特别大的时候会占用大量的内存



~~~java
Date date1 = new Date(); //生成时间
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("YYYY-MM-DD hh:mm:ss"); //将时间进行格式化
//        System.out.println(date1);
        System.out.println("开始时间："+simpleDateFormat.format(date1));

十、排序总结

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	排序方式	稳定性
冒泡排序	$O(n^2)$	$O (n)$	$O(n^2)$	$O(n^2)$	In-Place	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O (1)$	In-Place	不稳定
插入排序	$O(n^2)$	$O ()$
希尔排序
归并排序
快速排序
堆排序
计数排序
桶排序
基数排序