栈的介绍
栈（stack） 是一个先入后出的有序列表。栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，成为栈顶（Top），另一端为固定的一端，成为栈底（Botton）。根据栈的定义可知，先放入栈中的元素在栈底。最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。
栈的应用场景
- 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
- 处理递归调用：和子程序调用类似，只是除了存储下一个指令的地址外，也将参数，区域变量等数据存入堆栈中。
- 表达式的转换与求值（中缀表达式转后缀表达式）
- 二叉树的遍历
- 图形的深度优先（depth—first）搜索法。
栈的快速入门
用数组模拟栈的使用，由于栈是一种有序列表，当然可以使用数组的结构来存储栈的数据内容，下面我们就用数据模拟栈的出栈，入栈等操作。
实现栈的思路分析
- 使用数组来模拟栈
- 定义一个top 来表示栈顶，初始化为-1
- 入栈的操作，当有数据加入到栈时，top++;stack[top] = data;
- 出栈的操作，int value = stack[top];top–,return value
代码实现
- 创建ArrayStackDomo练习类
- 定义一个ArrayStack表示栈
class ArrayStack{ private int maxSize; //栈的大小 private int[] stack; //数组，数组模拟栈，数据就放在该数组 private int top = -1; //top表示栈顶，初始化为-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; }
- 编写入栈方法 push
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; }
- 编写显示栈的情况[遍历栈]，便利时，需要从栈顶开始显示数据。
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]); } }
测试
public static void main(String[] args) { //测试一下ArrayStack是否正确 //先创建一个ArrayStack对象->表示栈 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.print("请输入你的选择："); key=scanner.next(); switch (key){ case "show": stack.list(); break; case "exit": scanner.close(); loop=false; break; case "push": System.out.print("请输入一个数："); 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; default: break; } System.out.println("---------------------------------"); } System.out.println("程序已退出"); }
- 测试入栈
- 测试显示栈
- 测试出栈
完整代码
import java.util.Scanner; /** * @author mengzhichao * @create 2022-04-15-16:28 */ public class ArrayStackDemo { public static void main(String[] args) { //测试一下ArrayStack是否正确 //先创建一个ArrayStack对象->表示栈 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.print("请输入你的选择："); key=scanner.next(); switch (key){ case "show": stack.list(); break; case "exit": scanner.close(); loop=false; break; case "push": System.out.print("请输入一个数："); 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; default: break; } System.out.println("---------------------------------"); } System.out.println("程序已退出"); } } //定义一个 ArrayStack 表示栈 class ArrayStack{ private int maxSize; //栈的大小 private int[] stack; //数组，数组模拟栈，数据就放在该数组 private int top = -1; //top表示栈顶，初始化为-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; } //入栈-push 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; } //显示栈的情况[便利栈]，遍历时，需要从栈顶开始显示数据 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]); } } }
栈的一个实际需求
假如我们输入一串表达式字符串。计算机底层是如何运算得到结果的？如果用栈实现呢？
7+2∗6−4
使用栈完成表达式的计算思路
- 通过一个 index 值（索引），来遍历我们的表达式
- 如果我们发现是一个数字，就直接入栈
- 如果我们发现扫描到的是一个符号，就分如下情况，如果发现当前的符号栈为空，就直接入栈，如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出两个数，在从符号栈中pop出一个符号，进行运算，将得到的结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈。
- 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并进行运算。
- 最后在数栈只有一个数字，就是表达式的结果。
完整代码实现
/** * @author mengzhichao * @create 2022-04-16-11:12 */ public class Calculator { public static void main(String[] args) { //定义一个表达式 String expression = "7+2*6-4"; //创建两个栈，一个数栈，一个符号栈 CalculatorArrayStack numStack = new CalculatorArrayStack(100); CalculatorArrayStack operStack = new CalculatorArrayStack(100); int index = 0; //用于扫描 int num1 = 0; int num2 = 0; int oper = 0; int res = 0; char ch =' '; //将每次扫描得到的char保存在ch中 //开始while循环的扫描 expression while (true){ //一次得到 experssion 的每一个字符 ch = expression.substring(index,index+1).charAt(0); //判断ch是什么，然后做相应的处理 if (operStack.isOper(ch)){ //如果是运算符 //判断当前的符号栈是否为空 if (!operStack.isEmpty()){ //如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中的操作符， //就需要从数栈中pop出两个数，在从符号栈中pop出一个符号， //进行运算，将得到的结果，入数栈，然后将当前的操作符入符号栈 if (operStack.priority(ch) <= operStack.priority(operStack.peek())){ num1 = numStack.pop(); num2 = numStack.pop(); oper = operStack.pop(); res = numStack.cal(num1,num2,oper); //把运算的结果入数栈 numStack.push(res); //然后将当前的操作符入符号栈 operStack.push(ch); }else { //如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈 operStack.push(ch); } }else { //如果为空直接入符号栈... operStack.push(ch); // 7 * 2 } }else { numStack.push(ch - 48); } //让index + 1，并判断是否扫描到expression最后 index++; if (index >= expression.length()){ break; } } //当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并进行运算。 while (true){ //如果符号栈为空，则计算到最后的结果，数栈中只有一个数字【结果】 if (operStack.isEmpty()){ break; } num1 = numStack.pop(); num2 = numStack.pop(); oper = operStack.pop(); res = numStack.cal(num1,num2,oper); numStack.push(res); } //将数栈的最后数，pop出，就是结果 int res2 = numStack.pop(); System.out.printf("表达式%s = %d",expression,res2); } } //先创建一个栈 class CalculatorArrayStack{ private int maxSize; //栈的大小 private int[] stack; //数组，数组模拟栈，数据就放在该数组 private int top = -1; //top表示栈顶，初始化为-1表示没有数据 //构造器 public CalculatorArrayStack(int maxSize){ this.maxSize =maxSize; stack = new int[this.maxSize]; } //栈满 public boolean isFull(){ return top == maxSize - 1; //栈顶等于栈的大小的时候表示栈满 } //栈空 public boolean isEmpty(){ return top == -1; } //入栈-push public void push(int value){ //判断栈是否满 if (isFull()){ System.out.println("栈满"); return; } top++; stack[top] = value; } //返回栈顶的值，不做任何修改 public int peek(){ return stack[top]; } //出栈-pop，将栈顶的数据返回 public int pop(){ //先判断栈是否空 if (isEmpty()){ //抛出异常 throw new RuntimeException("栈空,没有数据~"); } int value = stack[top]; top--; return value; } //显示栈的情况[便利栈]，遍历时，需要从栈顶开始显示数据 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]); } } //返回运算符的优先级，优先级是程序员来确定，优先级使用数字表示 //数字越大，则优先级越高 public int priority(int oper){ if (oper == '*' || oper == '/'){ return 1; }else if (oper == '+' || oper == '-'){ return 0; } else { return -1; //假定目前的表达式只有+，-，*，/ } } //判断是不是一个运算符 public boolean isOper(char val){ return val == '+' || val == '-' || val == '*' || val == '/'; } //计算方法 public int cal(int num1,int num2,int oper){ int res = 0; //res 用于存放计算的结果 switch (oper){ case '+': res = num1 + num2; break; case '-': res = num2 - num1; //注意顺序 break; case '*': res = num1 * num2; break; case '/': res = num2 / num1; break; default: break; } return res; //结果返回 } }
运行并测试
经过测试我们发现通过程序计算出来的结果和我们算出来的结果是一致的，但是不知道大家有没有发现一个问题当我们把表达式中的 7 改为 70 后我们的计算结果就会出现一些问题。
那要怎么解决这个问题呢？我们接着往下看！
功能优化思路分析以及代码完善
- 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
- 在处理数，需要向expression的表达式的index 后再看一位，如果是数就进行扫描，如果是符号才入栈
- 因此我们需要定义一个变量 字符串，用于拼接
/** * @author mengzhichao * @create 2022-04-16-11:12 */ public class Calculator { public static void main(String[] args) { //定义一个表达式 String expression = "7*2*2-5+1-5+3-4"; //创建两个栈，一个数栈，一个符号栈 CalculatorArrayStack numStack = new CalculatorArrayStack(100); CalculatorArrayStack operStack = new CalculatorArrayStack(100); int index = 0; //用于扫描 int num1 = 0; int num2 = 0; int oper = 0; int res = 0; char ch =' '; //将每次扫描得到的char保存在ch中 String keepNum = ""; //用于拼接多位数 //开始while循环的扫描 expression while (true){ //一次得到 experssion 的每一个字符 ch = expression.substring(index,index+1).charAt(0); //判断ch是什么，然后做相应的处理 if (operStack.isOper(ch)){ //如果是运算符 //判断当前的符号栈是否为空 if (!operStack.isEmpty()){ //如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中的操作符， //就需要从数栈中pop出两个数，在从符号栈中pop出一个符号， //进行运算，将得到的结果，入数栈，然后将当前的操作符入符号栈 if (operStack.priority(ch) <= operStack.priority(operStack.peek())){ num1 = numStack.pop(); num2 = numStack.pop(); oper = operStack.pop(); res = numStack.cal(num1,num2,oper); //把运算的结果入数栈 numStack.push(res); //然后将当前的操作符入符号栈 operStack.push(ch); }else { //如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈 operStack.push(ch); } }else { //如果为空直接入符号栈... operStack.push(ch); // 7 * 2 } }else { // numStack.push(ch - 48); //分析思路 //1. 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数 //2. 在处理数，需要向expression的表达式的index 后再看一位，如果是数就进行扫描，如果是符号才入栈 //3. 因此我们需要定义一个变量 字符串，用于拼接 //处理多位数 keepNum += ch; //如果ch已经是expression的最后一位，就直接入栈。 if (index == expression.length() - 1){ numStack.push(Integer.parseInt(keepNum)); }else { //判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈 //注意是看后一位，不是index++ if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) { //如果后一位是运算符，则入栈 keepNum = "1" 或者 "123" numStack.push(Integer.parseInt(keepNum)); //重要的！！！！！！，keepNum清空 keepNum = ""; } } } //让index + 1，并判断是否扫描到expression最后 index++; if (index >= expression.length()){ break; } } //当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并进行运算。 while (true){ //如果符号栈为空，则计算到最后的结果，数栈中只有一个数字【结果】 if (operStack.isEmpty()){ break; } num1 = numStack.pop(); num2 = numStack.pop(); oper = operStack.pop(); res = numStack.cal(num1,num2,oper); numStack.push(res); } //将数栈的最后数，pop出，就是结果 int res2 = numStack.pop(); System.out.printf("表达式%s = %d",expression,res2); } } //先创建一个栈 class CalculatorArrayStack{ private int maxSize; //栈的大小 private int[] stack; //数组，数组模拟栈，数据就放在该数组 private int top = -1; //top表示栈顶，初始化为-1表示没有数据 //构造器 public CalculatorArrayStack(int maxSize){ this.maxSize =maxSize; stack = new int[this.maxSize]; } //栈满 public boolean isFull(){ return top == maxSize - 1; //栈顶等于栈的大小的时候表示栈满 } //栈空 public boolean isEmpty(){ return top == -1; } //入栈-push public void push(int value){ //判断栈是否满 if (isFull()){ System.out.println("栈满"); return; } top++; stack[top] = value; } //返回栈顶的值，不做任何修改 public int peek(){ return stack[top]; } //出栈-pop，将栈顶的数据返回 public int pop(){ //先判断栈是否空 if (isEmpty()){ //抛出异常 throw new RuntimeException("栈空,没有数据~"); } int value = stack[top]; top--; return value; } //显示栈的情况[便利栈]，遍历时，需要从栈顶开始显示数据 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]); } } //返回运算符的优先级，优先级是程序员来确定，优先级使用数字表示 //数字越大，则优先级越高 public int priority(int oper){ if (oper == '*' || oper == '/'){ return 1; }else if (oper == '+' || oper == '-'){ return 0; } else { return -1; //假定目前的表达式只有+，-，*，/ } } //判断是不是一个运算符 public boolean isOper(char val){ return val == '+' || val == '-' || val == '*' || val == '/'; } //计算方法 public int cal(int num1,int num2,int oper){ int res = 0; //res 用于存放计算的结果 switch (oper){ case '+': res = num1 + num2; break; case '-': res = num2 - num1; //注意顺序 break; case '*': res = num1 * num2; break; case '/': res = num2 / num1; break; default: break; } return res; //结果返回 } }
再次测试
该问题成功解决。
