4.3 、单链表面试题(新浪、百度、腾讯)

单链表的常见面试题有如下:
- 1) 求单链表中有效节点的个数
  - 思路：直接遍历即可(即直接在链表内加入方法即可)
代码实现入下：

    //添加方法：获取到单链表的个数（如果是带头节点的链表要求不统计头节点）
    /**
     *
     * @param head 链表的头节点
     * @return 返回的就是有效节点的个数
     */
    public static int getLength(SingleLinkedListHeroNode head){
   
   
        //首先判断链表是否为空
        if (head.next == null){
   
   
            return 0;    //若为空说明这是一个带头节点的空链表，直接返回0即可
        }
        int length = 0;
        //定义一个辅助变量,标识没有统计头节点
        SingleLinkedListHeroNode cur = head.next;
        while (cur!=null){
   
   
            length++;
            cur = cur.next;  //结束遍历
        }
        return length;
    }

在头节点种加入Getter方法并在主方法体中测试

public SingleLinkedListHeroNode getHead() {
        return head;
    }
        //测试以下求单链表种有效节点的个数
        System.out.println("有效的节点个数= " + getLength(singleLinkedList.getHead()));

输出结果如下：

2) 查找单链表中的倒数第 k 个结点【新浪面试题】
- 思路分析入下：编写一个方法，接收head节点，同时接收一个index
  - index表示倒数第index个节点
  - 由于此题数据结构是单链表，不能倒序遍历，因此先把链表从头到尾遍历，得到链表的总长度 getLength
  - 得到size （节点长度）后，我们从链表的第一个节点开始遍历（size-index）个，就可以得到
  - 如果找到该节点，则返回该节点，找不到节点返回null即可
代码演示如下

public static SingleLinkedListHeroNode findLastIndexNode(SingleLinkedListHeroNode head,int index){
        //首先判断链表是否为空，若链表为空返回null
        if (head.next == null){
            return null;   //没有找到该节点
        }
        //第一次遍历得到链表的长度(节点的个数)
        int size = getLength(head);
        /*第二次遍历 size-index 位置，即倒数的第k个节点，在此之前先给index做一个校验,即保证遍历的节点位置不能为负数
        也不能超过链表中总节点的数量,超过了就返回null*/
        if (index <=0 || index > size){
            return null;
        }
        //接下来开始遍历，定义一个辅助变量指向第一个有效的节点cut，找到之后使用for循环定位到倒数的index
        SingleLinkedListHeroNode cur = head.next;
        for(int i=0; i<size -index; i++){  //循环的主要是为了往下移动
            cur = cur.next;
        }
        return cur; //循环过后就找到了数据，直接返回即可
    }

接下来进行测试：k表示链表内任意一个有效节点，测试代码中获取的是倒数第一个

//测试以下是否得到了倒数第k个节点
        SingleLinkedListHeroNode result = findLastIndexNode(singleLinkedList.getHead(),1);
        System.out.println("result= " +result);
    }

输出结果如下：

根据结果得出结论代码无误

3) 单链表的反转，即把节点的顺序进行反转
- 思路分析图解如下

具体思路分析如下
- 1、先定义一个节点reserseHead = new HeroNode()；
- 2、从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reserseHead 的最前端
- 3、原链表的head.next = reverseHead.next
代码实现

    //将单链表进行反转
    public static void reversetList(SingleLinkedListHeroNode head){
        //如果当前链表为空，或者只有一个节点，就无需反转，直接返回即可
        if (head.next == null || head.next.next == null){
            return;
        }
        //定义一个辅助的变量帮助我们遍历原来的链表
        SingleLinkedListHeroNode cur = head.next;
        //定义当前指向当前节点(cur)的下一个节点
        SingleLinkedListHeroNode next = null;
        //再定义一个reverseHead节点，作用就是表示单链表头next
        SingleLinkedListHeroNode reverseHead = new SingleLinkedListHeroNode(0,"","");
        //先遍历原来的链表，并从头遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
        while (cur !=null){ //cur不能为空，若为空说明已经遍历结束了
            next = cur.next;  //先暂时保存当前节点的下一个节点，后面需要使用
            cur.next = reverseHead.next; //将cur的下一个节点指向新的链表的最前端
            reverseHead.next = cur;  //将cut连接到新的链表上
            cur = next;  //让cur后移
        }
        //将head.next指向reverseHead.next，实现单链表的反转
        head.next = reverseHead.next;
    }

