开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构与算法 -> 正文阅读

[数据结构与算法]数据结构与算法

Java数据结构与算法文章目录

提示：以下是本篇文章正文内容，下面案例可供参考

一、数据结构与算法关系

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

二、线性结构与非线性结构

线性结构

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

非线性结构

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

三、稀疏数组（sparsearray）和队列

3.1 稀疏数组

3.1.1 稀疏数组应用场景

在这里插入图片描述
基本介绍：
当一个数组中大部分元素为0，或者为同一个值的时候，可以使用稀疏数组来确保该数组
稀疏数组的处理方法：

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

3.1.2 思路分析

在这里插入图片描述

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

遍历原始的二维数组，得到有效数据的个数sum
根据sum就可以创建稀疏数组sparsearray，行为[sum + 1]，列为[3]
将二维数组的有效的数据存入稀疏数组

稀疏数组转原始的二维数组思路
1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
2.在读取稀疏数组后几行的数据，并赋给原始的二维数组即可

3.1.3 代码实现

public class SparseArray {
    public static void main(String[] args) {
        //创建一个原始的二维数组11 * 11
        //0：表示没有棋子，1 表示黑子 2 表示白子
        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        chessArr1[4][5] = 6;

        //输出原始的二维数组
        System.out.println("原始的二维数组：++++++++++++++++++++++++");
        for (int[] row : chessArr1){
            for (int data : row){
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }


        /*
        🌟 将二维数组转稀疏数组
        1. 遍历原始的二维数组，得到有效数据的个数sum
        2. 根据sum就可以创建稀疏数组sparsearray，行为[sum + 1]，列为[3]
        3. 将二维数组的有效的数据存入稀疏数组
         */

        //1.遍历二维数组得到非0数据的个数
        int sum = 0;
        for (int i = 0; i < 11; i++){
            for (int j = 0; j < 11; j++){
                if (chessArr1[i][j] != 0){
                    sum++;
                }
            }
        }

        //2.创建对应的稀疏数组
        int sparseArr[][] = new int[sum + 1][3];
        //给稀疏数组赋值
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;

        //遍历二维数组，将非0的值放到sparseArr中
        int count = 0; // 用来记录是第几个非0数据
        for (int i = 0; i < 11; i++){
            for (int j = 0; j < 11; j++){
                if (chessArr1[i][j] != 0){
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr1[i][j];
                }
            }
        }
        // 输出稀疏数组的显示
        System.out.println();
        System.out.println("得到的稀疏数组为：~~~~~~~~~~~~~~~~~~~~~~~~~");
        for (int i = 0; i <sparseArr.length; i++){
            System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
        }
        System.out.println();


        /*
        🌟 将稀疏数组转换为二维数组
        1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
        2.在读取稀疏数组后几行的数据，并赋给原始的二维数组即可
         */
        //1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
        int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
        //2.在读取稀疏数组后几行的数据，并赋给原始的二维数组即可
        for (int i = 1; i < sparseArr.length; i++){
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        System.out.println("恢复后的二维数组：！！！！！！！！！！");
        for (int[] row : chessArr2){
            for (int data : row){
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
    }
}

3.2 队列（使用数组实现）

3.2.1 使用场景

特点：先进先出，是一个有序列表，类似于餐厅排队买饭，先到先买，后到继续排队。

在这里插入图片描述
上图中可以看到MaxSize - 1 为该数组的最大容量，当往数组中添加数据的时候，rear会随着增加，front不变，当往出取的时候，rear不变，front会随着增加。

3.2.2 思路分析

此方法存在不足，当存入数据，当数据取出后无法在使用其腾出的空间，此问题在循环数组中得到解决

当尾指针往后移：rear + 1，当front == rear【空】
容尾指针rear小于队列的最大下标maxSize - 1，则数据存入rear所指的数组元素中，否则无法存入数据。
rear == maxSize - 1 【队列满】

3.2.3 代码实现

import java.util.Scanner;

public class ArrayQueueDemo {
    public static void main(String[] args) {
        //测试
        //创建队列
        ArrayQueue arrayQueue = new ArrayQueue(3);
        char key = ' '; //接收用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        //输出一个菜单
        while (loop){
            System.out.println("s(show)：显示队列");
            System.out.println("a(add)：添加数据到队列");
            System.out.println("g(get)：从队列中取出数据");
            System.out.println("h(head)：显示队列头的数据");
            System.out.println("e(exit)：退出程序");
            System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
            System.out.print("请输入：");
            key = scanner.next().charAt(0);
            switch (key){
                case 's' :
                    arrayQueue.showQueue();
                    System.out.println("--------------------------------");
                    break;
                case 'a' :
                    System.out.println("输入一个值：");
                    int value = scanner.nextInt();
                    arrayQueue.addQueue(value);
                    System.out.println("--------------------------------");
                    break;
                case 'g' :
                    try{
                        int res = arrayQueue.getQueue();
                        System.out.printf("取出的数据是：%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                        System.out.println("--------------------------------");
                    }
                    break;
                case 'h':
                    try{
                        int res = arrayQueue.headQueue();
                        System.out.printf("队列头数据是：%d\n",res);
                        System.out.println("--------------------------------");
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                        System.out.println("--------------------------------");
                    }
                    break;
                case 'e':
                    scanner.close();//关闭Scanner不然会有警告
                    loop = false;
                    break;
            }
        }
        System.out.println("--------------------------------");
        System.out.println("程序退出");
    }
}

    //所以数组模拟队列，编写一个ArrayQueue类
class ArrayQueue{
    private int maxSize; // 表示数组最大容量
    private int front; //表示队列头
    private int rear; // 表示队列尾
    private int[] arr; // 该数据用于存放数据，模拟队列

    // 创建队列构造器
    public ArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1; //指向队列头的前一个位置（不包含第一个数据）
        rear = -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++;
        arr[rear] = n;
    }

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

    //显示队列所有数据
    public void showQueue(){
        if (isEmpty()){
            System.out.println("队列空，不能显示数据");
            return;
        }
        for (int i = 0; i < arr.length; i++){
            System.out.printf("arr[%d]=%d\n",i,arr[i]);
        }
    }

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

3.3 循环数组

3.3.1 问题分析

解决上面3.3.2 中的问题，数组使用一次就不能在继续使用，没有达到复用的效果
改进：可以改进为环形队列 取模：%

3.3.2 思路分析

front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr[front] 就是队列的第一个元素，front的初始值 = 0
rear 变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间做为约定，rear的初始值 = 0
当队列满时，条件是（rear + 1）% maxSize == front【满】
判断为空：rear == front
队列中有效的数据的个数：（rear + maxSize - front）% maxSize

3.3.3 代码实现

import java.util.Scanner;

public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        //测试
        //创建环形队列
        CircleArray circleArray = new CircleArray(4);
        char key = ' '; //接收用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        //输出一个菜单
        while (loop){
            System.out.println("s(show)：显示队列");
            System.out.println("a(add)：添加数据到队列");
            System.out.println("g(get)：从队列中取出数据");
            System.out.println("h(head)：显示队列头的数据");
            System.out.println("e(exit)：退出程序");
            System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
            System.out.print("请输入：");
            key = scanner.next().charAt(0);
            switch (key){
                case 's' :
                    circleArray.showQueue();
                    System.out.println("--------------------------------");
                    break;
                case 'a' :
                    System.out.println("输入一个值：");
                    int value = scanner.nextInt();
                    circleArray.addQueue(value);
                    System.out.println("--------------------------------");
                    break;
                case 'g' :
                    try{
                        int res = circleArray.getQueue();
                        System.out.printf("取出的数据是：%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                        System.out.println("--------------------------------");
                    }
                    break;
                case 'h':
                    try{
                        int res = circleArray.headQueue();
                        System.out.printf("队列头数据是：%d\n",res);
                        System.out.println("--------------------------------");
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                        System.out.println("--------------------------------");
                    }
                    break;
                case 'e':
                    scanner.close();//关闭Scanner不然会有警告
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("--------------------------------");
        System.out.println("程序退出");
    }
}

    //所以数组模拟队列，编写一个CircleArray类
class CircleArray{
    private int maxSize; // 表示数组最大容量
    private int front; //表示队列头
    private int rear; // 表示队列尾
    private int[] arr; // 该数据用于存放数据，模拟队列

    // 创建队列构造器
    public CircleArray(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = 0; //front就指向队列的第一个元素，也就是说arr[front] 就是队列的第一个元素，front的初始值 = 0
        rear = 0; //rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间做为约定，rear的初始值 = 0
    }

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

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

    //添加数据到队列
    public void addQueue(int n){
        //判断队列是否满，如果满不能添加数据
        if (isFull()){
            System.out.println("队列满，不能添加数据");
            return;
        }
        //直接将数据加入
        arr[rear] = n;
        // 将 rear 后移 ，这里必须考虑取模
        rear = (rear + 1) % maxSize;
    }

    //取队列中的数据
    public int getQueue(){
        //判断队列是否为空
        if (isEmpty()){
            //通过抛出异常来处理
            throw new RuntimeException("队列空，不能取数据");
        }
        //这里需要分析出front是指向队列得第一个元素
        //1.先把front对于的值保持到一个临时变量
        int value = arr[front];
        //2.将front后移
        front = (front + 1) % maxSize;
        //3.将临时保存的变量返回
        return value;
    }

    //显示队列所有数据
    public void showQueue(){
        if (isEmpty()){
            System.out.println("队列空，不能显示数据");
            return;
        }
        for (int i = front; i < front + size(); i++){
            System.out.printf("arr[%d]=%d\n",i % maxSize,arr[i % maxSize]);
        }
    }

    //返回队列有效数据大小
    public int size(){
        return (rear + maxSize - front)  % maxSize;
    }

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

四、链表

4.1 单链表

4.1.1 单链表介绍

链表是以节点的方式存储
每个节点包含data域，next域
如图：发现链表的各个节点不一定连续存储
链表分带头节点的链表与不带头节点的链表，根据实际的需求来确定

4.1.2 单链表的创建与遍历分析实现

添加（创建）

先创建一个head头节点，作用就是表示单链表的头
后面我们每添加一个节点，就直接加入到链表的最后

遍历

通过一个辅助变量，帮助遍历整个链表

按照编号的顺序添加（中间插入）

首先找到新添加的节点的位置，是通过辅助变量（指针）
新的节点.next = temp.next
将temp.next = 新的节点

链表更新太简单不需要分析

链表删除

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

4.1.3 代码实现

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //测试
        //创建节点
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");

        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode3);
        singleLinkedList.addByOrder(heroNode3);

        //修改前显示
        System.out.println("————————————————修改前————————————————");
        singleLinkedList.showList();

        //修改节点的数据
        HeroNode heroNode5 = new HeroNode(2, "阿卢", "小麒麟");
        singleLinkedList.update(heroNode5);
        //修改后显示
        System.out.println("————————————————修改后————————————————");
        singleLinkedList.showList();

        //删除节点
        singleLinkedList.deleteList(1);
        System.out.println("————————————————删除后————————————————");
        singleLinkedList.showList();
    }
}

class SingleLinkedList{
    //先初始化头节点，头节点不要动
    private HeroNode head = new HeroNode(0,"","");

    //添加节点到单向列表,不考虑编号顺序
    //1.当前链表的最后节点
    //2.将最后这个节点的next指向新的节点
    public void add(HeroNode heroNode){
        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true){
            if (temp.next == null){
                break;
            }
            //如果没有找到就将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp指向了链表的最后
        //将最后这个节点的next 指向新的节点
        temp.next = heroNode;
    }

    //添加节点到单向列表,考虑编号顺序
    public void addByOrder(HeroNode heroNode){
        //因为head节点不能动，因此我们仍然通过指针变量来帮助我们找到添加的位置
        //因为我们找的temp是添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        boolean flag = false;//标识添加的编号是否存在，默认false
        //遍历链表，找到最后
        while (true){
            if (temp.next == null){//说明temp在链表最后，所以添加的位置可能位于最后
                break;
            }
            if (temp.next.no > heroNode.no){//位置找到了，就在temp的后面插入
                break;
            }else if (temp.next.no == heroNode.no){//说明希望添加的heroNode编号已经存在
                flag = true;
                break;
            }
            //如果没有找到就将temp后移,记住一定要后移
            temp = temp.next;
        }
        //判断flag的值
        if (flag){
            System.out.printf("准备插入的英雄编号：%d 已经存在不能在添加\n",heroNode.no);
        }else {
            /*
            1. 首先找到新添加的节点的位置，是通过辅助变量（指针）
            2. 新的节点.next = temp.next
            3. 将temp.next = 新的节点
             */
            heroNode.next = temp.next;//新插入的数据的下一个与temp数据的下一个个拉起来
            temp.next = heroNode;//temp的下一个数据指向新插入的数据
        }
    }

    //修改节点的信息，根据no编号来修改，即no不能修改
    public void update(HeroNode newHeroNode){
        if (head.next == null){
            System.out.println("链表为空无法修改！");
            return;
        }
        //根据no编号，找到需要修改的节点
        //定义一个辅助变量
        HeroNode temp = head.next;
        boolean flag = false;
        while(true){
            if (temp == null){
                break;//已经遍历完链表
            }
            if (temp.no == newHeroNode.no){
                //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag判断是否找到要修改的节点
        if (flag){
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        }else {//没有找到
            System.out.printf("没有找到编号为%d的节点，不能修改\n",newHeroNode.no);
        }
    }

    //显示链表
    public void showList(){
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 因为头节点不能动,因此需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true){
            if (temp == null){//判断链表最后
                break;
            }
            System.out.println(temp);//输出节点信息
            temp = temp.next;//将next后移
        }
    }

    //删除链表
    //思路1.head不能动，因此我们需要一个temp节点找到待删除节点的前一个节点
    //2.说明我们在比较的时候，是temp.next.no 和需要删除节点的no比较
    public void deleteList(int deleteHeroNode){
        HeroNode temp = head;
        boolean flag = false;//标志是否找到temp节点
        while (true){
            if (temp.next == null){//已经到达链表最后
                break;
            }
            if (temp.next.no == deleteHeroNode){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.next = temp.next.next;
        }else {
            System.out.printf("没有找到%d的节点\n",deleteHeroNode);
        }
    }
}

class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一个节点

    public HeroNode(int hNo,String hName,String hNickName){
        this.no = hNo;
        this.name = hName;
        this.nickname = hNickName;
    }

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

4.1.4 单链表新浪面试题

查询单链表中的倒数第k个节点思路：

编写一个方法，接收head节点，同时接收一个index
index 表示是倒数第index个节点
先把链表从头到尾遍历，得到链表的总长度，getLength
得到size后，我们从链表的第一个开始遍历（size - index）个，就可以得到
如果找到了，则返回该节点，否则返回null

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //测试
        //创建节点
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");

        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode3);

        singleLinkedList.showList();
        System.out.println("-----------------------------------");

        //查询个数
        System.out.printf("查询一共有%d个节点\n",getLength(singleLinkedList.getHead()));
        System.out.println("-----------------------------------");

        //查询倒数第K个节点
        int k = 2;
        HeroNode lastIndexNode = findLastIndexNode(singleLinkedList.getHead(), k);
        System.out.printf("查询倒数第%d个节点：%s",k,lastIndexNode);
    }

    //查询个数
    public static int getLength(HeroNode head){
        if (head.next == null){
            return 0;
        }
        int length = 0;
        HeroNode temp = head.next; //没有统计头节点
        while (temp != null){
            length++;
            temp = temp.next;
        }
        return length;
    }

    //查询单链表中的倒数第k个节点
    public static HeroNode findLastIndexNode(HeroNode head,int index){
        //判断链表是否为空
        if (head.next == null){
            return null;//没有找到
        }
        //第一个遍历得到链表的总长度
        int size = getLength(head);
        if (index <= 0 || index > size){
            return null;
        }
        //定义辅助变量，for循环单位倒数index
        HeroNode temp = head.next;
        for (int i = 0;i < size - index; i++){
            temp = temp.next;
        }
        return temp;
    }
}

class SingleLinkedList{
    //先初始化头节点，头节点不要动
    private HeroNode head = new HeroNode(0,"","");

    //返回头节点
    public HeroNode getHead() {
        return head;
    }

    //添加节点到单向列表,考虑编号顺序
    public void addByOrder(HeroNode heroNode){
        //因为head节点不能动，因此我们仍然通过指针变量来帮助我们找到添加的位置
        //因为我们找的temp是添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        boolean flag = false;//标识添加的编号是否存在，默认false
        //遍历链表，找到最后
        while (true){
            if (temp.next == null){//说明temp在链表最后，所以添加的位置可能位于最后
                break;
            }
            if (temp.next.no > heroNode.no){//位置找到了，就在temp的后面插入
                break;
            }else if (temp.next.no == heroNode.no){//说明希望添加的heroNode编号已经存在
                flag = true;
                break;
            }
            //如果没有找到就将temp后移,记住一定要后移
            temp = temp.next;
        }
        //判断flag的值
        if (flag){
            System.out.printf("准备插入的英雄编号：%d 已经存在不能在添加\n",heroNode.no);
        }else {
            /*
            1. 首先找到新添加的节点的位置，是通过辅助变量（指针）
            2. 新的节点.next = temp.next
            3. 将temp.next = 新的节点
             */
            heroNode.next = temp.next;//新插入的数据的下一个与temp数据的下一个个拉起来
            temp.next = heroNode;//temp的下一个数据指向新插入的数据
        }
    }

    //显示链表
    public void showList(){
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 因为头节点不能动,因此需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true){
            if (temp == null){//判断链表最后
                break;
            }
            System.out.println(temp);//输出节点信息
            temp = temp.next;//将next后移
        }
    }

}

class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一个节点

    public HeroNode(int hNo,String hName,String hNickName){
        this.no = hNo;
        this.name = hName;
        this.nickname = hNickName;
    }

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

4.1.5 单链表腾讯面试题

单链表反转思路：

先定义一个节点reverseHead = new HeroNode();
从头到尾遍历原来的链表，每遍历一个节点，并放在新的链表reverseHead 的最前端
原来链表的head.next = reverseHead .next

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //测试
        //创建节点
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");


        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode3);

