线性结构

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

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

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

• 线性结构常见的有：
  
  数组、队列、链表和栈
  
  。

1、稀疏数组

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

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

• 稀疏数组的处理方法是:

  • 记录数组
    
    一共有几行几列，有多少个不同
    
    的值 。

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

• 
  二维数组转稀疏数组的思路
  
  • 遍历 原始的二维数组，得到有效数据的个数 sum。
  • 根据sum 就可以创建 稀疏数组 sparseArr int[sum + 1] [3]。
  • 将二维数组的有效数据数据存入到 稀疏数组。
• 
  稀疏数组转原始的二维数组的思路
  
  • 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2 = int[11] [11]。
  • 在读取稀疏数组后几行的数据，并赋给 原始的二维数组 即可。

import java.io.*;

public class SparseArray01 {
    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] = 2;

        //输出原始的二维数组
        System.out.println("原始的二维数组：");
        for (int[] arr : chessArr1){
            for (int value : arr){
                System.out.print(value + "\t");
            }
            System.out.println();
        }

        //将二维数组转为稀疏数组
        //1、先遍历二维数组得到非0元素的个数
        int sum = 0;

        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[i].length; j++) {
                if (chessArr1[i][j] != 0) {
                    sum++;
                }
            }
        }

//        System.out.println("有效元素的个数 sum = " + 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;  //count 用于记录是第几个非0数据

        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[i].length; 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[] arr : sparseArr){
            for (int value : arr){
                System.out.print(value + "\t");
            }
            System.out.println();
        }



        //将稀疏数组写入到磁盘中
        FileWriter fw = null;
        try {
            fw = new FileWriter(new File("map.data"));
            for (int i = 0; i < sparseArr.length; i++) {
                for (int j = 0; j < sparseArr[i].length; j++) {
                    fw.write(sparseArr[i][j]+"\t");
                }
                fw.write("\t\n");
            }
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (fw != null){
                try {
                    fw.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }

        //读取文件中的稀疏数组
        BufferedReader br = null;
        try {
            br = new BufferedReader(new FileReader(new File("map.data")));
            String value;  //一行的记录
            int row = 0;   //记录行号

            if ((value = br.readLine()) != null) {
                String[] split = value.split("\t");

                sparseArr[row][0] = Integer.parseInt(split[0]);
                sparseArr[row][1] = Integer.parseInt(split[1]);
                sparseArr[row][2] = Integer.parseInt(split[2]);

                row++;
            }
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            if (br != null) {
                try {
                    br.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }

        //将稀疏数组  --->  恢复成 原始的二维数组
        /*
            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();
        System.out.println("恢复后的二维数组：");

        for (int[] arr : chessArr2){
            for (int value : arr){
                System.out.print(value + "\t");
            }
            System.out.println();
        }

    }
}

2、队列

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

• 队列
  
  只允许在一端进行插入操作，而在另一端进行删除操作的线性表
  
  。

• 
  允许插入的一端称为队尾，允许删除的一端称为对头
  
  。

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

2.1、数组模拟队列

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

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

• 当我们将数据存入队列时称为”addQueue”，
  
  addQueue 的处理需要有两个步骤
  
  ：

  • 将尾指针往后移：rear+1 , 当 front == rear 【空】

  • 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。rear == maxSize – 1 【队列满】

import java.util.Scanner;

public class ArrayQueue01 {
    public static void main(String[] args) {
        //创建一个队列
        ArrayQueue queue = new ArrayQueue(3);

        char key = ' ';   //接收用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;

        //输出一个菜单
        while (loop) {
            System.out.println("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.show();
                    break;
                case 'a' :      //添加数据到队列
                    System.out.println("请输入添加的数据：");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g' :      //取出数据的时候要捕获异常
                    try {
                        int k = queue.getQueue();
                        System.out.println("取出的数据为：\n" + k);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());  //输出异常信息
                    }

                    break;
                case 'h' :      //查看队列的头元素，需要捕获异常
                    try {
                        int i = queue.headQueue();
                        System.out.println("队列的头元素为：\n" + i);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }

                    break;

                case 'e' :      //退出程序
                    scanner.close();
                    loop = false;
                    break;
            }
        }

        System.out.println("程序退出！");

    }
}

//使用数组模拟队列，
class ArrayQueue {
    private int maxSize;   //表示数组的最大容量
    private int front;      //队列头
    private int rear;       //队列尾
    private int[] arr;      //该数组用于存放数据，模拟队列

    //创建数组的构造器
    public ArrayQueue(int maxSize){
        this.maxSize = maxSize;
        arr = new int[maxSize];
        front = -1;     //front指向队列头的前一个元素
        rear = -1;      //指向队尾的数据（即就是队列的最后一个数据）
    }

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

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

    //添加数据到队列
    public void addQueue(int n){
        //1、判断队列是否满
        if (isFull()) {
            System.out.println("队列已满，添加失败！");
            return;
        }

        rear++;     //rear向后移动
        arr[rear] = n;
    }

    //获取队列的数据，出队列
    public int getQueue() {
        //判断队列是否为空
        if (isEmpty()){
            //通过抛出异常
            throw new RuntimeException("队列为空，无法取出数据！");
        }

        front++;    //front后移
        return arr[front];
    }

    //显示队列的所有元素
    public void show() {
        //遍历数组
        //先判断数组是否为空
        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];
    }
}

• 问题分析并优化
  • 目前数组使用一次就不能用， 没有达到复用的效果
  • 将这个数组使用算法，改进成一个
    
    环形的队列
    
    取模：%。

2.1.1、环形队列

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

• rear == front 【空】

基础思路

：

• 
  front指向队列的第一个元素，也就是arr[front]就是队列的第一个元素，front的初始值为0
  
  。

• 
  rear指向队列最后一个元素的后一个位置，留出一个元素空间，当队列满时，数组中还有一个空闲单位，rear的初始值为0
  
  。

• 如何判断环形队列为空，为满有两种判断方法。

  • 
    一是附加一个标志位flag
    

    • 当front赶上rear，队列空，则令flag=0,
    • 当rear赶上front，队列满，则令flag=1。

  • 
    二是队尾结点与队首结点之间至少留有一个元素的空间
    
    （
    
    常用的一种
    
    ），当队列满时，数组中还有一个空位。

    • 当
      
      队列满
      
      时，条件是**(rear + 1) % maxSize == front**。
    • 当
      
      队列为空
      
      的条件是，
      
      rear == front
      
      。
    • 队列中
      
      有效的数据
      
      的个数为
      
      (rear + maxSize – front) % maxSize
      
      //rear = 1，front = 0
      • 
        解析
        
        ：当rear > front时，此时队列的长度为rear – front。但当rear < front时，队列的长度分为两段，一段是maxSize – front，另一段是0 + rear，加在一起长度为：rear – front + maxSize。因此通用长度表达式为：
      • 
        (rear + maxSize – front) % maxSize
        

import java.util.Scanner;

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

        System.out.println("用数组模拟环形队列的案例");
        //创建一个环形队列
        CircleArray queue = new CircleArray(4);     //设置为4.队列有效数据最大为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.show();
                    break;
                case 'a' :      //添加数据到队列
                    System.out.println("请输入添加的数据：");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g' :      //取出数据的时候要捕获异常
                    try {
                        int k = queue.getQueue();
                        System.out.println("取出的数据为：\n" + k);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());  //输出异常信息
                    }

                    break;
                case 'h' :      //查看队列的头元素，需要捕获异常
                    try {
                        int i = queue.headQueue();
                        System.out.println("队列的头元素为：\n" + i);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }

                    break;

                case 'e' :      //退出程序
                    scanner.close();
                    loop = false;
                    break;
            }
        }

        System.out.println("程序退出！");
    }
}

class CircleArray {
    private int maxSize;   //表示数组的最大容量
    //front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素 front的初始值为 = 0
    private int front;      //队列头
    //rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间作为约定，rear的初始值 = 0
    private int rear;       //队列尾
    private int[] arr;      //该数组用于存放数据，模拟队列

    public CircleArray(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
        //默认为0，可以不写
//        front = 0;
//        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对应的值保存到一个临时变量，如果直接输出对应的值那么front就没有机会后移
        2、将front后移,需要考虑取模
        3、将临时保存的变量返回
         */
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;
    }

    //显示队列的所有元素
    public void show() {
        //判断队列是否为空
        if (isEmpty()) {
            System.out.println("队列为空，没有元素!");
            return;
        }

        //从front开始遍历
        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];
    }

}

3、链表

• 链表是有序的列表，链表是以节点的方式来存储,
  
  是链式存储。
  

• 每个节点包含 data 域：存储数据元素信息， next 域：指向下一个节点。

• 
  链表的各个节点不一定是连续存储
  
  ，是用一组任意的存储单元存储线性的数据元素，这组存储单元可以是连续的，也可以是不连续的。

• 链表分
  
  带头节点的链表
  
  和
  
  没有头节点的链表
  
  ，根据实际的需求来确定。

• 
  链表中第一个节点的存储位置叫做头指针
  
  。

• 
  有时候会在单链表的第一个节点前附加一个节点，称为头节点，头节点的数据域可以不附加任何信息，也可以存储线性表的长度等附加信息，头节点的指针域存储指向第一个节点的指针
  
  。

• 
  头节点与头指针的异同
  

  • 
    头指针
    
    ：
    • 头指针是指链表指向第一个节点的指针，若链表有头节点，则是指向头节点的指针。
    • 头指针具有标识作用，所以常用头指针冠以链表的名字。
    • 无论链表为空，头指针均不为空，
      
      头指针是链表的必要元素
      
      。
  • 
    头节点
    
    ：
    • 头节点是为了操作的统一的方便二设立的，放在第一个元素的节点之前，其数据域一般无意义（也可以存放链表的长度）
    • 有了头节点，对在第一个元素节点前插入节点和删除第一个节点，其操作与其他节点的操作就统一了。
    • 
      头节点不一定是链表必要元素
      
      。

3.1、单链表

• 
  链表的每个节点只包含一个指针域，所以叫做单链表
  
  。
• 
  单链表的添加
  
  • 第一种添加方式：
    
    按照顺序添加
    
    • 直接添加到链表的尾部。
  • 第二种添加方式：
    
    添加到指定位置
    

    • 

    • 首先找到新添加的节点的位置, 是通过辅助变量(指针), 通过遍历来搞定。

    • 
      新的节点.next = temp.next
      
      。

    • 将
      
      temp.next = 新的节点
      
      。

• 
  单链表的删除
  
  • 我们先找到 需要删除的这个节点的
    
    前一个节点 temp
    
    。
  • 
    temp.next = temp.next.next
    
    。
  • 被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收。
• 
  单链表的修改
  
  • 通过编号找到需要修改的节点，来修改内容。
• 创建一个单链表，实现单链表的添加（两种），修改，删除

public class SingleLikedListDemo {
    public static void main(String[] args) {
        //测试
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

        //创建链表
        SingleLikedList singleLikedList = new SingleLikedList();
        //添加
//        singleLikedList.add(hero1);
//        singleLikedList.add(hero2);
//        singleLikedList.add(hero3);
//        singleLikedList.add(hero4);

        //添加，按照编号的顺序
        singleLikedList.addOrder(hero1);
        singleLikedList.addOrder(hero4);
        singleLikedList.addOrder(hero2);
        singleLikedList.addOrder(hero3);
        //显示链表
        singleLikedList.list();

        //修改节点
        HeroNode newHeroNode = new HeroNode(4, "鲁智深", "花和尚");
        singleLikedList.update(newHeroNode);
        System.out.println("修改后的链表情况");
        //显示链表
        singleLikedList.list();

        //删除节点
        singleLikedList.del(1);
        singleLikedList.del(4);
        System.out.println("删除节点后的链表");
        //显示链表
        singleLikedList.list();
    }
}

//定义SingleLikedList 管理我们的元素
class SingleLikedList {
    //先初始化一个头节点，头节点不要移动，不存放具体的数据
    private HeroNode head = new HeroNode(0,"","");

    public HeroNode getHead() {
        return head;
    }

    //添加节点到单向链表
    //当不考虑编号的顺序时
    //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 addOrder(HeroNode heroNode) {
        /*
            因为头节点不能移动，因此我们需要一个辅助指针（变量）来帮助我们找到添加的位置
            我们找的temp是位于添加位置的前一个节点，否则插入不了
         */
        HeroNode temp = head;
        boolean flag = false;   //添加的编号是否存在，默认为false不存在

        while (true) {
            if (temp.next == null) {    //说明已经在链表的最后
                break;
            }

            if (temp.next.no > heroNode.no) {   //位置找到，就在temp的后面插入
                break;
            } else if (temp.next.no == heroNode.no) {   //说明希望添加的编号已经存在
                flag = true;    //说明编号已经存在
                break;
            }
            temp = temp.next;   //temp后移遍历链表
        }

        //判断flag的值
        if (flag) { //不能添加说明编号存在
            System.out.println("准备插入的英雄编号："+heroNode.no+"已经存在,不能添加");
        } else {
            /*
                此时temp指向需要插入位置的前一个节点
                temp.next就是需要处于插入位置的那个节点，此时再将temp.next赋值给heroNode.next，需要插入的heroNode节点就指向了
                处于插入位置的那个节点，再将heroNode赋值给temp.next,插入位置的前一个节点就指向了需要插入的节点，完成插入。
             */
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //修改节点的信息，根据no编号来修改，即no编号不能修改
    /*
        说明：
        1、根据 newHeroNode的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;   //temp后移
        }
        //根据flag判断是否找到要修改的节点
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        } else {    //没有找到
            System.out.println("没有编号为："+newHeroNode.no+"的节点可以进行修改");
        }
    }

    //删除节点
    /*
        思路：
        1、head不能移动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
        2、说明我们在比较的时，是temp.next.no 和需要删除的节点的no值进行比较
     */
    public void del(int no) {
        HeroNode temp = head;
        boolean flag = false;   //标志是否找到待删除的节点

        while (true) {
            if (temp.next == null) {    //已经到链表最后
                break;
            }
            if (temp.next.no == no) {
                //找到待删除节点的前一个节点temp
                flag = true;
                break;
            }
            temp = temp.next;   //temp后移，遍历链表
        }
        //判断flag
        if (flag) {     //找到
            //删除
            temp.next = temp.next.next;
        } else {
            System.out.println("没有找到编号为："+no+"的节点");
        }
    }

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

//定义一个HeroNode，每个HeroNode对象就是一个节点
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;
    }

    //为了显示方便，我们重写toString方法
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

三道面试题

1. 查找单链表中的倒数第k个节点

public class SingleLinkedTest1 {
    public static void main(String[] args) {
        //测试
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "林冲", "豹子头");
        HeroNode hero4 = new HeroNode(4, "吴用", "智多星");

        //创建链表
        SingleLikedList singleLikedList = new SingleLikedList();

        //加入按照编号的顺序
        singleLikedList.addOrder(hero1);
        singleLikedList.addOrder(hero3);
        singleLikedList.addOrder(hero4);
        singleLikedList.addOrder(hero2);
        //显示链表
        singleLikedList.list();

        //得到了倒数第k个节点
        System.out.println("res = "+findLastIndexNode(singleLikedList.getHead(), 2));
    }

    //查找单链表中的倒数第k个节点(面试题1)
    /*
        思路：
        1、编写一个方法，接收index节点，同时接收一个index
        2、index表示是倒数第index个节点
        3、先把链表从头到尾遍历，得到链表的总长度 使用下面定义好了的getLength方法
        4、得到size后，我们从链表的第一个开始遍历（size - index）个，就可以得到
        5、如果找到了，则返回该节点，否则返回null
     */
    public static HeroNode findLastIndexNode(HeroNode head,int index) {
        //判断如果链表为空，返回null
        if (head.next == null) {
            return null;    //没有找到
        }
        //第一次遍历得到链表的长度（节点的个数）
        int size = getLength(head);
        //第二次遍历 size - index 位置，就是我们倒数的第k个节点
        //先校验index
        if (index <= 0 || index > size) {
            return null;
        }
        //定义一个辅助变量，for循环定位到倒数的index
        HeroNode cur = head.next;
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    //获取到单链表的节点的个数（如果是带头节点的链表，需要不统计头节点）
    /*
       head就是链表的头节点
       返回的就是有效的节点个数
     */
    public static int getLength(HeroNode head) {
        if (head.next == null) {    //链表为空
            return 0;
        }

        int length = 0;
        //定义一个辅助节点,这里我们没有统计头节点
        HeroNode cur = head.next;
        while (cur != null) {
            length++;   //长度加1
            cur = cur.next;    //遍历链表
        }
        return length;
    }
}

2. 将单链表反转输出

• 思路:

  • 先定义一个节点 reverseHead = new HeroNode();

  • 从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端.

  • 原来的链表的head.next = reverseHead.next

public class SingleLinkedTest2 {
    public static void main(String[] args) {
        //测试
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "林冲", "豹子头");
        HeroNode hero4 = new HeroNode(4, "吴用", "智多星");

        //创建链表
        SingleLikedList singleLikedList = new SingleLikedList();

        //加入按照编号的顺序
        singleLikedList.addOrder(hero1);
        singleLikedList.addOrder(hero3);
        singleLikedList.addOrder(hero4);
        singleLikedList.addOrder(hero2);
        //显示链表
        singleLikedList.list();

        //单链表的反转
        System.out.println("单链表的反转");
        reverseList(singleLikedList.getHead());
        singleLikedList.list();

    }

    //将单链表反转（面试题2）
    public static void reverseList(HeroNode head) {
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if (head.next == null || head.next.next == null) {
            return;
        }
        //定义一个辅助指针（变量），帮助我们遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next = null;   //指向当前节点（cur）的下一个节点、
        HeroNode reverseHead = new HeroNode(0,"","");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
        while (cur != null) {
            next = cur.next;    //先暂时保存当前节点的下一个节点，我们后面需要用到

            /*
            第一次循环时
                将reverseHead.next赋值给cur.next，此时reverseHead.next = null,所以此时cur.next = null，就使得
                cur指向空
             第二次循环时
                cur后移了一位，cur = cur.next，此时再将reverseHead.next赋值给cur.next，
                就相当于reverseHead.next赋值给cur.next.next，也就是将cur的地址值赋值给cur下一个元素的next，
                就使得cur的下一个元素就指向了cur。
             */
            cur.next = reverseHead.next;

            /*
             第一次循环时
                  再将cur的地址赋值给reverseHead.next，此时reverseHead就指向了cur，cur指向空，为最后一个元素
              第二次循环
                  cur后移了一位，cur = cur.next，此时再将cur的地址值赋值给reverseHead.next，
                  就相当于将cur的下一个节点的地址值赋值给reverseHead.next，也就是说将头节点指向了cur的下一个元素，
                  此时cur任然指向空，为最后一个元素，并且一直为最后一个元素。
              第二轮循环之后就成功将cur的下一个元素插入到头节点和cur之间，继续循环下去，就会使得cur的下下个元素插入
              到头节点和cur的下一个节点之间，循环结束之后，就可以实现链表的逆转。
             */
            reverseHead.next = cur;
            cur = next;     //将cur后移
        }
        //将reverseHead.next赋值给head.next,实现原单链表的反转
        head.next = reverseHead.next;
    }
}

3. 使用栈实现单链表的逆序打印

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

使用第二种方式完成

import java.util.Stack;

public class SingleLinkedTest3 {
    public static void main(String[] args) {
        //测试
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "林冲", "豹子头");
        HeroNode hero4 = new HeroNode(4, "吴用", "智多星");

        //创建链表
        SingleLikedList singleLikedList = new SingleLikedList();

        //加入按照编号的顺序
        singleLikedList.addOrder(hero1);
        singleLikedList.addOrder(hero3);
        singleLikedList.addOrder(hero4);
        singleLikedList.addOrder(hero2);
        //显示链表
        singleLikedList.list();

        //单链表的逆序打印
        System.out.println("单链表的逆序打印");
        reversePrint(singleLikedList.getHead());

    }

    //使用栈实现单链表的逆序打印（面试题3）
    public static void reversePrint(HeroNode head) {
        if (head.next == null) {    //链表为空
            return;
        }
        //创建一个栈，将链表中的节点压入到栈中
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;

        while (cur != null) {
            stack.push(cur);
            cur = cur.next;     //cur后移，遍历链表
        }
        //将栈中的节点进行打印，出栈
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }
}

