• 数据结构和算法——基于Java——4.1栈(数组实现栈、链表实现栈)


    理论补充

    在这里插入图片描述

    先进后出 FILO(First-Input-Last-Out)的有序列表,限制线性表中元素的插入和删除只能在线性表的同一端进行

    • 栈顶:变化的一端
    • 栈底:固定的一端

    代码实现

    2.1 数组模拟栈

    package com.b0.stack;
    
    import java.util.Scanner;
    
    public class ArrayStackDemo {
        public static void main(String[] args) {
            ArrayStack stack = new ArrayStack(5);
            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.println("出栈数据是:"+res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case "exit":
                        scanner.close();
                        loop = false;
                        break;
                    default:
                        break;
                }
            }
            System.out.println("程序退出~");
        }
    }
    class ArrayStack{
        private int maxSize;//栈的大小
        private int[] stack;//数组模拟栈
        private int top = -1;//栈顶,初始化为-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 num){
            //判断是否栈满
            if (isFull()){
                System.out.println("栈满");
                return;
            }
            top++;
            stack[top] = num;
        }
        //出栈
        public int pop(){
            //判断是否栈空
            if (isEmpty()){
                //抛出异常
                throw new RuntimeException("栈空,没有数据!");
            }
            int value = stack[top];
            top--;
            return value;
        }
        //遍历栈
        public void list(){
            if (isEmpty()){
                System.out.println("栈空!");
                return;
            }
            while (top != -1){
                //从栈顶开始遍历
                System.out.println(stack[top]);
                top--;
            }
        }
    }
    
    
    • 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
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97

    2.2 链表模拟栈(头插法)

    在这里插入图片描述

    package com.b0.stack;
    
    public class LinkedStackDemo {
        public static void main(String[] args) {
            LinkedStack linkedStack = new LinkedStack();
            linkedStack.push(1);
            linkedStack.push(2);
            linkedStack.push(3);
            linkedStack.push(4);
            System.out.println("出栈值为:"+linkedStack.pop());
            System.out.println("出栈值为:"+linkedStack.pop());
            System.out.println("出栈值为:"+linkedStack.pop());
            System.out.println("出栈值为:"+linkedStack.pop());
        }
    }
    class LinkedStack{
        //头节点
        Node head = new Node(0);
        //栈空,尾插法
        public boolean isEmpty(){
            return head.next == null;
        }
        //入栈,头插法
        public void push(int num){
            Node node = new Node(num);
            if (isEmpty()){
                head.next = node;
            }
            node.next = head.next;
            head.next = node;
        }
        public int pop(){
            if (isEmpty()){
                //抛出异常
                throw new RuntimeException("栈空,没有数据!");
            }
            //定义零时变量,不修改head指针指向
            Node cur = head;
            int value = cur.next.no;
            cur.next = cur.next.next;
            return value;
        }
    }
    class Node{
        public int no;
        public Node next;
    
        public Node(int no) {
            this.no = no;
        }
    }
    
    
    • 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
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    2.3 链表模拟栈(尾插法,不推荐)

    package com.b0.stack;
    
    public class LinkedStackDemo {
        public static void main(String[] args) {
            LinkedStack linkedStack = new LinkedStack();
            linkedStack.push(1);
            linkedStack.push(2);
            linkedStack.push(3);
            linkedStack.push(4);
            System.out.println("出栈值为:"+linkedStack.pop());
            System.out.println("出栈值为:"+linkedStack.pop());
            System.out.println("出栈值为:"+linkedStack.pop());
            System.out.println("出栈值为:"+linkedStack.pop());
            System.out.println("出栈值为:"+linkedStack.pop());
        }
    }
    class LinkedStack{
        //头节点
        Node head = new Node(0);
        //栈空
        public boolean isEmpty(){
            return head.next == null;
        }
        //入栈
        public void push(int num){
            Node node = new Node(num);
            Node cur = head;
            while (true){
                if (cur.next == null)break;
                cur = cur.next;
            }
            cur.next = node;
        }
        //出栈
        public int pop(){
            if (isEmpty()){
                //抛出异常
                throw new RuntimeException("栈空,没有数据!");
            }
            //定义零时变量,不修改head指针指向
            Node cur = head;
            int value;
            while (true){
                if (cur.next.next == null){
                    value = cur.next.no;
                    cur.next = null;
                    break;
                }
               cur = cur.next;
            }
            return value;
        }
    }
    class Node{
        public int no;
        public Node next;
    
        public Node(int no) {
            this.no = no;
        }
    }
    
    
    • 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
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
  • 相关阅读:
    Tomcat 如何加载 SpringMVC 组件
    科技的成就(三十六)
    【LeetCode】三个无重叠子数组的最大和 [H](动态规划)
    JMeter参数化方式:三招让你的性能测试更灵活!
    uniapp IOS上架AppStore因打开相机、相册提示不明确被拒
    linuex服务器中如何安装mysql数据库(一次性完成,包含远程连接)
    谈谈我对云原生与软件供应链安全的思考
    基于PySide6的数据处理及可视化分析软件开发
    【Oracle】数据库导入导出
    HTB-Paper
  • 原文地址:https://blog.csdn.net/G_change_/article/details/128136622