        singleLinkedList.showList();
        System.out.println("-----------------------------------");
        reversetList(singleLinkedList.getHead());
        singleLinkedList.showList();
    }
    public static void reversetList(HeroNode head){
        //如果当前链表为空，或者只有一个节点，则无需反转，直接返回
        if (head.next == null || head.next.next == null){
            return;
        }

        HeroNode temp = head.next;//定义一个辅助的指针（变量），帮助我们遍历原来的链表
        HeroNode next = null;//指向当前节点temp的下一个节点
        HeroNode reverseHead = new HeroNode(0,"","");//新的链表
        //开始遍历原来的链表，每遍历一个节点，并放在新的链表reverseHead 的最前端
        while (temp != null){
            next = temp.next;//先暂时保存当前节点的下一个节点，后面需要使用
            temp.next = reverseHead.next;//将temp的下一个节点指向新的链表的最前端
            reverseHead.next = temp;//将temp连接到新的链表上
            temp = next;//让temp后移
        }
        //将head.next 指向 reverseHead.next，实现单链表的反转
        head.next = reverseHead.next;
    }
}

class SingleLinkedList{
    //先初始化头节点，头节点不要动
    private HeroNode head = new HeroNode(0,"","");

    //返回头节点
    public HeroNode getHead() {
        return head;
    }