3.2、双向链表

双向链表是在单链表的每个节点中，在设置一个指向其前驱的节点的指针域，双向链表有两个指针域，一个指向直接后继，一个指向直接前驱。

单向链表的缺点分析:

• 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。

• 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除节点时，总是需要一个辅助节点temp,temp 是待删除节点的前一个节点。

• 
  双向链表的遍历，添加，修改，删除分析
  

  • 
    遍历
    
    方式和单链表一样，可以向前，也可以向后查找。

  • 
    添加
    
    (默认添加到双向链表的最后)

    • 先找到双向链表的最后这个节点

    • temp.next = newHeroNode

    • newHeroNode.pre = temp;

  • 
    修改
    
    思路和原来的单向链表一样。

  • 
    删除
    

    • 因为是双向链表，因此，我们可以实现自我删除某个节点。

    • 直接找到要删除的这个节点，用temp表示

    • temp.pre.next = temp.next

    • temp.next.pre = temp.pre;

  代码实现双向链表的遍历、添加、修改、删除。

public class DoubleLinkedListTest {
    public static void main(String[] args) {
        System.out.println("测试双向链表");
        HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
        HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
        HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
        HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");

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

        //显示双向链表
        doubleLinkedList.list();
//
        //修改双向链表
        HeroNode2 newHero = new HeroNode2(4, "鲁智深", "花和尚");
        doubleLinkedList.update(newHero);
        System.out.println("修改后的双向链表为：");
        doubleLinkedList.list();

        //删除双向链表的一个节点
        doubleLinkedList.del(1);
        System.out.println("删除节点后情况");
        doubleLinkedList.list();

    }
}

