【Java数据结构和算法】008-栈

浅浅的花香味﹌ 2023-10-05 13:38 83阅读 0赞

# **目录** #

0、警醒自己

一、栈的应用场景和介绍

1、栈的应用场景

一个实际的场景：

我的思考：

2、栈的介绍

入栈演示图：

出栈演示图：

栈的应用场景：

二、栈的思路分析和代码实现

1、思路分析

数组模拟栈的思路分析图：

2、代码实现

3、运行结果

4、备注

三、栈实现综合计算器

1、思路分析

2、简单的表达式验证思路

简单的表达式：

验证思路：

3、代码实现

4、运行结果

5、关于运算数是多位数的备注

--------------------

# 0、警醒自己 #

**1、学习不用心，骗人又骗己；**

**2、学习不刻苦，纸上画老虎；**

**3、学习不惜时，终得人耻笑；**

**4、学习不复习，不如不学习；**

**5、学习不休息，毁眼伤身体；**

**7、狗才等着别人喂，狼都是自己寻找食物；**

# 一、栈的应用场景和介绍 #

## 1、栈的应用场景 ##

### 一个实际的场景： ###

请输入一个表达式 计算式:\[7\*2\*2-5+1-5+3-3\] 点击计算【如下图】：

![20201114110731348.png][]

**请问：计算机底层是如何运算得到结果的？**

注意不是简单的把算式列出运算，因为我们看这个算式 7 \* 2 \* 2 - 5, 但是计算机怎么理解这个算式的(对计算机而言，它接收到的就是一个字符串)，我们讨论的是这个问题。-> 栈

### 我的思考： ###

假如是我的话，给我一串这样的字符串，让我对其进行计算，我的思路是先用正则表达式匹配，看是否存在数组和加减乘除之外的字符，如果有就报错，如果没有就继续计算，因为要先算加减再算乘除，所以先去匹配\*/，先获取有多少个数参与计算，也就是+-\*/符号的数量+1，要注意相邻的乘除，将乘除计算之后用字符串替换的方式将之前的算式替换为计算的结果，剩下来的就是加和减了，按顺序计算即可，简单思考一下，不成熟的想法，代码实现就不做了，因为我对正则表达式不熟悉。

## 2、栈的介绍 ##

①栈的英文为(stack)；

②栈是一个**先入后出**(FILO-First In Last Out)的**有序列表**；

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

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

### 入栈演示图： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70][]

### 出栈演示图： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 1][]

### 栈的应用场景： ###

①子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中；

②处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中；

③表达式的转换\[中缀表达式转后缀表达式\]与求值(实际解决)；

④二叉树的遍历；

⑤图形的深度优先(depth一first)搜索法；

# 二、栈的思路分析和代码实现 #

## 1、思路分析 ##

### 数组模拟栈的思路分析图： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 2][]

## 2、代码实现 ##

package com.zb.ds;
    
    //演示栈的使用
    public class TestStack {
        public static void main(String[] args) {
            MyStack stack = new MyStack(5);
            //入栈
            stack.push(12);
            stack.push(71);
            stack.push(4);
            stack.push(22);
            stack.push(99);
            stack.push(999);
            //出栈
            System.out.println(stack.pop() + "出栈成功！");
            System.out.println(stack.pop() + "出栈成功！");
            System.out.println(stack.pop() + "出栈成功！");
            System.out.println(stack.pop() + "出栈成功！");
            System.out.println(stack.pop() + "出栈成功！");
            System.out.println(stack.pop() + "出栈成功！");
        }
    }
    class MyStack{
        private int top = -1;
        private final int[] stack;
    
        public MyStack(int length) {
            stack = new int[length];
        }
    
        //入栈
        public void push(int num){
            top++;
            if(top<stack.length){
                stack[top] = num;
                System.out.println(num + "入栈成功！");
            }else {
                System.out.println("栈满了，添加失败！");
                //这里减-，是下移，因为上面top++上移一位，发现上移一位之后栈满了，那么top就数组下标越界了，所以减-回到栈顶
                top--;
            }
        }
    
        //出栈
        public int pop() {
            if (top > -1) {
                return stack[top--];
            } else {
                throw new RuntimeException("栈为空，出栈失败！");
            }
        }
    }

## 3、运行结果 ##