    //添加节点到单向列表,考虑编号顺序
    public void addByOrder(HeroNode heroNode){
        //因为head节点不能动，因此我们仍然通过指针变量来帮助我们找到添加的位置
        //因为我们找的temp是添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true){
            if (temp.next == null){//说明temp在链表最后，所以添加的位置可能位于最后
                break;
            }
            //如果没有找到就将temp后移,记住一定要后移
            temp = temp.next;
        }
        temp.next = heroNode;//temp的下一个数据指向新插入的数据
    }

    //显示链表
    public void showList(){
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 因为头节点不能动,因此需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true){
            if (temp == null){//判断链表最后
                break;
            }
            System.out.println(temp);//输出节点信息
            temp = temp.next;//将next后移
        }
    }

}

class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一个节点

    public HeroNode(int hNo,String hName,String hNickName){
        this.no = hNo;
        this.name = hName;
        this.nickname = hNickName;
    }

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

4.1.6 单链表百度面试题

从尾到头打印单链表【百度，要求方式1：反向遍历。方式2：Stack栈】
思路：

上面题的要求就是进行逆序打印单链表
方式一：先将单链表进行反转操作，然后在遍历即可，这样的做法是会破坏原来单链表的结构的，不建议
方式二：可以利用栈这个数据结构，将各个节点压入栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果