//
class DoubleLinkedList {
    //先初始化一个头节点，头节点不要移动，不存放具体的数据
    private HeroNode2 head = new HeroNode2(0,"","");

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

    //删除双向链表中的一个节点
    /*
        分析：
        1、对于双向链表，我们可以直接找到要删除的这个节点
        2、找到后直接删除即可
     */
    public void del(int no) {
        //判断当前链表是否为空
        if (head.next == null) {    //为空
            System.out.println("链表为空，无法删除");
            return;
        }

        HeroNode2 temp = head.next;
        boolean flag = false;   //标志是否找到待删除的节点

        while (true) {
            if (temp == null) {    //已经到链表最后
                break;
            }
            if (temp.no == no) {
                //找到待删除的节点temp
                flag = true;
                break;
            }
            temp = temp.next;   //temp后移，遍历链表
        }
        //判断flag
        if (flag) {     //找到
            //删除
            temp.pre.next = temp.next;
            //如果是最后一个节点，就不需要执行下面这句话，否则会出现空指针
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
        } else {
            System.out.println("没有找到编号为："+no+"的节点");
        }
    }

    //修改双向链表中一个节点的内容
    //修改节点的信息，根据no编号来修改，即no编号不能修改
    /*
        说明：
        1、根据 newHeroNode的no值来修改即可
     */
    public void update(HeroNode2 newHeroNode) {
        //先判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点，根据no值
        HeroNode2 temp = head.next;
        boolean flag = false;   //表示是否找到该节点
        while (true) {
            if (temp == null) {
                break;  //已经遍历完链表
            }
            if (temp.no == newHeroNode.no) {    //表示找到了
                flag = true;
                break;
            }
            temp = temp.next;   //temp后移
        }
        //根据flag判断是否找到要修改的节点
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        } else {    //没有找到
            System.out.println("没有编号为："+newHeroNode.no+"的节点可以进行修改");
        }
    }

    //添加一个节点到链表最后
    public void add(HeroNode2 heroNode) {
        //因为head节点不能移动，因此我们需要一个辅助变量temp
        HeroNode2 temp = head;
        //遍历链表，移动到最后
        while (true) {
            //找到链表最后
            if (temp.next == null) {
                break;
            }
            //如果没有找到最后，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next指向新的节点，再将新节点的pre指向最后的节点
        temp.next = heroNode;
        heroNode.pre = temp;
    }

    public void addOrder(HeroNode2 heroNode) {
        /*
            因为头节点不能移动，因此我们需要一个辅助指针（变量）来帮助我们找到添加的位置
            我们找的temp是位于添加位置的前一个节点，否则插入不了
         */
        HeroNode2 temp = head;
        boolean flag = false;   //添加的编号是否存在，默认为false不存在

        while (true) {
            if (temp.next == null) {    //说明已经在链表的最后
                break;
            }

            if (temp.next.no > heroNode.no) {   //位置找到，就在temp的后面插入
                break;
            } else if (temp.next.no == heroNode.no) {   //说明希望添加的编号已经存在
                flag = true;    //说明编号已经存在
                break;
            }
            temp = temp.next;   //temp后移遍历链表
        }

        //判断flag的值
        if (flag) { //不能添加说明编号存在
            System.out.println("准备插入的英雄编号："+heroNode.no+"已经存在,不能添加");
        } else {
            /*
                此时temp指向插入位置的前一个元素，temp.next就是处于待插入位置的节点，此时将temp.next赋值给heroNode.next，
                就使得待插入的节点heroNode指向了处于待插入位置的节点，再将heroNode赋值给temp.next，就使得temp指向了待插入的节点，
                此时就完成了单向连接。第三步，将heroNode赋值给temp.next.pre（temp.next就是处于待插入位置的节点），就使得待插入
                位置的节点指向了待插入的节点。最后，将temp赋值给heroNode.pre，就使得heroNode指向了temp。
             */
            heroNode.next = temp.next;
            temp.next = heroNode;
            temp.next.pre = heroNode;
            heroNode.pre = temp;


        }
    }

    //遍历双向链表
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        //因为头节点不能移动，因此我们需要一个辅助变量来遍历
        HeroNode2 temp = head.next;
        while (true) {
            //判断链表是否到最后
            if (temp == null) {
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将temp后移
            temp = temp.next;
        }
    }

}

