数据结构-栈
栈
定义
限制插入和删除只能在表的末端进行操作，也就是栈顶进行操作。符合先进后出的特点。Java中栈的实现是 通过数组。
例如：把1,2,3,4插入栈中，则存储结构如下:
栈的简单应用-计算器
代码如下:
import java.util.Stack;/** * 实现带括号的四则运算 */public class CalculatorUtil { public static void main(String[] args) { System.out.println(CalculatorUtil.Calculator("1 2*3.0 (1 1*3) 5")); } public static double Calculator(String expression){ char[] chars = expression.toCharArray(); //存储计算结果 Stack<Double> result=new Stack<>(); //存储操作 Stack<Character> oper=new Stack<>(); //临时存储数值 StringBuilder num=new StringBuilder(); for(int i=0;i<chars.length;i ){ if(chars[i]==' ' || chars[i]=='-' || chars[i]=='*' || chars[i]=='/' ){ //数值存入结果栈，并先进行乘除操作 if(!oper.isEmpty() && (oper.peek()=='*' || oper.peek()=='/')){ dealSum(oper.pop(),result,result.pop(),Double.parseDouble(num.toString())); }else { result.push(Double.parseDouble(num.toString())); } //清空临时数值 num.setLength(0); oper.push(chars[i]); }else if(chars[i]=='('){ //存储左括号 oper.push(chars[i]); }else if(chars[i]==')'){ char operLast; //一致进行出栈操作直到遇到左括号 while ((operLast=oper.pop())!='('){ dealSum(operLast,result,result.pop(),result.pop()); } }else { //拼接数值 num.append(chars[i]); } } if(num.length()>0){ result.push(Double.parseDouble(num.toString())); } //将剩余的操作出栈 while (!oper.isEmpty()){ dealSum(oper.pop(),result,result.pop(),result.pop()); } return result.peek(); } private static void dealSum(char oper,Stack<Double> result,double numFirst,double numSecond){ switch (oper){ case ' ': result.push(numFirst numSecond); break; case '-': result.push(numFirst-numSecond); break; case '*': result.push(numFirst*numSecond); break; case '/': result.push(numFirst/numSecond); break; } }}例如: 1 2.0*3 (1 1*3) 5
把输入的字符串转为字符数组，我们通过两个栈进行操作，result存储计算结果，operate存储操作。
第1轮操作
result: [1]
operate:[]
第2轮操作
result: [1]
operate:[ ]
第3轮操作
result: [1,2.0]
operate:[ ]
第4轮操作
result: [1,2.0]
operate:[ ,*]
第5轮操作
result: [1,6.0]
operate:[ ]
第6轮操作
result: [1,6.0]
operate:[ , ]
第7轮操作
result: [1,6.0]
operate:[ , ,(]
第8轮操作
result: [1,6.0,1]
operate:[ , ,(, ]
第9轮操作
result: [1,6.0,1,1]
operate:[ , ,(, ]
第10轮操作
result: [1,6.0,1,1]
operate:[ , ,(, ,*]
第11轮操作
result: [1,6.0,1,1,3]
operate:[ , ,(, ,*]
第12轮操作
result: [1,6.0,4]
operate:[ , ]
第13轮操作
result: [1,6.0,4]
operate:[ , , ]
第14轮操作
result: [1,6.0,4,5]
operate:[ , , ]
第15轮操作
result: [1,6.0,9]
operate:[ , ]
第16轮操作
result: [1,15.0]
operate:[ ]
第17轮操作
result: [16.0]
operate:[]