import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //测试
        //创建节点
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");


        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode3);

        singleLinkedList.showList();
        System.out.println("-----------------------------------");
        System.out.println("测试栈逆序打印单链表！！！没有改变链表本身的结构");
        reversPrint(singleLinkedList.getHead());
    }
    public static void reversPrint(HeroNode head){
        if (head.next == null){
            return;//空列表不能打印
        }
        //创建栈将各节点压入栈
        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode temp = head.next;
        //将链表的所有节点压入栈
        while (temp != null){
            stack.push(temp);
            temp = temp.next;//temp后移，这样可以压入下一个节点
        }
        //将栈中的节点进行打印，pop出栈
        while (stack.size() > 0){
            System.out.println(stack.pop());//stack的特点是先进先出
        }
    }
}

class SingleLinkedList{
    //先初始化头节点，头节点不要动
    private HeroNode head = new HeroNode(0,"","");

    //返回头节点
    public HeroNode getHead() {
        return head;
    }

    //添加节点到单向列表,考虑编号顺序
    public void addByOrder(HeroNode heroNode){
        //因为head节点不能动，因此我们仍然通过指针变量来帮助我们找到添加的位置
        //因为我们找的temp是添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true){
            if (temp.next == null){//说明temp在链表最后，所以添加的位置可能位于最后
                break;
            }
            //如果没有找到就将temp后移,记住一定要后移
            temp = temp.next;
        }
        temp.next = heroNode;//temp的下一个数据指向新插入的数据
    }

    //显示链表
    public void showList(){
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 因为头节点不能动,因此需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true){
            if (temp == null){//判断链表最后
                break;
            }
            System.out.println(temp);//输出节点信息
            temp = temp.next;//将next后移
        }
    }
}

class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一个节点

    public HeroNode(int hNo,String hName,String hNickName){
        this.no = hNo;
        this.name = hName;
        this.nickname = hNickName;
    }

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

4.1.7 课后练习