//定义一个HeroNode2，每个HeroNode对象就是一个节点
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;
    }

    //为了显示方便，我们重写toString方法
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

3.3、单向环形链表

使用场景：Josephu （约瑟夫）问题

3.3.1、Josephu问题

• 
  Josephu 问题为
  
  ：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到

  m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此

  产生一个出队编号的序列。

• 
  设计思路
  
  ：用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开

  始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。

  • 先创建一个辅助指针helper，先指向环形链表最后的那个节点。

  • 报数之前，先让first和helper移动k – 1次，使得first指向开始报数的节点，helper指向要报数节点的前一个节点。

  • 当开始报数时，让first和helper移动m -1次

  • 此时first就指向了要出圈的节点

  • first = first.next;
    helper = helper.next;
    

public class JosephuTest {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();

        circleSingleLinkedList.add(5);
        circleSingleLinkedList.list();

        circleSingleLinkedList.countNode(1,2,5);
    }
}

//创建一个单向的环形链表
class CircleSingleLinkedList {
    //创建一个first节点，当前没有编号
    private Boy first = null;
    //添加节点，构建成一个环形的链表
    public void add(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，
                    再把first赋值给first.next，使得first指向first，再让之前创建的辅助节点curBoy指向第一个节点。
                 */
                first = boy;
                first.next = first; //形成一个环
                curBoy = first; //让curBoy指向第一个节点
            } else {
                /*
                    先将boy赋值给curBoy.next，使得之前链表的最后一个节点指向新创建的节点，再将first赋值给boy.next，
                    使得新创建的节点指向第一个节点，形成环形链表，再把boy赋值给curBoy，使得curBoy指向当前链表的最后一个节点。
                 */
                curBoy.next = boy;
                boy.next = first;
                curBoy = boy;
             }
        }
    }

    //遍历环形链表
    public void list() {
        //判断链表是否为为空
        if (first == null) {
            System.out.println("链表为空");
            return;
        }
        //因为first不能移动，需要一个辅助节点来遍历链表
        Boy curBoy = first;
        while (true) {
            System.out.println("小孩的编号为：" + curBoy);
            if (curBoy.next == first){  //表示已经遍历完毕
                break;
            }
            curBoy = curBoy.next;
        }
    }


    /**
     * @param startNo 表示从第几个节点开始计数
     * @param countNum 表示计数几下
     * @param nums 表示最初有多少节点在圈中
     */
    public void countNode(int startNo, int countNum, int nums) {
        //先对数据进行检验
        if (first == null || startNo < 1 || startNo > nums){
            System.out.println("输入的数据有误");
            return;
        }
        //创建一个辅助指针，帮助完成节点出圈
        Boy helper = first;
        //需要创建一个辅助指针helper，先指向该环形链表的最后
        while (true) {
            if (helper.next == first) {     //将helper移动到最后的这个节点
                break;
            }
            helper = helper.next;
        }
        /*
            节点出圈前，先让first和helper移动startNo - 1次（因为是从自身开始数，所以数的个数就要减去表示自身的一个），
            使得first指向编号为startNo的节点（也就是开始计数的节点），helper指向编号为startNo的前一个节点。
         */
        for (int i = 0; i < startNo - 1; i++) {
            first = first.next;
            helper = helper.next;
        }
        //当计数时，让first 和 helper指针同时移动countNum - 1，然后出链表
        //循环操作，直到圈中只有一个节点
        while (true) {
            if (helper == first) {  //此时表示圈中只有一个节点
                break;
            }
            /*
                让first 和 helper指针同时移动countNum - 1（因为是从自身开始数，所以数的个数就要减去表示自身的一个），
                使得first指向要出圈的节点，helper指向要出圈节点的前一个节点。
             */
            for (int i = 0; i < countNum - 1; i++) {
                first = first.next;
                helper = helper.next;
            }
            /*
                此时first指向的节点，就是要出圈的节点，先将这个节点输出
             */
            System.out.println("节点" + first.getNo() + "出圈");
            /*
                在将first指针后移一位，到出圈节点的下一个节点，再将first赋值给helper.next，也就是让helper指向
                出圈节点的下一个节点，然后再继续移动。
             */
            first = first.next;
            helper.next = first;
        }
        //循环完成后，first和helper都指向了最后的这个节点，最后再输出这个节点
        System.out.println("最后的节点为：" + first.getNo());
    }
}