接下来进行测试

         //测试一下单链表的反转功能
        System.out.println("原链表的情况");
        singleLinkedList.list();

        //反转
        System.out.println("反转单链表之后");
        reversetList(singleLinkedList.getHead());
        singleLinkedList.list();
    }

结果如下：

4) 从尾到头打印单链表【百度，要求方式 1：反向遍历。方式 2：Stack 栈】
- 思路分析
  - 题目要求就是逆向打印单链表
  - 方式一：先将单链表进行反转操作，然后再遍历即可（这样做的问题是会破坏原来的单链表的结果，不建议）
  - 方式二：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点就实现了逆序打印的效果
由于方式一会破坏链表的结构，所以这题直接使用方式二：代码演示如下：

    //使用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
    public static void reversePrint(SingleLinkedListHeroNode head){
        //首先判断链表是否为空
        if (head.next == null) {
            return;  //链表为空，无法打印
        }
        //若不是空链表，创建一个栈,将各个节点压入栈中
        Stack<SingleLinkedListHeroNode> stack = new Stack();
        //首先将此节点保存，用于稍后遍历
        SingleLinkedListHeroNode cur = head.next;
        //将链表的所有节点压入栈中
        while (cur != null){
            stack.push(cur);
            cur = cur.next;  //让cut后移，这样就可以压入下一个节点
        }
        //将栈中的节点进行遍历即可
        while (stack.size() > 0){
            System.out.println(stack.pop());  //由于栈的特性是先进后出，直接调用stack的pop方法就可以实现倒序输出
        }
    }

进行测试

        //测试一下单链表的反转功能
        System.out.println("原链表的情况");
        singleLinkedList.list();

        System.out.println("测试逆序打印的情况,没有改变链表的本身结构");
        reversePrint(singleLinkedList.getHead());

测试结果如下

4.4 、双向链表应用实例

4.4.1、双向链表的操作分析和实现

使用带 head 头的双向链表实现 –水浒英雄排行榜
管理单向链表的缺点分析:
- 1) 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
- 2) 单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到 temp,temp 是待删除节点的前一个节点(认真体会).
- 3) 分析了双向链表如何完成遍历，添加，修改和删除的思路

对上图的说明:

分析双向链表的遍历，添加，修改，删除的操作思路===》代码实现
- 1) 遍历方和单链表一样，只是可以向前，也可以向后查找
- 2) 添加 (默认添加到双向链表的最后)
  - (1) 先找到双向链表的最后这个节点
  - (2) temp.next = newHeroNode
  - (3) newHeroNode.pre = temp;
- 3) 修改思路和原来的单向链表一样.
- 4) 删除
  - (1) 因为是双向链表，因此，我们可以实现自我删除某个节点
  - (2) 直接找到要删除的这个节点，比如 temp
  - (3) temp.pre.next = temp.next
  - (4) temp.next.pre = temp.pre;
双向链表增删改查功能的代码实现：首先定义增删改查的四个方法：

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

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

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

    //添加一个节点到双向链表的最后
    public void add(DoubleLinkedListHeroNode heroNode){
        //因为head（即头节点）不能动，因此我们需要一个辅助变量temp
        DoubleLinkedListHeroNode temp = head;
        //遍历链表找到最后节点
        while (true){
            //当变量temp找到最后一个节点为空时，就代表找到了最后节点的位置
            if (temp.next == null){
                break;
            }
            //如果没有找到最后，就让temp向后移动即可
            temp = temp.next;
        }
        //当退出了这个循环后说明了temp已经指向了链表的最后
        //形成一个双向链表
        temp.next = heroNode;
        heroNode.pre = temp;
    }

    //修改一个节点的内容
    /*修改节点的信息，根据编号来修改，即编号不能进行修改
    说明：根据newHeroNode的no来修改即可
    可以双向列表的内容修改和前面的单向链表一模一样，唯一的区别就是节点的类型不同
    */
    public void update(DoubleLinkedListHeroNode newHeroNode){
        //首先判断链表是否为空
        if(head.next == null ){
            System.out.println("链表为空，无法修改");
        }
        //找到需要修改的节点,根据no编号来找，定义辅助节点方便查询
        DoubleLinkedListHeroNode temp = head.next;
        boolean flag = false; //表示是否找到该节点
        while (true){
            if (temp == null){
                break;  //若temp为空表示链表已经遍历结束了
            }
            if (temp.no == newHeroNode.no){
                //temp找到当前需要修改的节点了
                flag = true;
                break;  //找到就结束循环，否则会一直往后
            }
            temp = temp.next;
        }
        //根据flag判断是否找到要修改的节点
        if(flag==true){
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        }else { //没有找到此节点
            System.out.println("没有找到编号为" + newHeroNode.no + "的节点");
        }
    }

    /*从双线链表中删除一个节点,说明：
    1、对于双向链表，我们可以直接找到要删除的这个节点
    2、找到后自我删除即可*/
    public void delete(int no){
        //判断当前链表是否为空
        if(head.next==null){ //空链表
            System.out.println("链表为空，无法删除");
        }
        //辅助遍历
        DoubleLinkedListHeroNode 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;
            //如果是最后一个节点，就不需要执行 temp.next.pre = temp.pre;,否则会出现空指针异常
            if (temp.next!=null){
                temp.next.pre = temp.pre;
            }
        }else {
            System.out.println("要删除的节点" + no + "不存在");
        }
    }
}