合并两个有序的单链表，合并之后的链表依然有序

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //测试
        //创建节点
        HeroNode heroNode1 = new HeroNode(1, "1宋江", "1及时雨");
        HeroNode heroNode3 = new HeroNode(3, "3卢俊义", "3玉麒麟");
        HeroNode heroNode5 = new HeroNode(5, "5吴用", "5智多星");
        HeroNode heroNode7 = new HeroNode(7, "7林冲", "7豹子头");
        //创建A链表
        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
        singleLinkedList1.addByOrder(heroNode1);
        singleLinkedList1.addByOrder(heroNode3);
        singleLinkedList1.addByOrder(heroNode5);
        singleLinkedList1.addByOrder(heroNode7);
        singleLinkedList1.showList(singleLinkedList1.getHead());

        System.out.println("----------------分隔线---------------");

        HeroNode heroNode2 = new HeroNode(2, "2宋江", "2及时雨");
        HeroNode heroNode4 = new HeroNode(4, "4卢俊义", "4玉麒麟");
        HeroNode heroNode6 = new HeroNode(6, "6吴用", "6智多星");
        HeroNode heroNode8 = new HeroNode(8, "8林冲", "8豹子头");
        //创建B链表
        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
        singleLinkedList2.addByOrder(heroNode2);
        singleLinkedList2.addByOrder(heroNode4);
        singleLinkedList2.addByOrder(heroNode6);
        singleLinkedList2.addByOrder(heroNode8);
        singleLinkedList2.showList(singleLinkedList2.getHead());

        System.out.println("----------------分隔线---------------");

        HeroNode heroNode = mergeList(singleLinkedList1.getHead(), singleLinkedList2.getHead());
        singleLinkedList2.showList(heroNode);
    }
    public static HeroNode mergeList(HeroNode heroNode1,HeroNode heroNode2){
        //创建一个新的链表来存储两个链表中的值
        HeroNode resultNode = new HeroNode(0, "", "");
        HeroNode result = resultNode;           //因为head节点不能动，因此我们仍然通过指针变量来帮助我们找到添加的位置
        HeroNode temp1 = heroNode1.next;        //定义一个辅助的指针（变量），帮助我们遍历原来的链表
        HeroNode temp2 = heroNode2.next;        //定义一个辅助的指针（变量），帮助我们遍历原来的链表
        while (temp1 != null && temp2 != null){ //判断是否为空
            if (temp1.no <= temp2.no){          //判断temp1的数值大还是temp2的数值大
                result.next = temp1;            //如果temp1的数值小那么先插入temp1
                result = result.next;           //result指向新插入的节点
                temp1 = temp1.next;             //temp1指向新的节点
            }else{                              //否则就是temp2小，插入temp2
                result.next = temp2;            
                result = result.next;
                temp2 = temp2.next;
            }
        }
        if (temp1 == null) {                    //如果temp1为空temp2还有节点，那么循环遍历给result插入temp2
            while (temp2 != null) {
                result.next = temp2;
                result = result.next;
                temp2 = temp2.next;
            }
        } else {
            while (temp1 != null) {
                result.next = temp1;
                result = result.next;
                temp1 = temp1.next;
            }
        }
        return resultNode;
    }
}

class SingleLinkedList{
    //先初始化头节点，头节点不要动
    private HeroNode head = new HeroNode(0,"","");

    //返回头节点
    public HeroNode getHead() {
        return head;
    }

    //添加节点到单向列表,考虑编号顺序
    public void addByOrder(HeroNode heroNode){
        //因为head节点不能动，因此我们仍然通过指针变量来帮助我们找到添加的位置
        //因为我们找的temp是添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true){
            if (temp.next == null){//说明temp在链表最后，所以添加的位置可能位于最后
                break;
            }
            //如果没有找到就将temp后移,记住一定要后移
            temp = temp.next;
        }
        temp.next = heroNode;//temp的下一个数据指向新插入的数据
    }

    //显示链表
    public void showList(HeroNode heroNode){
        //判断链表是否为空
        if (heroNode.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 因为头节点不能动,因此需要一个辅助变量来遍历
        HeroNode temp = heroNode.next;
        while (temp != null){//判断链表最后
            System.out.println(temp);//输出节点信息
            temp = temp.next;//将next后移
        }
    }
}

class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一个节点

    public HeroNode(int hNo,String hName,String hNickName){
        this.no = hNo;
        this.name = hName;
        this.nickname = hNickName;
    }

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

4.2 双向链表

4.2.1 分析与介绍

单向链表，查找的方向只可能是一个方向，二双向链表可以向前或后查找
单向链表不能自我删除，需要辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp的下一个节点来删除
示意图：

双向链表遍历：

遍历方式与单链表一样，只是可以向前，也可以向后查找

双向链表添加：（默认添加到最后）

先找到双向链表的最后节点
temp.next = newHeroNode
newHeroNode.pre = temp

双向链表修改：

思路与原来的单向链表一样

双向链表修改：

因为是双向链表，因此可以实现自我删除
直接找到要删除的节点，比如temp
temp.pre = temp.next ?该节点的上一个节点指向该节点的下一个节点
temp.next.pre = temp.pre ?该节点的下一个节点的上一个节点的指向，改为该节点的上一个节点（仔细读）

双向链表删除图解：
在这里插入图片描述
双向链表按照顺序插入（中间插入）图解：

4.2.2 代码实现

public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        //测试
        System.out.println("--------------添加测试--------------");
        //创建节点
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");
        //创建双向链表（添加测试）
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(heroNode1);
        doubleLinkedList.add(heroNode2);
        doubleLinkedList.add(heroNode3);
        doubleLinkedList.add(heroNode4);

        //添加测试
        doubleLinkedList.showList();
        System.out.println("--------------修改测试--------------");

        HeroNode update = new HeroNode(2, "小卢", "小麒麟");
        doubleLinkedList.update(update);
        doubleLinkedList.showList();

        System.out.println("--------------删除测试--------------");
        doubleLinkedList.deleteLink(4);
        doubleLinkedList.showList();

        System.out.println("--------------顺序插入测试--------------");
        DoubleLinkedList doubleLinkedList2 = new DoubleLinkedList();
        doubleLinkedList2.addOrderBy(heroNode4);
        doubleLinkedList2.addOrderBy(heroNode1);
        doubleLinkedList2.addOrderBy(heroNode3);
        doubleLinkedList2.addOrderBy(heroNode2);

        doubleLinkedList2.showList();
    }
}