//创建一个Boy类，表示一个节点
class Boy {
    private int no;     //编号
    Boy next;   //指向下一个节点，默认为null

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

    public int getNo() {
        return no;
    }

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

    @Override
    public String toString() {
        return "Boy{" +
                "no=" + no +
                '}';
    }
}

4、栈

• 栈的英文为(stack) 。

• 栈是一个
  
  后进先出
  
  (LIFO-Last In First Out)
  
  的有序列表
  
  。

• 
  栈
  
  是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为
  
  栈顶
  
  (Top)，另一端为固定的一端，称为
  
  栈底
  
  (Bottom)。

• 根据栈的定义可知，
  
  最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除
  
  。

• 栈是一个线性表，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表。定义中说是在线性表的表尾进行插入和删除，这里的表尾是指栈顶。

• 栈的插入操作叫做，压栈，也叫做入栈。栈的删除操作叫做出栈，也叫做弹出栈。
  
  

4.1、数组模拟栈

• 定义一个 top 来表示栈顶，初始化 为 -1;

• 入栈的操作，当有数据加入到栈时：

  top++;

  stack[top] = data;

• 出栈的操作：

  int value = stack[top];

  top–;

  return value;

import java.util.Scanner;

public class ArrayStackTest {
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(4);
        String key = "";
        boolean flag = true;    //控制是否退出菜单
        Scanner scanner = new Scanner(System.in);

