原文地址：https://blog.csdn.net/guorui_java/article/details/106193563

一、栈

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

二、栈的应用场景

1、子程序的调用

在调往子程序前，会先将下个指令的地址存放到堆栈中，直到子程序执行完后再将地址抛出，以回到原来的程序。

2、处理递归调用

和子程序的调用类似，除了村下个指令的地址外，还要存放参数，区域变量等数据。

3、表达式的转换

中缀表达式转后缀表达式

4、二叉树的遍历

5、图形的深度优先搜索法

三、栈实现综合计算器（中缀表达式）

1、思路分析

  • 通过一个index值（索引），来遍历我们的表达式
  • 如果发现是一个数字直接入数栈
  • 如果发现当前的符号栈是空，就直接入栈
  • 如果发现符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或等于栈中的操作符，就需要从数栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈。
  • 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并进行运算。
  • 最后在数栈中只有一个数字，就是表达式的结果。

    2、代码实例

（1）ArrayStack工具类

  1. package dataStructure.stack;
  3. public class ArrayStack {
  4.     private int maxSize; // 栈的大小
  5.     private int[] stack; // 数组，数组模拟栈，数据就放在该数组
  6.     private int top = -1;// top表示栈顶，初始化为-1
  8.     //构造器
  9.     public ArrayStack(int maxSize) {
  10.         this.maxSize = maxSize;
  11.         stack = new int[this.maxSize];
  12.     }
  14.     //增加一个方法，可以返回当前栈顶的值, 但是不是真正的pop
  15.     public int peek() {
  16.         return stack[top];
  17.     }
  19.     //栈满
  20.     public boolean isFull() {
  21.         return top == maxSize - 1;
  22.     }
  23.     //栈空
  24.     public boolean isEmpty() {
  25.         return top == -1;
  26.     }
  27.     //入栈-push
  28.     public void push(int value) {
  29.         //先判断栈是否满
  30.         if(isFull()) {
  31.             System.out.println("栈满");
  32.             return;
  33.         }
  34.         top++;
  35.         stack[top] = value;
  36.     }
  37.     //出栈-pop, 将栈顶的数据返回
  38.     public int pop() {
  39.         //先判断栈是否空
  40.         if(isEmpty()) {
  41.             //抛出异常
  42.             throw new RuntimeException("栈空，没有数据~");
  43.         }
  44.         int value = stack[top];
  45.         top--;
  46.         return value;
  47.     }
  48.     //显示栈的情况[遍历栈]， 遍历时，需要从栈顶开始显示数据
  49.     public void list() {
  50.         if(isEmpty()) {
  51.             System.out.println("栈空，没有数据~~");
  52.             return;
  53.         }
  54.         //需要从栈顶开始显示数据
  55.         for(int i = top; i >= 0 ; i--) {
  56.             System.out.printf("stack[%d]=%d\n", i, stack[i]);
  57.         }
  58.     }
  59.     //返回运算符的优先级，优先级是程序员来确定, 优先级使用数字表示
  60.     //数字越大，则优先级就越高.
  61.     public int priority(int oper) {
  62.         if(oper == '*' || oper == '/'){
  63.             return 1;
  64.         } else if (oper == '+' || oper == '-') {
  65.             return 0;
  66.         } else {
  67.             return -1; // 假定目前的表达式只有 +, - , * , /
  68.         }
  69.     }
  70.     //判断是不是一个运算符
  71.     public boolean isOper(char val) {
  72.         return val == '+' || val == '-' || val == '*' || val == '/';
  73.     }
  74.     //计算方法
  75.     public int cal(int num1, int num2, int oper) {
  76.         int res = 0; // res 用于存放计算的结果
  77.         switch (oper) {
  78.             case '+':
  79.                 res = num1 + num2;
  80.                 break;
  81.             case '-':
  82.                 res = num2 - num1;// 注意顺序
  83.                 break;
  84.             case '*':
  85.                 res = num1 * num2;
  86.                 break;
  87.             case '/':
  88.                 res = num2 / num1;
  89.                 break;
  90.             default:
  91.                 break;
  92.         }
  93.         return res;
  94.     }
  95. }