接下来是对双向链表的增删改查进行测试

public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        //测试双向链表的增删改查功能是否正常
        System.out.println("双向链表的测试");
        //先创建节点
        DoubleLinkedListHeroNode heroNode1 = new DoubleLinkedListHeroNode(1,"宋江","及时雨");
        DoubleLinkedListHeroNode heroNode2 = new DoubleLinkedListHeroNode(2,"卢俊义","玉麒麟");
        DoubleLinkedListHeroNode heroNode3 = new DoubleLinkedListHeroNode(3,"吴用","智多星");
        DoubleLinkedListHeroNode heroNode4 = new DoubleLinkedListHeroNode(4,"林冲","豹子头");
        DoubleLinkedListHeroNode heroNode5 = new DoubleLinkedListHeroNode(5,"武松","武都头");
        //再创建一个双向链表对象
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(heroNode5);
        doubleLinkedList.add(heroNode3);
        doubleLinkedList.add(heroNode2);
        doubleLinkedList.add(heroNode4);
        doubleLinkedList.add(heroNode1);
        //输出查看结果是否正确
        doubleLinkedList.list();

        //修改测试
        DoubleLinkedListHeroNode newHeroNode = new DoubleLinkedListHeroNode(4,"公孙胜","入云龙");
        doubleLinkedList.update(newHeroNode);
        System.out.println("修改后的链表情况");
        doubleLinkedList.list();

        //删除
        doubleLinkedList.delete(5);
        System.out.println("删除后的链表情况");
        doubleLinkedList.list();
    }
}

输出结果如图所示

通过测试结果我们发现链表的节点添加编号是根据添加，即非顺序排序，所以我们参考单链表的顺序添加第二种方式进行优化

 //新增第二种添加英雄的方式，根据排名将英雄插入到指定位置，若有此排名，则添加失败并返回错误信息
    public void addByOrder(DoubleLinkedListHeroNode heroNode){
        //因为是双链表，因此temp可以在插入的位置 （区别于单链表）
        DoubleLinkedListHeroNode temp = head;
        //标识添加的变量是否存在，默认为false
        boolean flag = 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.next;  //若是以上三个条件都不满足，就让temp后移，遍历当前链表
        }
        //判断flag的值
        if (flag){//若flag的值为true，说明不能添加，编号已经存在
            System.out.println("准备的插入的英雄编号" + heroNode.no + "已经存在了,无法重复添加");
        }else {
            //插入到链表种，即temp的后一位插入到链表，temp的后面,这里的顺序很有讲究，看一下
            heroNode.pre = temp;
            heroNode.next = temp.next;
            temp.next = heroNode;
            temp.next.pre = heroNode;
        }
    }

测试：

         doubleLinkedList.addByOrder(heroNode5);
        doubleLinkedList.addByOrder(heroNode3);
        doubleLinkedList.addByOrder(heroNode2);
        doubleLinkedList.addByOrder(heroNode4);
        doubleLinkedList.addByOrder(heroNode1);
        //测试结果
        doubleLinkedList.list();

结果如下：

总结：双链表排序大致与单链表一致，重点是代码的这一部分

            node.pre = temp;
            node.next = temp.next;
            temp.next = node;
            temp.next.pre = node;

当这部分的顺序发生改变时，代码会报错或者发生运行不完的情形
- 也就是说，我们需要按照下面这种顺序进行赋值

在这里插入图片描述

