1. 使用数组模拟栈

//定义一个ArrayStack表示栈,使用数组模拟 class ArrayStack{ public int maxSize; //栈的大小 public int[] stack; //数组，数组模拟栈，数据就放在这里 public int top = -1 ;//top表示栈顶，初始化为-1 //构造器,因为数组一定要初始化大小，所以我们使用有参构造 public ArrayStack(int maxSize) { this.maxSize = maxSize; stack = new int[this.maxSize]; //初始化数组的大小 } //栈满 public boolean isFull(){ //当top == maxSize-1 时，栈就满了 return top==maxSize-1; //栈满 返回true } //栈空 public boolean isEmpty(){ return top==-1; //当top等于-1时，栈是空的 } //入栈，每近来一个数据top就++ public void push(int value){ //先判断栈是否满了 if (isFull()){ System.out.println("栈满"); return; } top++; stack[top]=value; } //出栈，没出去一个数据，top就-- public int pop(){ if (isEmpty()){ System.out.println("栈空"); return -1; } 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]); } } }

2. 创建stack

import java.util.Scanner; public class ArrayStackDemo { public static void main(String[] args) { //测试是否可以使用 ArrayStack arrayStack = new ArrayStack(4); //创建栈的大小为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": arrayStack.list(); break; case "push": System.out.println("请输入一个数"); int value = scanner.nextInt(); arrayStack.push(value); break; case "pop": int pop = arrayStack.pop(); System.out.println("出栈的数据为:"+pop); break; case "exit": scanner.close(); //关闭输入流 loop = false; break; default: break; } } System.out.println("程序退出了"); } }

结果

3. 使用数组模拟stack并模拟计算器

思路：重点

//定义一个ArrayStack表示栈,使用数组模拟，需要扩展功能 class ArrayStack2{ public int maxSize; //栈的大小 public int[] stack; //数组，数组模拟栈，数据就放在这里 public int top = -1 ;//top表示栈顶，初始化为-1 //构造器 public ArrayStack2(int maxSize) { this.maxSize = maxSize; stack = new int[this.maxSize]; //初始化数组的大小 } //栈满 public boolean isFull(){ //当top == maxSize-1 时，栈就满了 return top==maxSize-1; //栈满 返回true } //栈空 public boolean isEmpty(){ return top==-1; //当top等于-1时，栈是空的 } //入栈 public void push(int value){ //先判断栈是否满了 if (isFull()){ System.out.println("栈满"); return; } top++; stack[top]=value; } //出栈 public int pop(){ if (isEmpty()){ System.out.println("栈空"); return -1; } 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; // 用来存放计算结果 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; } //增加一个方法，可以返回当前栈顶的值，但是不弹出 public int peek(){ return stack[top]; } }

4. 模拟计算器

public class Calculator { public static void main(String[] args) { String expression = "70+2*6-4"; //输入表达式 //创建两个栈，一个是数栈，一个符号栈 ArrayStack2 numStack = new ArrayStack2(20); //数栈 ArrayStack2 operStack = new ArrayStack2(20); //符号栈 //定义需要的相关变量 int index = 0 ; //用于扫描的 int num1 = 0 ; //第一个数 int num2 = 0 ; //第二个数 int oper = 0 ; //操作符 int res = 0; //临时结果 char ch = ' '; //将每次扫描的char保存在ch String keepNum = "" ;//用于拼接多位数 //开始循环扫描expression while (true){ //一次扫描expression的每一个字符 //substring方法，截取一段字符串，成为一个新的字符串，从下标为index1开始，并扩展到index2-1处，长度为index2-index1 //substring(index1,index2) ch = expression.substring(index,index+1).charAt(0); //判断ch是什么，做出相应的处理 if (operStack.isOper(ch)){ //如果是运算符 //判断当前的符号栈是否为空 if (!operStack.isEmpty()){ //如果符号栈有操作符，就需要比大小 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); } }else { //如果是数，直接入数栈 //numStack.push(ch-48); //这里我们得到的是字符，所以要-48 //1.当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数 //2.在处理数是，需要想expression的表达式的index后，在看一位，如果是数，就继续扫描，如果是符号就入栈 //3.因此我们需要定义一个字符串变量，用于拼接 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))){ //如果后一位是运算符，则入栈 keepNum="1"或者"123" numStack.push(Integer.parseInt(keepNum)); //重要的！！！！keepNum需要清空 keepNum = ""; } } } //让index+1，并判断是否扫描到最后 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); //入栈 } System.out.println("结果为"+numStack.pop()); } }