链表模拟栈

背景

• 数据结构——链表模拟栈

• 博主以b站尚硅谷Java数据结构与算法课进行学习

思路

• 定义一个HeroNode类，每一个HeroNode对象就是一个节点

  • 代码实现

    class HeroNode {
        public int no;
        public int value;
        public HeroNode next;//指向下个节点
    
        public HeroNode(int no, int value) {
            this.no = no;
            this.value = value;
        }
    
        //为了显示方便，重写toString方法
    
        @Override
        public String toString() {
            return "HeroNode{" +
                    "no=" + no +
                    ", value=" + value +
                    '}';
        }
    }

• 链表模拟栈Linkdist_stack类

  • 初始化一个头节点head，不存放数据

    • 代码实现

      private HeroNode head = new HeroNode(-1,0);

  • top为栈顶指针，初始化为**-1**

    • 代码实现

      private int top =-1;//栈顶指针

  • maxLength为栈的最大容量

    • 代码实现

      int maxLength;//定义最大长度
      //设置栈最大容量
      public Linkdist_stack(int maxLength) {
          this.maxLength = maxLength;
      }

  • 判断栈是否为空isEmpty

    • 代码实现

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

  • 判断栈是否满isFull

    • 代码实现

      public boolean isFull(){
          return top>=maxLength-1;
      }

  • 使用倒插法入栈push

    • 代码实现

      public void push(int value){//为新节点传入新值
      
           HeroNode heroNode = new HeroNode(top,value);
           if (isFull()){
               System.out.println("栈满");
               return;
           }
           top++;
           if(head.next==null){//说明没有新节点，可以直接添加
               head.next = heroNode;
           }else{
               heroNode.next = head.next;
               head.next = heroNode;
           }
      }

  • 出栈pop

    • 代码实现

      public int pop() {
          if (isEmpty()) {
              throw new RuntimeException("栈空，没有数据");
          }
         int value = head.next.value;
          head.next = head.next.next;
          top--;
          return value;
      }

  • 显示show

    • 代码实现

      public void show(){
          if (isEmpty()){
              System.out.println("栈空没有数据");
              return;
          }
          HeroNode temp = head.next;
          while(true){
              System.out.println(temp);
              if (temp.next==null){
                  break;
              }
              temp=temp.next;
          }
      }

• 测试类 linkdist_stackDemo

  • 代码实现

    public class linkdist_stackDemo{
        public static void main(String[] args) {
    //测试一下LinkedListStack是否正确
            //先创建一个LinkedListStack对象表示栈
            Linkdist_stack stack = new Linkdist_stack(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;
                }
            }
        }
    
        }

本章重点

• 单链表的倒插法的算法

  • 图解倒插法

  • 算法：

    • heroNode.next = head.next;
      head.next = heroNode;