这是因为：
- 我们所做的1、2步，是把要添加的node节点2变完整，是它既有next指针，又有pre指针。这样再将其他位置的指针指向node2，也会是一个完整的。而不能先指向node2，再将node2进行改变。
- 因此上图的顺序可以进行小调整，那就是将1、2顺序互换，但是，3、4位置不能互换

在这里插入图片描述

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

Josephu(约瑟夫、约瑟夫环) 问题

Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从1 开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

提示：用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由k结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1 开始计数，直到最后一个结点从链表中删除算法结束。

4.6、单向环形链表介绍

4.7、 Josephu (约瑟夫)问题

约瑟夫问题的示意图

Josephu 问题
- Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从1 开始报数，数到m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
提示
- 用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由k 结点起从1开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1 开始计数，直到最后一个结点从链表中删除算法结束
约瑟夫问题-创建环形链表的思路图解

环形链表的创建及其解决约瑟夫问题的代码实现
- 首先创建一个实体类Boy，表示节点，创建对应属性、构造器和Get和Set方法

public class Boy {
    private int no; //编号
    private Boy next;  //指向下一个节点，默认为null

    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;
    }
}

接下来创建一个环形的单向链表，以及遍历环形链表的方法

public class CircleSingleLinkedList{

    //创建一个节点
    BoyNode first = null;
    public void setFirst(BoyNode first) {
        this.first = first;
    }

    //添加小孩节点
    public void addNode(int nums){
        //nums做一个数据校验
        if(nums < 1){
            System.out.println("nums的值不正确！");
            return;
        }
        BoyNode curBoy = null;  //辅助指针，来帮助构成环形链表
        //使用for循环来创建我们的环形链表
        for(int i = 1; i <= nums; i++){
            BoyNode boy = new BoyNode(i);
            //如果是第一个小孩节点
            if(i == 1){
                first = boy;
                first.setNext(first);  //构成一个环
                curBoy = first;  //让curBoy指向第一个小孩
            }else{
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }

    //遍历当前环形链表
    public void showBoy(){
        if(first == null){
            System.out.println("链表为空！");
            return;
        }
        //因为first不能动，因此我们需要一个辅助指针完成遍历
        BoyNode curBoy = first;
        while (true){
            System.out.println("小孩的编号"+curBoy.getNo());
            if(curBoy.getNext() == first ){  //说明已经遍历完毕
                break;
            }
            curBoy = curBoy.getNext();  //让curBoy后移
        }
    }

接下来进行测试，查看功能是否正常，如下图所示结果正常

public class Josepfu {
    public static void main(String[] args) {
        //测试构建环形链表和遍历是否正常显示
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5); //加入五个节点
        circleSingleLinkedList.showBoy();
    }
}

4.8、环形链表出圈问题的代码实现

约瑟夫问题-小孩出圈的思路分析图

代码实现如下：

/**
     * 根据用户的输入，计算出出圈的顺序
     * @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;
        }
        //创建一个辅助指针，帮助完成小孩出圈
        BoyNode temp = first;
        //遍历让temp指向最后一个节点
        while(true){
            if(temp.getNext() == first){
                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 次
        //这里是一个循环操作，直到最后一个小孩
        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.println("小孩"+first.getNo()+"出圈");
            //这时将first指向的小孩节点出圈
            first = first.getNext();
            temp.setNext(first);
        }
        System.out.println("最后留在圈中的小孩编号为："+first.getNo());
    }

测试

        //测试节点出圈是否正确
        circleSingleLinkedList.countBoy(1,2,5);  //2-->4-->1-->5-->3

测试结果如下：

第五章、栈

5.1、栈的一个实际需求

请输入一个表达式

计算式:[722-5+1-5+3-3] 点击计算【如下图】

请问: 计算机底层是如何运算得到结果的？注意不是简单的把算式列出运算,因为我们看这个算式7 2 2 - 5 + 1 - 5 + 3 + 3

但是计算机怎么理解这个算式的(对计算机而言，它接收到的就是一个字符串)，我们讨论的是这个问题。--->栈

5.2、栈的介绍

1) 栈的英文为(stack)
2) 栈是一个先入后出(FILO-First In Last Out)的有序列表。
3)栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
4) 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除
5) 图解方式说明出栈(pop)和入栈(push)的概念

5.3、栈的应用场景

1) 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
2) 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
3) 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
4) 二叉树的遍历
5) 图形的深度优先(depth 一 first)搜索法。

5.4、栈的快速入门

1) 用数组模拟栈的使用，由于栈是一种有序列表，当然可以使用数组的结构来储存栈的数据内容，下面我们就用数组模拟栈的出栈，入栈等操作。
2) 实现思路分析,并画出示意图

使用数组模拟实现栈的思路分析
- 1、使用数组来模拟
- 2、定义一个 top 来表示栈顶，初始化为 -1
- 3、入栈的操作，当有数据加入到栈时， top++; stack[top] = data;
- 4、出栈的操作， int value = stack[top]; top--, return value
接下来的代码实现，首先先定义一个类，使用数组模拟
- 分别把栈空、栈满、入栈、出栈和遍历栈的方法

/**
 * description
 * 定义一个类，使用数组模拟栈结构
 * @author
 * @since 2022/10/25 10:01
 */
public 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 value) {
        //先判断栈是否满
        if(isFull()){
            System.out.println("栈满");
        }
        top++;
        stack[top] = value;
    }

