栈

发表于 更新于 分类于

栈

背景

  • 数据结构——栈

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

介绍

  • 栈是一个先进后出的有序列表

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

  • 先进的元素后删除，后进的元素先删除

思路

  • 使用数组模拟栈

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

  • 入栈操作，当有数据入栈时，top++；stack[top] = data;

  • 出栈操作，int value = stack [top];top–,return value;

步骤

  • 创建一个测试类ArrayStackDemo

    • 代码实现

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      public class ArrayStackDemo {
          public static void main(String[] args) {
          //测试
              ArrayStack stack = new ArrayStack(4);
              String key =" ";
              boolean loop = true;//控制是否退出菜单
              Scanner scanner = new Scanner(System.in);
              while(loop){
                  System.out.println("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 "push":
                          System.out.println("请输入一个数：");
                          int value = scanner.nextInt();
                          stack.push(value);
                          break;
                      case "pop":
                          try {
                          int res = stack.pop();
                              System.out.printf("出栈的数据是%d\n",res);
                          }catch (Exception e){
                              System.out.println(e.getMessage());
                          }
                          break;
                      case "exit":
                          scanner.close();
                          loop = false;
                          break;
                      default:
                          break;

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

  • 定义一个ArrayStack类

    • 栈的大小

      • 代码实现

        1
        private int maxSize;

    • 数组模拟栈，数据放在改数组

      • 代码实现

        1
        private int[] stack;

    • top表示栈顶，初始化为-1

      • 代码实现

        1
        private int top = -1;

    • 栈满

      • 代码实现

        1
        2
        3
        public boolean isFull(){
            return top == maxSize -1;
        }

    • 栈空

      • 代码实现

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

    • 入栈

      • 代码实现

        1
        2
        3
        4
        5
        6
        7
        8
        9
        public void push(int value){
            //判断栈是否满
            if(isFull()){
                System.out.println("栈满");
                return;
            }
            top++;
            stack[top] = value;
        }

    • 出栈

      •  //出栈pop，将栈顶数据返回
    public int pop(){
     //先判断栈是否空
        if(isEmpty()){
            //抛出异常
             throw new RuntimeException("栈空");
        }
        int value = stack[top];
        top--;
        return value;
    }

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17

        * 遍历栈

          * 代码实现

          ```java
            //遍历栈，遍历时要从栈顶开始
               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]);
                   }
               }