12入栈成功！
    71入栈成功！
    4入栈成功！
    22入栈成功！
    99入栈成功！
    栈满了，添加失败！
    99出栈成功！
    22出栈成功！
    4出栈成功！
    71出栈成功！
    12出栈成功！
    Exception in thread "main" java.lang.RuntimeException: 栈为空，出栈失败！
    	at com.zb.ds.MyStack.pop(TestStack.java:49)
    	at com.zb.ds.TestStack.main(TestStack.java:20)

## 4、备注 ##

我们也可以写一个判断栈是否满或者为空的方法，在入栈和出栈之前调用判断，这里不再演示；

# 三、栈实现综合计算器 #

## 1、思路分析 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 3][]

## 2、简单的表达式验证思路 ##

### 简单的表达式： ###

3+2\*6-2

### 验证思路： ###

拿到3，直接入数栈；拿到+，发现符号栈为空，入符号栈；拿到2，直接入数栈；拿到\*，发现\*的优先级大于符号栈栈顶符号+，入符号栈；拿到6，直接入数栈；拿到-，发现-的优先级小于符号栈栈顶符号\*，pop出数栈中的6和2，再pop出符号栈中的\*，使得2\*6=12，将12直接入数栈，继续比较，发现-的幼年及等于符号栈栈顶符号+，所以再从数栈中pop出12和3，从符号栈中pop出+，使得3+12=15，将15直接入数栈，此时发现符号栈为空，将-直接入符号栈；拿到2，直接如数栈；表达式遍历完毕，从数栈中pop出2和15，从符号栈中pop出-，使得15-2=13，将13入数栈；此时发现，数栈中值的数量为1，符号栈为空，得知数栈中的13就是最终运算结果；

## 3、代码实现 ##