    //模拟出栈,将栈顶的数据返回
    public int pop() {
        //先判断栈是否空
        if (isEmpty()){
            //抛出异常
            throw new RuntimeException("栈空,没有数据");
        }
        //先取得栈顶的值
        int value = stack[top];
        top--;
        return value;
    }

    //显示栈的情况（遍历栈）,由于栈是先入后出，所以要从栈底开始遍历
    public void list(){
        if (isEmpty()){
            System.out.println("栈空，没有数据");
        }
        //需要从栈顶开始显示数据
        for (int i = top; i>0; i--){
            System.out.printf("stack[%d]=%d\n",stack[i]);
        }
    }

}

接下来进行测试，测试各项功能是否正常

public class ArrayStackDemo {
    public static void main(String[] args) {
        //测试ArrayStack是否正确，先创建一个ArrayStack的对象
        ArrayStack arrayStack = new ArrayStack(4);
        String key = "";
        boolean loop = true;  //此变量用于是否退出菜单
        Scanner scanner = new Scanner(System.in);  //拿到一个扫描器
        //使用while循环模拟输入菜单
        while (loop){
            System.out.println("show:表示显示栈");
            System.out.println("exit:表示退出程序");
            System.out.println("push:表示添加数据到栈(入栈)");
            System.out.println("pop:表示从栈取出数据(出栈)");
            System.out.println("请输入你的选择");
            key = scanner.next();   //使用key来快速接收扫描器
            switch (key){
                case "show":
                    arrayStack.list();
                    break;
                case "push":
                    System.out.println("请输入一个数");
                    int value = scanner.nextInt();  //使用一个变量用于接收
                    arrayStack.push(value);
                    break;
                case "pop":
                    try { //由于调用pop时可能会出现异常，使用try/catch进行捕获
                        int res = arrayStack.pop();
                        System.out.printf("出栈的数据是%d\n", res);
                    } catch (Exception e){
                        System.out.println(e.getMessage());  //若有异常输出信息即可
                    }
                    break;
                case "exit":
                    scanner.close();   //关闭接收器资源流
                    loop = false;   //让loop = false即可停止循环
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序已退出");
    }
}

经测试功能正常
- 接下来是使用链表实现，即使用链表模拟栈的思路分析：
  - 1、使用链表来模拟
  - 2、定义一个top来表示栈顶，初始化为-1
  - 3、入栈的操作，当有数据加入到栈时，top++；stack[top] = data;
  - 4、出战的操作，int = value = stack[top]; top--, return value
    - 接下来的代码实现，定义一个类使用数组模拟
      - 分别把栈空、栈满、入栈、出战和遍历输出栈的方法(提示：链表有倒序输出的方法)

代码实现入下：先定义出节点类，该类包含三个属性：节点编号、节点数据以及next指针，并重写toString方法。

/**
 * description
 * 定义一个类，使用链表模拟栈结构
 * @author
 * @since 2022/10/25 15:25
 */
public class HeroStack {
    private int id; //节点编号
    private int value;  //节点数据
    private HeroStack next;  //指向下一个节点

    //get and set

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public int getValue() {
        return value;
    }

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

    public HeroStack getNext() {
        return next;
    }

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

    //构造器
    public HeroStack(int id, int value) {
        this.id = id;
        this.value = value;
    }

    @Override
    public String toString() {
        return "LinkedListStack{" +
                "id=" + id +
                ", value=" + value +
                '}';
    }
}

定义一个LinkedListStack栈。在构造方法中传入maxLength属性，对栈的最大容量进行定义。定义入栈、出栈以及显示栈的方法

package com.xujicheng.stack;

/**
 * description
 * 栈的最大容量进行定义。定义入栈、出栈以及显示栈的方法
 * @author
 * @since 2022/10/25 15:39
 */
public class LinkedListStack {
    //首先初始化一个头节点，头节点不要动，不用于存放具体的数据
    private HeroStack head = new HeroStack(-1,0);
    private int top = -1;  //定义栈顶指针
    int maxSize; //定义最大长度

    //在构造方法内传入栈的最大容量
    public LinkedListStack(int maxSize) {
        this.maxSize = maxSize;
    }

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

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

    //模拟入栈的方法
    public void push(int value){
        HeroStack heroStack = new HeroStack(top,value); //新建一个top节点
        //判断栈是否满了
        if (isFull()){
            System.out.println("栈已满，无法添加");
        }
        top++;
        if (head.getNext() == null){ //说明暂时没有节点，可以直接添加
            head.setNext(heroStack);//将新建的节点添加到头节点的后面
        }else {
            //如果链表已有节点，则在头节点和原来的第一个节点中间插入新的节点（倒插）
            heroStack.setNext(head.getNext());
            head.setNext(heroStack);
        }
    }
    //模拟出栈
    public int pop(){
        //先判断栈是否为空
        if (isEmpty()){
            //抛出异常
            throw new RuntimeException("栈空，没有数据");
        }
        //不为空，取出栈顶的值
        int value = head.getNext().getValue();
        head.setNext(head.getNext().getNext());
        top--;
        return value;
    }

    //显示栈
    public void show(){
        //判断栈是否为空
        if (isEmpty()){
            System.out.println("栈空，无法显示数据");
        }
        HeroStack temp = head.getNext();  //不能写成HeroNode temp = head;否则会显示头节点
        //遍历链表
        while (true){
            System.out.println(temp);
            /*
            如果push方法中写成heroNode = head.getNext()，则head的下一个节点仍是null而不是heroNode，
            即把null赋给了temp，这会导致下面的if语句中的temp.getNext()出现空指针异常*/
            if (temp.getNext() == null){
                break;
            }
            //如果没有找到最后就将temp后移
            temp = temp.getNext();
        }
    }
}

定义测试类

package com.xujicheng.stack;

import java.util.Scanner;

/**
 * description
 * 课堂练习，将老师写的程序改成使用链表来模拟栈。
 * 使用倒插法添加节点
 * @author
 * @since 2022/10/25 16:25
 */
public class LinkedListStackDemo {
    public static void main(String[] args) {
        //测试一下LinkedListStack是否正确
        //先创建一个LinkedListStack对象表示栈
        LinkedListStack stack = new LinkedListStack(3);
        String key = "";
        boolean loop = true;//控制是否退出菜单
        Scanner scanner = new Scanner(System.in);

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

        while (loop) {
            System.out.print("\n请输入你的选择:");
            key = scanner.next();
            switch (key) {
                case "show":
                    stack.show();
                    break;
                case "push":
                    System.out.print("请输入一个数:");
                    int value = scanner.nextInt();
                    stack.push(value);
                    break;
                case "pop":
                    try {
                        int res = stack.pop();
                        System.out.println("出栈的数据是：" + res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }
}

数据结构和算法的学习笔记（第四部分）

4.3 、单链表面试题(新浪、百度、腾讯)

4.4 、双向链表应用实例

4.4.1、双向链表的操作分析和实现

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

4.6、单向环形链表介绍

4.7、 Josephu (约瑟夫)问题

4.8、环形链表出圈问题的代码实现

第五章、栈

5.1、栈的一个实际需求

5.2、栈的介绍

5.3、栈的应用场景

5.4、栈的快速入门

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构和算法的学习笔记（第四部分）

4.3 、单链表面试题(新浪、百度、腾讯)

4.4 、双向链表应用实例

4.4.1、双向链表的操作分析和实现

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

4.6、 单向环形链表介绍

4.7、 Josephu (约瑟夫)问题

4.8、环形链表出圈问题的代码实现

第五章、栈

5.1、栈的一个实际需求

5.2、栈的介绍

5.3、栈的应用场景

5.4、栈的快速入门

热门文章

最新文章

相关课程

相关电子书

相关实验场景

4.6、单向环形链表介绍