        while (flag) {
            System.out.println("show：表示显示栈");
            System.out.println("exit：退出程序");
            System.out.println("push：表示添加数据到栈");
            System.out.println("pop：表示从栈中取出数据");

            System.out.println("请输入你用进行的操作：");
            key = scanner.next();
            switch (key) {
                case "show" :
                    stack.list();
                    break;
                case "exit" :
                    scanner.close();
                    flag = false;
                    break;
                case "push" :
                    System.out.println("请输入要添加的数据：");
                    int i = scanner.nextInt();
                    stack.push(i);
                    break;
                case "pop" :
                    try {
                        int res = stack.pop();
                        System.out.println("出栈的数据：" + res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    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[maxSize];   //初始化数组
    }

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

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

    //添加数据到栈中
    public void push(int m) {
        //判断栈是否满
        if (isFull()) {
            System.out.println("栈已经满，无法再添加数据！");
            return;
        }
        top++;
        stack[top] = m;
    }

    //从栈中（栈顶）取出数据
    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]);
        }
    }
}

4.2、链表模拟栈

public class LinkedStackTest {
    public static void main(String[] args) {
        LinkedStack linkedStack = new LinkedStack();

        linkedStack.push(new Node(1));
        linkedStack.push(new Node(2));
        linkedStack.push(new Node(3));
        linkedStack.push(new Node(4));
        linkedStack.push(new Node(5));
        linkedStack.list();
        System.out.println("=============================");

        linkedStack.pop();
        linkedStack.list();
        linkedStack.pop();
        linkedStack.list();

        System.out.println("=================================");
        linkedStack.pop();
        linkedStack.pop();
        linkedStack.pop();
        linkedStack.pop();
        linkedStack.list();
    }
}

//使用链表模拟栈
class LinkedStack {
    private Node top = new Node(-1);

    //添加数据到栈中，使用头插法，插入数据，以达到链表的先进后出的规则
    public void push(Node node) {
        Node first = top;   //first表示头节点
        if (top.next == null) { //先插入第一个节点
            top.next = node;
            return;
        }
        /*
            使用头插法完成节点的插入
            此时first指向第一个元素之前，方便进行插入，先将第一个元素也就是first.next赋值给node.next，使得
            新加入的节点node指向之前的那个节点，再把先插入的节点赋值给first.next，使得头节点first指向node。
         */
        node.next = first.next;
        first.next = node;
    }

    //从栈中取出数据
    public void pop() {
        //先判断栈是否为空
        if (top.next == null) {
            System.out.println("栈为空，无法取出数据！");
            return;
        }
        System.out.println("出栈的节点为：" + top.next.getNo());
        top = top.next;
    }

    //遍历栈的元素
    public void list() {
        if(top.next == null){
            System.out.println("栈空!");
            return;
        }
        Node temp = top;
        while(temp.next != null){
            System.out.println("节点为："+temp.next.getNo());
            temp = temp.next;
        }
    }
}

//创建一个节点
class Node {
    private int no; //表示节点的编号
    Node next;  //指向下一个节点的辅助指针

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

    public int getNo() {
        return no;
    }

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

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                '}';
    }
}

4.3、栈实现计算器（中缀表达式）

• 先创建两个栈，一个数栈，一个符号栈；

• 通过一个index值（索引），来遍历我们的表达式；

• 如果我们发现是一个数字, 就直接入数栈；

• 如果发现扫描到是一个符号, 就分如下情况：

  • 如果发现当前的符号栈为空，就直接入栈；
  • 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符， 就需要从数栈中pop出两个数,在从符号栈中pop出一个符号进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈。

• 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行；

• 最后在数栈只有一个数字，就是表达式的结果。

