java模拟栈的操作
- 2020 年 4 月 5 日
- 筆記
栈是一种有序列表，可以使用数组的结构来储存栈的数据内容
思路
1. 创建一个栈类StackArray
2. 定义一个top来模拟栈顶，初始化为-1
3. 入栈： 当有数据加入到栈的时候 top++ stack[top] = data
4. 出栈 int value = stack[top]; top--, return value
代码实现
//定义一个类来表示栈 class ArrayStack{ private int maxSize; //栈的大小 private int[] stack; //数组模拟栈 数据放在数组中 private int top = -1; //top 表示栈顶 //构造器 public ArrayStack(int maxSize) { this.maxSize = maxSize; stack = new int[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]=%dn", i,stack[i]); } } }
通过main方法调用自定义的栈类来模拟栈的操作
public class StackArrayDemo { 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.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 result = stack.pop(); System.out.printf("取出的数据为：%dn", result); }catch (Exception e){ System.out.println(e.getMessage()); } break; case "exit": scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出"); } }
根据上边的内容 来模拟一下用栈实现的计算表达式的功能
思路
通过一个index（索引） 来遍历我们的表达式
如果我们发现是一个数字 就直接入数栈
如果扫描到的是一个符号 就分如下情况
1.如果当前符号栈为空， 就直接入栈
2.如果符号栈有操作符 就进行比较 如果当前操作符的优先级 小于或等于栈中的操作符
就需要从数栈中pop出两个数，再从符号栈中pop出一个符号，进行运算，将得到的结果入数栈
再把当前的符号入符号栈，
3.如果当前符号的优先级大于栈中的操作符，直接入栈
扫描完毕后 就顺序地冲数栈和符号栈中pop出响应的数和符号 并运行
最后在数栈中只有一个数字就是表达式的结果
参考上边的ArrayStack类 拓展一个ArrayStack2 类 并对功能进行增强
//定义一个类来表示栈 对ArrayStack进行扩展 class ArrayStack2{ private int maxSize; //栈的大小 private int[] stack; //数组模拟栈 数据放在数组中 private int top = -1; //top 表示栈顶 //构造器 public ArrayStack2(int maxSize) { this.maxSize = maxSize; stack = new int[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]=%dn", 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 oper, int num1, int num2){ int result = 0; // 用于存放计算的结果 switch (oper){ case '+': result = num1 + num2; break; case '-': result = num2 - num1; break; case '*': result = num2 * num1; break; case '/': result = num2 / num1; break; default: break; } return result; } //返回栈顶的值 不Pop public int peek(){ return stack[top]; } }
调用主方法 进行案例的具体实现
public class StackCalculate { public static void main(String[] args) { //完成表达式的运算 String expression = "500+7*2-8"; //创建两个栈 一个数栈一个符号栈 ArrayStack2 numStack = new ArrayStack2(10); ArrayStack2 operStack = new ArrayStack2(10); //定义扫描的索引 int index = 0; int num1 = 0; int num2 = 0; int oper = 0; int res = 0; //将每次扫描的的char保存到ch中 char ch = ' '; //用于拼接多位数 String keepNum = ""; //循环扫描表达式 while (true){ //依次得到expression的每一个字符 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(oper,num1, num2); //将运算结果压入数栈 numStack.push(res); //将当前运算符压入符号栈 operStack.push(ch); }else { operStack.push(ch); } }else { //为空 直接入栈、 operStack.push(ch); } }else { //如果ch是数字 直接入数栈 // numStack.push(ch - 48); // ASCII码转换成int //当处理多位数时 有可能是多位数 因此 需要定义一个字符串变量 用于拼接 keepNum += ch; //如果ch已经到expression的最后一位了直接入栈 if (index == expression.length() - 1){ numStack.push(Integer.parseInt(keepNum)); } else if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))){ // 如果后一位是运算符则入栈 numStack.push(Integer.parseInt(keepNum)); //!!重要的 清空keepNum keepNum = ""; } } //index ++ 判断是否扫描到表达式最后的位置 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(oper,num1, num2); numStack.push(res); } //将最后的计算结果pop出 int finalRes = numStack.pop(); System.out.printf("表达式%s = %d", expression, finalRes); } }
