一)栈的定义
堆栈(Stack)可以看成是一种“特殊的”线性表,这种线性表上的插入和删除运算限定在表的某一端进行的。
- 通常称插入、删除的这一端为栈顶(Top),另一端称为栈底(Bottom)。
- 当表中没有元素时称为空栈。
- 栈为后进先出(Last In First Out)的线性表,简称为LIFO表。
- 栈的修改是按后进先出的原则进行。每次删除(退栈)的总是当前栈中"最新"的元素,即最后插入(进栈)的元素,而最先插入的是被放在栈的底部,要到最后才能删除。
二)栈的基本操作
获取栈的状态(栈空、栈满、栈大小)、出栈、入栈。
三)java中的栈
java中的类Stack实现了栈的功能。其类结构如下图
Vector是ArrayList的Synchronized实现,Stack继承了Vector,因此Stack是基于数组的顺序栈。
主要方法:push、pop、peek
public E push(E item) { addElement(item); return item; } public synchronized E pop() { E obj; int len = size(); obj = peek(); removeElementAt(len - 1); return obj; } public synchronized E peek() { int len = size(); if (len == 0) throw new EmptyStackException(); return elementAt(len - 1); }
四)栈的应用
4.1)表达式的计算
这里有两个知识点:后缀表达式(逆波兰算法)、后缀表达式求值
后缀表达式:不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则,如:(2 + 1) * 3 , 即2 1 + 3 *)。其优点就是不用再考虑运算符的优先级。
将中缀表达式转换成后缀表达式,其算法如下:(算法为转载,出处不明!)
private List<String> infixExpToPostExp(String exp) {// 将中缀表达式转化成为后缀表达式 List<String> postExp = new ArrayList<String>();// 存放转化的后缀表达式的链表 StringBuffer numBuffer = new StringBuffer();// 用来保存一个数的 Stack<Character> opStack = new Stack<Character>();// 操作符栈 char ch, preChar; opStack.push('#'); try { for (int i = 0; i < exp.length();) { ch = exp.charAt(i); switch (ch) { case '+': case '-': case '*': case '/': preChar = opStack.peek(); // 如果栈里面的操作符优先级比当前的大,则把栈中优先级大的都添加到后缀表达式列表中 while (priority(preChar) >= priority(ch)) { postExp.add("" + preChar); opStack.pop(); preChar = opStack.peek(); } opStack.push(ch); i++; break; case '(': // 左括号直接压栈 opStack.push(ch); i++; break; case ')': // 右括号则直接把栈中左括号前面的弹出,并加入后缀表达式链表中 char c = opStack.pop(); while (c != '(') { postExp.add("" + c); c = opStack.pop(); // 'c'是'('时不要添加到输出字符串中了 } i++; break; // #号,代表表达式结束,可以直接把操作符栈中剩余的操作符全部弹出,并加入后缀表达式链表中 case '#': char c1; while (!opStack.isEmpty()) { c1 = opStack.pop(); if (c1 != '#') postExp.add("" + c1); } i++; break; // 过滤空白符 case ' ': case '\t': i++; break; // 数字则凑成一个整数,加入后缀表达式链表中 default: if (Character.isDigit(ch)) { while (Character.isDigit(ch)) { numBuffer.append(ch); ch = exp.charAt(++i); } postExp.add(numBuffer.toString()); numBuffer = new StringBuffer(); } else { throw new IllegalExpressionException("illegal operator"); } } } } catch (RuntimeException e) { throw new IllegalExpressionException(e.getMessage()); } return postExp; }
转成后缀表达式,求值就很容易了,遇到运算符就“弹出”两个运算量进行计算,将计算结果“压入”运算量栈,以此类推直至运算符栈为空。
其算法如下:
private double doEval(List<String> list) { Stack<String> stack = new Stack<String>(); String element; double n1, n2, result; try { for (int i = 0; i < list.size(); i++) { element = list.get(i); if (isOperator(element)) { n1 = Double.parseDouble(stack.pop()); n2 = Double.parseDouble(stack.pop()); result = doOperate(n2, n1, element); stack.push(new Double(result).toString()); } else { stack.push(element); } } return Double.parseDouble(stack.pop()); } catch (RuntimeException e) { throw new IllegalExpressionException(e.getMessage()); } }
4.2)子程序嵌套调用
4.3)递归
递归方法思路:
第一步骤(递归步骤):将规模较大的原问题分解为一个或多个规模更小、但具有类似于原问题特性的子问题。即较大的问题递归地用较小的子问题来描述,解原问题的方法同样可用来解这些子问题。
第二步骤:确定一个或多个无须分解、可直接求解的最小子问题(称为递归的终止条件)。
简单理解就是大问题化小问题,小问题有解。