（2）测试类

  1. package dataStructure.stack;
  3. public class Calculator {
  4.     public static void main(String[] args) {
  5.         //根据前面老师思路，完成表达式的运算
  6.         String expression = "100/5+2*3-1"; // 25
  7.         //创建两个栈，数栈，一个符号栈
  8.         ArrayStack numStack = new ArrayStack(10);
  9.         ArrayStack operStack = new ArrayStack(10);
  10.         //定义需要的相关变量
  11.         int index = 0;//用于扫描
  12.         int num1 = 0;
  13.         int num2 = 0;
  14.         int oper = 0;
  15.         int res = 0;
  16.         char ch = ' '; //将每次扫描得到char保存到ch
  17.         String keepNum = ""; //用于拼接 多位数
  18.         //开始while循环的扫描expression
  19.         while (true) {
  20.             //依次得到expression 的每一个字符
  21.             ch = expression.substring(index, index + 1).charAt(0);
  22.             //判断ch是什么，然后做相应的处理
  23.             if (operStack.isOper(ch)) {//如果是运算符
  24.                 //判断当前的符号栈是否为空
  25.                 if (!operStack.isEmpty()) {
  26.                     //如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出两个数,
  27.                     //在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈
  28.                     if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
  29.                         num1 = numStack.pop();
  30.                         num2 = numStack.pop();
  31.                         oper = operStack.pop();
  32.                         res = numStack.cal(num1, num2, oper);
  33.                         //把运算的结果如数栈
  34.                         numStack.push(res);
  35.                         //然后将当前的操作符入符号栈
  36.                         operStack.push(ch);
  37.                     } else {
  38.                         //如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.
  39.                         operStack.push(ch);
  40.                     }
  41.                 } else {
  42.                     //如果为空直接入符号栈..
  43.                     operStack.push(ch); // 1 + 3
  44.                 }
  45.             } else { //如果是数，则直接入数栈
  47.                 //numStack.push(ch - 48); //? "1+3" '1' => 1
  48.                 //分析思路
  49.                 //1. 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
  50.                 //2. 在处理数，需要向expression的表达式的index 后再看一位,如果是数就进行扫描，如果是符号才入栈
  51.                 //3. 因此我们需要定义一个变量 字符串，用于拼接
  53.                 //处理多位数
  54.                 keepNum += ch;
  56.                 //如果ch已经是expression的最后一位，就直接入栈
  57.                 if (index == expression.length() - 1) {
  58.                     numStack.push(Integer.parseInt(keepNum));
  59.                 } else {
  60.                     //判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
  61.                     //注意是看后一位，不是index++
  62.                     if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
  63.                         //如果后一位是运算符，则入栈 keepNum = "1" 或者 "123"
  64.                         numStack.push(Integer.parseInt(keepNum));
  65.                         //重要的!!!!!!, keepNum清空
  66.                         keepNum = "";
  67.                     }
  68.                 }
  69.             }
  70.             //让index + 1, 并判断是否扫描到expression最后.
  71.             index++;
  72.             if (index >= expression.length()) {
  73.                 break;
  74.             }
  75.         }
  77.         //当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行.
  78.         while (true) {
  79.             //如果符号栈为空，则计算到最后的结果, 数栈中只有一个数字【结果】
  80.             if (operStack.isEmpty()) {
  81.                 break;
  82.             }
  83.             num1 = numStack.pop();
  84.             num2 = numStack.pop();
  85.             oper = operStack.pop();
  86.             res = numStack.cal(num1, num2, oper);
  87.             numStack.push(res);//入栈
  88.         }
  89.         //将数栈的最后数，pop出，就是结果
  90.         int res2 = numStack.pop();
  91.         System.out.printf("表达式 %s = %d", expression, res2);
  92.     }
  93. }

3、控制台输出

5.栈实现综合计算器 - 图1