//创建双向链表的类
class DoubleLinkedList{
    private HeroNode head = new HeroNode(0,"","");

    public HeroNode getHead() {
        return head;
    }

    //
    //双向链表顺序添加
    public void addOrderBy(HeroNode newData){
        HeroNode temp = head;           //辅助变量，head节点不能动
        boolean flag = false;
        while (true){                   //遍历链表找到最后
            if (temp.next == null){     //判断是否为最后
                break;
            }else if (temp.next.no > newData.no){
                break;
            }else if(temp.next.no == newData.no){
                flag = true;
                break;
            }
            temp = temp.next;           //如果没有找到最后，将temp后移
        }                               //当while退出代表已经找到了最后
        if (flag){
            System.out.println("已经存在");
        }else{
            if (temp.next == null){
                temp.next = newData;
                newData.pre = temp;
            }else{
                newData.next = temp.next;
                temp.next.pre = newData;
                newData.pre = temp;
                temp.next = newData;
            }
        }
    }

    //删除双向链表的节点
    public void deleteLink(int no){
        if (head.next == null){
            System.out.println("链表为空不能删除！");
            return;
        }
        HeroNode temp = head.next;           //辅助变量
        boolean flag = false;           //标志是否得到要删除的节点
        while (true){
            if (temp == null){          //已经到达该链表的最后
                break;
            }
            if (temp.no == no){         //找到要删除的节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.pre.next = temp.next;       //双向链表进行删除
            if (temp.next != null){
                temp.next.pre = temp.pre;        //如果是最后一个就不需要执行这句话，否则会出空指针
            }
        }else {
            System.out.printf("没有找到%d节点",no);
        }
    }

    //双向链表修改,修改与单向链表相同
    public void update(HeroNode newHeroNode){
        if (head.next == null){
            return;
        }
        boolean flag = false;
        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                break;                          //已经遍历完成
            }
            if (temp.no == newHeroNode.no){
                flag = true;                    //找到节点
                break;
            }
            temp = temp.next;
        }
        if (flag){              //根据flag判断是否找到要修改的节点
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        }else {
            System.out.printf("没有找到%d节点",newHeroNode.no);
        }
    }

    //双向链表添加
    public void add(HeroNode heroNode){
        HeroNode temp = head;           //辅助变量，head节点不能动
        while (true){                   //遍历链表找到最后
            if (temp.next == null){     //判断是否为最后
                break;
            }
            temp = temp.next;           //如果没有找到最后，将temp后移
        }                               //当while退出代表已经找到了最后
        temp.next = heroNode;           //然后给temp的最后添加上传入的节点
        heroNode.pre = temp;
    }

    //遍历双向链表的方法
    public void showList(){
        if (head.next == null){         //判断是否为空
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;      //因为头节点不能动，所以定义一个辅助变量
        while (true){
            if (temp == null){          //判断是否为链表最后
                break;
            }
            System.out.println(temp);   //输出节点信息
            temp = temp.next;           //temp后移
        }
    }
}

//创建一个双向链表的类
class HeroNode{
    public int no;
    public String name;
    public String nickName;
    public HeroNode next; //指向下一个节点
    public HeroNode pre;  //指向上一个节点

    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 + '\'' +
                '}';
    }
}

4.3 单向环形链表

4.3.1 分析与介绍

网上找到了一个印象深刻的回答：
????据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏
图解：
在这里插入图片描述
思路分析：

添加节点

先创建一个节点，让first指向该节点，并形成环形
后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可

遍历环形链表

先让一个辅助指针（变量），指向first节点
然后通过一个while循环遍历该环形链表即可curBoy.next == first结束

约瑟夫问题实现思路：

需要先创建一个辅助指针（变量）temp，事先应该指向环形链表的最后这个节点
报数前，先让first和temp移动k - 1次
当小孩报数时，让first和temp指针同时移动m - 1次，这时就可以将first指向的小孩节点出圈
first = first.next
temp.next = first
原来的first指向的节点就没有任何引用，就会被回收

4.3.2 代码实现

public class Josepfu {
    public static void main(String[] args) {
        //测试
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);

        circleSingleLinkedList.showLink();
        System.out.println("-----------------分割线-----------------");
        circleSingleLinkedList.countBoy(1,2,5);
    }
}

//创建环形单向链表
class CircleSingleLinkedList{
    //创建一个first节点，当前没有编号
    private Boy first = new Boy(-1);

    //添加小孩，构建成一个环形的链表
    public void addBoy(int nums){
        if (nums < 1){                              //数据校验
            System.out.println("nums值不正确");
            return;
        }
        Boy temp = null;                            //添加一个小孩节点，构建成一个环形的链表
        for (int i = 1; i <= nums; i++){            //使用for来创建环形链表
            Boy boy = new Boy(i);                   //根据编号来创建节点
            if (i == 1){                            //如果是第一个小孩节点
                first = boy;
                first.setNext(first);               //构成环
                temp = first;                       //让temp指向第一个节点
            }else {
                temp.setNext(boy);
                boy.setNext(first);
                temp = boy;
            }
        }
    }

    //遍历当前所以节点
    public void showLink(){
        //判断链表是否为空
        if (first == null){
            System.out.println("没有任何小孩");
        }
        //first不能动
        Boy temp = first;
        while (true){
            System.out.printf("小孩的编号为：%d\n",temp.getNo());
            if (temp.getNext() == first){       //说明已经遍历完毕
                break;
            }
            temp = temp.getNext();              //让temp指向下一个节点
        }
    }