public class Calculator {
    public static void main(String[] args) {
        //创建一个需要计算的表达式
        String expression = "600+6*2+20/2-100";
        //创建两个栈，一个存放数字，一个存放符号
        ArrayStack2 numStrack = new ArrayStack2(100);
        ArrayStack2 operStrack = new ArrayStack2(100);
        //定义一些变量
        int index = 0;  //索引，用于遍历表达式
        int num1;
        int num2;
        int res;
        int oper;
        char ch = ' ';  //用于存放每次遍历出来的值
        String keepNum = "";    //用于拼接多位数
        //遍历表达式
        while (true) {
            ch = expression.charAt(index);
            //判断ch是什么
            if (operStrack.isOper(ch)) {    //如果是运算符
                //判断当前符号栈是否为空
                if (operStrack.isEmpty()) {
                    //如果为空直接入栈
                    operStrack.push(ch);
                } else {
                    /*
                        如果符号栈有操作符，就进行比较，如果当前的符号栈的优先级小于或者等于栈中的操作符，
                        就需要从数栈中pop出两个数，再从符号栈中pop出一个符号，进行运算，将得到的结果入数栈，然后将当前的操作符入符号栈
                    */
                    if (operStrack.priority(ch) <= operStrack.priority(operStrack.peek())) {
                        num1 = numStrack.pop();
                        num2 = numStrack.pop();
                        oper = operStrack.pop();
                        res = numStrack.cal(num1,num2,oper);
                        //把运算的结果入数栈
                        numStrack.push(res);
                        //把运算符入符号栈
                        operStrack.push(ch);
                    } else {
                        //如果当前的运算符大于栈中的运算符，则直接入栈
                        operStrack.push(ch);
                    }
                }
            } else {    //如果是数就直接入栈
//                numStrack.push(ch - '0');   //转换为十进制的数  只能计算个位数
                /*
                    1.当处理多位数时，不能发现是一个数就直接入栈，因为他可能是多位数
                    2.在处理数时，需要多向后遍历几位数，直到下一个是运算符为止
                    3.定义一个字符串变量进行拼接
                 */
                keepNum += ch;  //拼接数字

                //如果ch已经是expression的最后一位，就直接入栈
                if (index == expression.length() - 1) {
                    numStrack.push(Integer.parseInt(keepNum));
                } else {
                    //判断下一个字符是不是数字，如果是运算符就直接入栈，如果是数字就继续遍历
                    if (operStrack.isOper(expression.charAt(index + 1))) {
                        //如果最后一位是运算符就直接入栈
                        numStrack.push(Integer.parseInt(keepNum));
                        //拼接完成后，将keepNum清空，否则就会继续再前一个数字后面拼接
                        keepNum = "";
                    }
                }
            }
            //让index+1，并判断是否遍历到最后
            index++;
            if (index >= expression.length()) {
                break;
            }
        }

        //当表达式遍历完毕后，就顺序的从符号栈和数栈中pop出相应的符号和数，进行运算
        while (true) {
            //如果符号栈为空，则表示已经计算完毕，数栈中只有一个数就是结果
            if (operStrack.isEmpty()) {
                break;
            }
            num1 = numStrack.pop();
            num2 = numStrack.pop();
            oper = operStrack.pop();
            res = numStrack.cal(num1,num2,oper);
            numStrack.push(res);
        }
        //数栈中最后的数就是结果
        int sum = numStrack.pop();
        System.out.println("表达式：" + expression + " = " + sum);
    }
}

//定义一个ArrayStack 表示栈
class ArrayStack2 {
    private int maxSize;    //表示栈的大小
    private int[] stack;    //用数组模拟栈，数据就存在该数组中
    private int top = -1;   // top表示栈顶，初始化为-1，表示栈中没有数据

    //初始化数据

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

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

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

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

    //添加数据到栈中
    public void push(int m) {
        //判断栈是否满
        if (isFull()) {
            System.out.println("栈已经满，无法再添加数据！");
            return;
        }
        top++;
        stack[top] = m;
    }

    //从栈中（栈顶）取出数据
    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 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 val){
        int res = 0;    //用于存放计算的结果
        switch (val) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;  //后出来的数减去前出来的数
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;  //**
                break;
        }
        return res;
    }

}

4.4、逆波兰计算器

完成一个逆波兰计算器：

• 输入一个逆波兰表达式(后缀表达式)，使用栈(Stack)，计算其结果

• 简化计算器，只支持对整数的运算。

• 将中缀表达式转换为后缀表达式

  1. 初始化两个栈：运算符栈 s1 和储存中间结果的栈 s2；

  2. 从左至右扫描中缀表达式；

  3. 遇到操作数时，将其压 s2；

  4. 遇到运算符时，比较其与 s1 栈顶运算符的优先级：

     1. 如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；

     2. 否则，若优先级比栈顶运算符的高，也将运算符压入 s1；

     3. 否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再与 s1 中新的栈顶运算符相比较；

  5. 遇到括号时：

     1. 如果是左括号“(”，则直接压入 s1
     2. 如果是右括号“)”，则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到左括号为止，此时将这一对括号丢弃

  6. 重复步骤 2 至 5，直到表达式的最右边

  7. 将 s1 中剩余的运算符依次弹出并压入 s2

  8. 依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

中缀表达式：1 + ( ( 2 + 3 )× 4) – 5 的后缀表达式为 ：1 2 3 + 4 * + 5 –

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

public class PolandNotation {
    public static void main(String[] args) {
        /*
            完成对一个中缀表达式转成后缀表达式的功能
            1、1+((2+3)*4)-5 -> 转成 1 2 3 + 4 * + 5 -
            2、先创建"1+((2+3)*4)-5"中缀表达式对应的List
            即"1+((2+3)*4)-5" -> ArrayList[1,+,(,(,2,+,3,),*,4,),-,5]
         */
        String expression = "1+((2+3)*4)-5";
        List<String> infixExpressionList = toInfixExpression(expression);
        System.out.println("中缀表达式对应的List：" + infixExpressionList);

        /*
            3.将得到的中缀表达式对应的List转成后缀表达式对应的List
              即ArrayList[1,+,(,(,2,+,3,),*,4,),-,5] --> ArrayList[1,2,3,+,4,*,+,5,-]
         */
        List<String> suffixExpressionList = parseSuffixExpression(infixExpressionList);
        System.out.println("后缀表达式对应的List：" + suffixExpressionList);

        System.out.println("expression = " + calculate(suffixExpressionList));

//        //先定义一个逆波兰表达式
//        //(30+4)*5-6 -> 30 4 + 5 * 6 -
//        String suffixExpression = "30 4 + 5 * 6 -";
//
//        /*
//            1.先将"3 4 + 5 * 6" -> 放入到ArrayList中
//            2.将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算
//         */
//        List<String> rpnList = getListString(suffixExpression);
//        System.out.println("rpnList= "+rpnList);
//
//        int res = calculate(rpnList);
//        System.out.println("计算的结果是：" + res);
    }