package com.zb.ds;
    
    public class MyCalculator {
        public static void main(String[] args) {
            // 默认的表达式，咱这里只讨论题目，不讨论二位数字的情况
            String expression = "7*2*2-5+1-5+3-3";
            // 创建两个栈：数栈、符号栈
            MyStack2 numStack = new MyStack2(10);
            MyStack2 operatorStack = new MyStack2(10);
            char[] chars = expression.toCharArray();
            for (char c : chars) {
                if(MyStack2.isOperator(c)){
                    // 操作符入栈
                    MyStack2.pushOper(c,operatorStack,numStack);
                }else {
                    // 数字入栈
                    System.out.println("数字入栈：" + c);
                    //字符‘7’等于数字55
                    int cr = Integer.parseInt(c + "");
                    numStack.push(cr);
                }
            }
            // 遍历完毕，全部入栈结束了
            // 当表达式遍历完毕，就顺序从数栈和符号栈pop出相应的数和符号进行运算，并将结果直接入数栈，以此循环往复直到数栈剩下一个数，
            // 符号栈为空，此时数栈中的剩下的数就是表达式计算的结果
            // 其实要循环的次数就是操作符的数量，因为每次运算消耗一个运算符两个数字，又产生一个数字，运算符变化简单
            int elementNum = operatorStack.getElementNum();
            while (elementNum!=0){
                MyStack2.pAndC(operatorStack,numStack);
                elementNum = operatorStack.getElementNum();
            }
            // 遍历完毕，符号栈为空，数栈剩下一个数字，弹出即可得到最终运算结果
            System.out.println("表达式计算结果：" + numStack.pop());
        }
    }
    class MyStack2{
        private int top = -1;
        private final int[] stack;
        private boolean isFull;
    
        public MyStack2(int length) {
            stack = new int[length];
        }
    
        // 入栈
        public void push(int num){
            top++;
            if(top<stack.length){
                stack[top] = num;
                System.out.println(num + "入栈成功！");
            }else {
                System.out.println("栈满了，添加失败！");
                isFull = true;
                //这里减-，是下移，因为上面top++上移一位，发现上移一位之后栈满了，那么top就数组下标越界了，所以减-回到栈顶
                top--;
            }
        }
    
        // 出栈
        public int pop() {
            if (top > -1) {
                return stack[top--];
            } else {
                throw new RuntimeException("栈为空，出栈失败！");
            }
        }
    
        // 观察栈顶元素
        public int watchTop(){
            if (top > -1) {
                return stack[top];
            } else {
                throw new RuntimeException("栈为空，出栈失败！");
            }
        }
    
        //符号入栈
        public static void pushOper(char c,MyStack2 operatorStack,MyStack2 numStack){
            //此时判断一下符号栈是否为空，如果为空，直接入栈
            if(operatorStack.isNull()){
                //操作符入栈
                System.out.println("操作符入栈：" + c);
                operatorStack.push(c);
            }else {
                //进行符号入栈操作
                //这个时候不应该弹出来，应该是观察
                int watchTop = operatorStack.watchTop();
                //比较两个操作符的优先级
                //分别获取操作符的优先级的数字表示
                int priorityThis = MyStack2.priority(c);
                int priorityTop = MyStack2.priority((char) watchTop);
                // 进行比较：如果当前符号的优先级小于或等于栈顶符号的优先级，那就从数栈中pop两个数，
                // 从符号栈中pop一个符号，进行运算，将运算结果入数栈
                if(priorityThis<=priorityTop){
                    int num1 = numStack.pop();
                    int num2 = numStack.pop();
                    int oper = operatorStack.pop();
                    int res = MyStack2.cal(num1, num2, (char) oper);
                    //数字入栈
                    System.out.println("数字入栈：" + res);
                    numStack.push(res);
                    //上一个计算结果入数栈了，那符号应该继续跟栈顶符号进行判断，以此循环，知道当前符号入了符号栈
                    //调用自己，直到c入了符号栈才算罢休
                    pushOper(c,operatorStack,numStack);
                }else {
                    //操作符入栈
                    System.out.println("操作符入栈：" + c);
                    operatorStack.push(c);
                }
            }
        }
    
        //数栈弹出两个数字、符号栈弹出一个符号，进行运算，然后将运算结果入数栈
        public static void pAndC(MyStack2 operatorStack,MyStack2 numStack){
            int num1 = numStack.pop();
            int num2 = numStack.pop();
            int oper = operatorStack.pop();
            int res = MyStack2.cal(num1, num2, (char) oper);
            numStack.push(res);
        }
    
        //获取当前元素数量
        public int getElementNum(){
            return top + 1;
        }
    
    
        //判断是否为空
        public boolean isNull(){
            return top == -1;
        }
    
        //判断是否满
        public boolean isFull(){
            return isFull;
        }
    
        //返回运算符的优先级，优先级是程序员来确定的，优先级使用数字表示，我们假定数字越大优先级越高
        public static int priority(char operator){
            if(operator=='*' || operator=='/'){
                return 1;
            }else if(operator=='+' || operator=='-'){
                return 0;
            }else {
                return -1;//假定目前表达式只含有+-*/
            }
        }
    
        //判断是否是一个操作符
        public static boolean isOperator(char val){
            return val == '+' || val == '-' || val == '*' || val == '/';
        }
    
        //计算方法
        public static int cal(int num1, int num2, char oper){
            int res;//res用来存储计算结果
            switch (oper){
                case '+':
                    res = num1 + num2;
                    break;
                case '-':
                    res = num2 - num1;
                    break;
                case '*':
                    res = num1 * num2;
                    break;
                case '/':
                    res = num2 / num1;
                    break;
                default:
                    throw new RuntimeException("意料之外的情况，操作符为：" + oper);
            }
            return res;
        }
    }

## 4、运行结果 ##

数字入栈：7
    7入栈成功！
    操作符入栈：*
    42入栈成功！
    数字入栈：2
    2入栈成功！
    数字入栈：14
    14入栈成功！
    操作符入栈：*
    42入栈成功！
    数字入栈：2
    2入栈成功！
    数字入栈：28
    28入栈成功！
    操作符入栈：-
    45入栈成功！
    数字入栈：5
    5入栈成功！
    数字入栈：23
    23入栈成功！
    操作符入栈：+
    43入栈成功！
    数字入栈：1
    1入栈成功！
    数字入栈：24
    24入栈成功！
    操作符入栈：-
    45入栈成功！
    数字入栈：5
    5入栈成功！
    数字入栈：19
    19入栈成功！
    操作符入栈：+
    43入栈成功！
    数字入栈：3
    3入栈成功！
    数字入栈：22
    22入栈成功！
    操作符入栈：-
    45入栈成功！
    数字入栈：3
    3入栈成功！
    19入栈成功！
    表达式计算结果：19

## 5、关于运算数是多位数的备注 ##

其实并不难，只需要在发现（遍历到）一位数字的时候，看看下一位是数字还是符号，是数字继续往后看，知道发现符号，前面的数字是一个数，再用Integer.parseInt()解析成数字即可；

[20201114110731348.png]: https://img-blog.csdnimg.cn/20201114110731348.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020111411351628.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201114113558377.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201114115656480.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020111412395548.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70