    /**
     * 根据用户的输入，计算出小孩出圈的顺序
     * @param startNo 表示从第几个小孩开始数
     * @param countNum  表示数几下
     * @param nums  表示最初有多少小孩在圈中，目的是检验
     */
    public void countBoy(int startNo,int countNum,int nums){
        //先对数据进行检验
        if (first == null || startNo < 1 || startNo > nums){
            System.out.println("参数输入有误，请重新输入");
            return;
        }
        //创建辅助指针，帮助完成小孩出圈
        Boy temp = first;
        //temp指向最后一个节点
        while (true){
            if (temp.getNext() == first){ //说明temp到了最后一个节点
                break;
            }
            temp = temp.getNext();
        }

        //报数前先让first和temp移动k - 1 次
        for (int j = 0; j < startNo - 1; j++){
            first = first.getNext();
            temp = temp.getNext();
        }

        //当小孩报数前，让first和temp指针同时移动m - 1次，这时就可以将first指向的小孩节点出圈
        //循环操作直到圈中只有一个节点
        while (true){
            if (temp == first){ //说明只有一个节点
                break;
            }
            //否则让first和temp指针同时移动countNum - 1
            for (int j = 0; j < countNum - 1; j++){
                first = first.getNext();
                temp = temp.getNext();
            }
            //这时first指向的节点，就是要出圈的小孩节点
            System.out.printf("小孩%d出圈\n",first.getNo());
            //这时将first指向的小孩节点出圈
            first = first.getNext();
            temp.setNext(first);
        }
        System.out.printf("最后留在圈中的小孩编号%d\n",first.getNo());//最后temp与first相同
    }
}

//创建一个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;
    }
}

五、栈

5.1 栈的基本实现

5.1.1 栈（stack）的使用场景与介绍

介绍：

栈式=是一个先入后出的有序列表
栈是限制限制列表中元素的插入与删除只能在线性表的同一端进行的一种特殊线性表，称为栈底
根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

栈的示意图：出栈(pop),入栈(push)
在这里插入图片描述
栈（stack）的应用场景：

子程序的调用：在跳往子程序前，会先将下一个指令的地址存到堆栈中，直到子程序执行完后在将地址取出，以回到原来的程序中
处理递归调用：和子程序的调用类似，只是除了存储下一个指令的地址外，也将参数，区域变量等数据存入堆栈中
表达式的转换【中缀表达式转后缀表达式】与求值
二叉树遍历
图的深度优先搜索

5.1.2 思路分析

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

5.1.3 代码实现

import java.util.Scanner;