    /*
        将得到的中缀表达式对应的List转成后缀表达式对应的List
            即ArrayList[1,+,(,(,2,+,3,),*,4,),-,5] --> ArrayList[1,2,3,+,4,*,+,5,-]
     */
    public static List<String> parseSuffixExpression(List<String> list) {
        //定义两个容器
        Stack<String> s1 = new Stack<>();   //符号栈
        /*
            因为s2这个栈在转换过程中没有pop操作，而且后面我们还需要逆序输出
            因此我们可以直接使用ArrayList<String> s2
         */
        ArrayList<String> s2 = new ArrayList<>();   //存储中间结果的ArrayList s2

        //遍历list
        for (String item : list) {
            //如果是一个数就直接加入到s2
            if (item.matches("\\d+")) {
                s2.add(item);
            } else if (item.equals("(")) {
                //如果是左括号“(”，则直接压入 s1
                s1.push(item);
            } else if (item.equals(")")) {
                //如果是右括号“)”，则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到左括号为止，此时将这一对括号丢弃
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                //将 ( 从s1中弹出,消除括号
                s1.pop();
            } else {    //为运算符时
                /*
                    当item的优先级小于等于s1栈顶的运算符时,将 s1 栈顶的运算符弹出并压入到 s2 中，
                    再与 s1 中新的栈顶运算符相比较；
                 */
                while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
                    s2.add(s1.pop());
                }
                //将item入s1栈
                s1.push(item);
            }
        }

        //将 s1 中剩余的运算符依次弹出并加入 s2
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }

        //此时不需要逆序输出
        return s2;
    }

    //将中缀表达式转成对应的List
    public static List<String> toInfixExpression(String s) {
        //定义一个ArrayList用于存放中缀表达式
        ArrayList<String> list = new ArrayList<>();
        int i = 0;  //这是一个指针，用于遍历中缀表达式字符串
        String str; //对多位数进行拼接
        char c; //每遍历到一个字符就存放到c
        do {
            //如果c是一个非数字，就直接加入到list中
            if ((c = s.charAt(i)) < '0' || (c = s.charAt(i)) > '9') {
                list.add("" + c);
                i++;
            } else {    //如果是一个数，则需要考虑多位数
                str = "";   //每次都要重置str
                while (i < s.length() && (c = s.charAt(i)) >= '0' && (c = s.charAt(i)) <= '9') {
                    str += c;   //进行拼接
                    i++;
                }
                list.add(str);
            }
        } while (i < s.length());

        return list;
    }

    //将一个逆波兰表达式的数据和运算符依次放入到ArrayList中
    public static List<String> getListString(String suffixExpression){
        //将suffixExpression分割
        String[] spilt = suffixExpression.split(" ");
        ArrayList<String> list = new ArrayList<>();
        for (String value : spilt) {
            list.add(value);
        }
        return list;
    }

    //完成对逆波兰表达式的计算
    /*
        1．从左至右扫描，将 3 和 4 压入堆栈；
        2．遇到+运算符，因此弹出 4 和 3（4 为栈顶元素，3 为次顶元素），计算出 3+4 的值，得 7，再将 7 入栈；
        3．将 5 入栈；
        4．接下来是×运算符，因此弹出 5 和 7，计算出 7×5=35，将 35 入栈；
        5．将 6 入栈；
        6．最后是-运算符，计算出 35-6 的值，即 29，由此得出最终结果
     */
    public static int calculate(List<String> list) {
        Stack<String> stack = new Stack<>();
        for (String item : list) {
            //使用正则表达式来取出数
            if (item.matches("\\d+")){//匹配的是多位数
                //就入栈
                stack.push(item);
            } else {    //如果是运算符
                //pop出两个数，进行运算，再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;

                if (item.equals("+")){
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有误！");
                }
                //将res转换成字符串再入栈
                stack.push("" + res);
            }
        }
        //最后留在栈中的就是最后的结果
        return Integer.parseInt(stack.pop());
    }
}

//用于返回运算符的优先级
class Operation {
    private static final int ADD = 1;   //加法
    private static final int SUB = 1;   //减法
    private static final int MUL = 1;   //乘法
    private static final int DIV = 1;   //除法

    public static int getValue(String operation) {
        int result = 0;
        switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("不存在该运算符！");
                break;
        }
        return result;
    }
}

5、递归

5.1、八皇后问题

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于

1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即：

任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法(92)

。

思路分析

：

1. 第一个皇后先放第一行第一列。

2. 第二个皇后放在第二行第一列、然后判断是否 OK， 如果不 OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适。

3. 继续第三个皇后，还是第一列、第二列……直到第 8 个皇后也能放在一个不冲突的位置，算是找到了一个正确解。

4. 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解,全部得到。

5. 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4 的步骤。

package com.tian.recursion;

public class Queue {
    //定义一个max表示一共有多少个皇后
    int max = 8;
    //定义一个数组array，保存皇后存放位置的结果
    int[] array = new int[max];
    static int count = 0;

    public static void main(String[] args) {
        Queue queue = new Queue();
        queue.check(0);
        System.out.println("解法一共有：" + count + "种");
    }

    private void check(int n){
        if (n == max){      //n = 8,前8个皇后已经放好了
            print();
            return;
        }

        //依次放入皇后，并进行判断
        for (int i = 0; i < max; i++) {
            //先将把当前的皇后放置到改行的第一列
            array[n] = i;
            //判断当前放置的位置是否冲突
            if (judge(n)){      //不冲突
                //接着开始放置第n + 1个皇后，开始递归
                check(n + 1);
            }
            //如果冲突，就继续执行，即将当前皇后移动一列，在继续进行判断
        }

    }

    /*
        n表示第n个皇后
        查看当我们放置第n个皇后时，就应该去检测该皇后是否满足所规定的条件
     */
    private boolean judge(int n){
        for (int i = 0; i < n; i++) {
            /*
                1.array[i] == array[n]用于判断该皇后是否和前面的皇后在同一列。
                2.Math.abs(n - i) == Math.abs(array[n] - array[i])用于判断该皇后是否和第i个皇后
                在同一斜线。
             */
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])){
                return false;
            }
        }
        return true;
    }

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

}