public class ArrayStackDemo {
    public static void main(String[] args) {
        //测试
        ArrayStack arrayStack = new ArrayStack(5);
        boolean loop = true;  //判断是否退出栈
        Scanner scanner = new Scanner(System.in);
        String key = "";
        while (loop){
            System.out.println("show：显示栈");
            System.out.println("exit：退出栈");
            System.out.println("push：出栈");
            System.out.println("pop：入栈");
            System.out.print("请输入：");
            key = scanner.next();
            switch (key){
                case "show":
                    arrayStack.showStack();
                    System.out.println("------------------分割线------------------");
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                case "push":
                    System.out.print("请输入一个值：");
                    int i = scanner.nextInt();
                    arrayStack.push(i);
                    System.out.println("------------------分割线------------------");
                    break;
                case "pop":
                    try {
                        int res = arrayStack.pop();
                        System.out.printf("出栈的数据是：%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    System.out.println("------------------分割线------------------");
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出！");
    }
}

//定义ArrayStack类,表示栈
class ArrayStack{
    private int maxSize;//栈的大小
    private int[] stack;//数组，数组模拟栈，数据就放在该数组
    private int top = -1;//top表示栈顶，初始化为-1

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

    //栈满
    public boolean isFull(){
        return top == maxSize - 1;
    }

    //栈空
    public boolean isEmpty(){
        return top == -1;
    }

    //入栈
    public void push(int values){
        if (isFull()){//先判断是否满了
            System.out.println("栈已经满了");
            return;
        }
        top++;
        stack[top] = values;
    }

    //出栈
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("栈空，取完了");
        }
        int value = stack[top];
        top--;
        return value;
    }

    //显示栈中的数据
    public void showStack(){
        if (isEmpty()){
            System.out.println("栈空没有数据了");
            return;
        }
        //从栈顶开始遍历
        for (int i = top; i >= 0; i--){
            System.out.printf("取出stack[%d] = %d\n",i,stack[i]);
        }
    }
}

5.1.4 课后作业(链表的先进后出)：

方法一：创建一个新的节点，每取一个节点都放在新节点的前面，方法一大多时候不会使用，因为会破坏原来链表的数据结构，但是也需要掌握
方法一图解：
方法二：栈
方法三：使用for循环遍历

import java.util.Stack;

public class ArrayStackDemo {
    public static void main(String[] args) {
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.positiveSequence(heroNode1);
        singleLinkedList.positiveSequence(heroNode2);
        singleLinkedList.positiveSequence(heroNode3);
        singleLinkedList.positiveSequence(heroNode4);
        System.out.println("-----------------------普通按照正序打印-----------------------");
        singleLinkedList.showLink();

        System.out.println("-----------------------栈方法二逆序打印链表-----------------------");
        singleLinkedList.reverseOrder2(singleLinkedList.getHead());

        System.out.println("-----------------------for方法三逆序打印链表-----------------------");
        singleLinkedList.reverseOrder3();

        System.out.println("-----------------------栈方法一逆序打印链表-----------------------");
        singleLinkedList.reverseOrder1(singleLinkedList.getHead());
        singleLinkedList.showLink();
    }
}

class SingleLinkedList{
    public HeroNode head = new HeroNode(0,"","");

    public HeroNode getHead() {
        return head;
    }

    //添加节点进入链表
    public void positiveSequence(HeroNode heroNode){
        HeroNode temp = head;

        while (true){
            if (temp.next == null){
                break;
            }
            temp = temp.next;
        }
        temp.next = heroNode;
    }

    //正常从头到尾显示链表节点
    public void showLink(){
        if (head.next == null){
            System.out.println("列表为空");
            return;
        }
        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

    //逆序输出链表方法一：创建一个新的节点，每取一个节点都放在新节点的前面
    //方法一大多时候不会使用，因为会破坏原来链表的数据结构
    public void reverseOrder1(HeroNode oldNode){
        if (oldNode.next == null || oldNode.next.next == null){
            return;
        }
        HeroNode newNode = new HeroNode(0, "", "");//定义一个新节点
        HeroNode temp = oldNode.next;
        HeroNode next = null;       //定义一个空存储
        while (temp != null){
            next = temp.next;       //存储temp的下一个节点
            temp.next = newNode.next;
            newNode.next = temp;
            temp = next;            //temp后移
        }
        oldNode.next = newNode.next;
    }

    //逆序输出链表方法二：栈
    public void reverseOrder2(HeroNode heroNode){
        if (head.next == null){
            System.out.println("链表为空！");
            return;
        }
        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode temp = head.next;
        //将链表节点放入栈
        while (temp != null){
            stack.push(temp);
            temp = temp.next;
        }
        //将链表节点逆序取出
        while (!stack.empty()){
            //stack.peek()方法是Java封装的栈逆序打印方法
            System.out.println(stack.peek());
            stack.pop();
        }
    }

    //逆序输出链表：使用for循环遍历
    public void reverseOrder3(){
        if (head.next == null){ //判断链表是否为空
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;//定义辅助变量，帮助找到一共有多少节点
        int length = 0;//存储节点个数
        while (true){
            if (temp == null){//判断是否到达最后节点
                break;
            }
            length++;//让如果循环时候该节点不为空length+1
            temp = temp.next;//辅助变量自加一
        }
        //循环次数小于length，带上0刚刚好是节点的个数，目的：得到打印第一个节点，或者第二个节点
        for (int i = 0; i < length; i++){
            HeroNode cur = head;//每次循环for重新更新cur辅助节点
            int j = 0;//保存循环次数，作用：到达一定次数，重新开始循环
            while (j < length - i) {//循环到达倒数第几个节点
                j++;//进入一次循环记录一次
                cur = cur.next;//辅助遍历移动到下一个节点
            }
            //while循环结束表示到达倒数第几个节点，所以打印，然后重新循环打印该节点的上一个节点
            System.out.println(cur);
        }
    }
}

class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一个节点

    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 + '\'' +
                '}';
    }
}

5.1.5 栈实现综合计算（中缀表达式）

思路：

通过一个index值（索引），来遍历我们的表达式
如果我们发现是一个数字，就直接入数栈
如果发现扫描到是一个符号，就分如下情况
3.1 如果方向当前的符号栈为空，就直接入栈
3.2 如果符号栈有操作符，就进行比较，如果当前的操作符优先级小于等于栈中的操作符，
就需要从数栈中pop出两个数，在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后
将当前的操作符入符号栈，如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈
当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行，
最后在数栈只有一个数字，就是表达式的结果

public class ArrayStackDemo {
    public static void main(String[] args) {
        //测试
        String expression = "70+2*6-4";
        ArrayStack numStack = new ArrayStack(10);
        ArrayStack operStack = new ArrayStack(10);
        int index = 0;//用于扫描
        int num1 = 0;
        int num2 = 0;
        int oper = 0; //存储运算符
        int res = 0; //存储结果
        char ch = ' ';//将每次扫描得到char保存到ch
        String keepNum = "";//用于拼接
        //开始while循环的扫描expression
        while (true){//开始循环扫描expression
            ch = expression.substring(index, index + 1).charAt(0);//循环得到字符串中的每一个字符
            if (operStack.isOper(ch)){                            //如果是运算符
                if (!operStack.isEmpty()){                        //判断符号栈不为空
                    //如果符号栈有操作符，就进行比较
                    //如果当前的操作符优先级小于等于栈中的操作符，就需要从数栈中pop出两个数
                    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);//因为计算机中的数字’字符串‘相差48，0就是48，如果要存储数字，需要做转换，进行减48
                //分析解决：
                //1.处理多位数时，不能是一个数就立即入栈，因为他可能是多位数
                //2.当处理数，需要向expression的表达式的index后，在看一位，如果是数继续扫描如果是运算符才能入栈
                //3.因此我们需要定义一个字符串变量，用于拼接
                keepNum += ch;

                //如果ch已经是expression的最后一位，就直接入栈
                if (index == expression.length() - 1){
                    numStack.push(Integer.parseInt(keepNum));
                }else {
                    //判断下一个字符是否为数字，如果是继续扫描，如果不是运算符就入栈
                    if(operStack.isOper(expression.substring(index+1,index+2).charAt(0))){
                        //如果后一位是运算符，则入栈,keepNum = "1" 或者 = "2"
                        numStack.push(Integer.parseInt(keepNum));
                        //初始化keepNum
                        keepNum = "";
                    }
                }
            }
            index++;//让index加一，判断是否到达expression的最后
            if (index >= expression.length()){
                break;
            }
        }
        //当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行
        while (true){
            if (operStack.isEmpty()){
                //如果符号栈为空则计算最后的结果，数栈中只有一个数字
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = operStack.cal(num1,num2,oper);
            numStack.push(res);//将得到结果，入数栈
        }
        //最后将数栈最后一个数字pop出
        System.out.printf("表达式为：%s = %d",expression,numStack.pop());
    }
}

class ArrayStack{
    private int maxSize;
    private int[] stack;
    private int top = -1;

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

    //判断栈是否为满
    public boolean isFull(){
        return top == maxSize -1;
    }

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

    //返回当前栈顶的值，但不是真正的pop
    public int peek(){
        return stack[top];
    }

    //入栈
    public void push(int values){
        if (isFull()){
            System.out.println("栈满了");
            return;
        }
        top++;
        stack[top] = values;
    }

    //出栈
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("栈空，取完了");
        }
        int value = stack[top];
        top--;
        return value;
    }

    //显示栈中的数据
    public void showStack(){
        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 priority(int 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; // 注意顺序
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;// 注意顺序
                break;
            default:
                break;
        }
        return res;
    }
}