stack:
1.top and bottom.统一在top端增加和删除。
Attention:
函数 delete(x) 是将top端的元素删除并且赋值给x
实现：通过linked list实现 。
public class StackLi { public StackLi( ){ topOfStack = null; } public boolean isFull( ){ return false; } public boolean isEmpty( ){ return topOfStack = = null; } public void makeEmpty( ){ topOfStack = null; } public void push( object x ) public object top( ) public void pop( ) throws Underflow public object topAndPop( ) private ListNode topOfStack; }
通过数组实现。
主要的应用：用于进行括号的匹配 尝试编程中因为之前没有怎么用过stack
主要用到的几个方法： add(x),pop(),firstelement()
public void testMatch(String expression){ matchstack=new Stack<Integer>(); int len=expression.length(); for(int i=0;i<len;i++){ char getCh=expression.charAt(i); if(getCh==‘(‘){ matchstack.add(i); }else if(getCh==‘)‘){ try{ matchstack.pop(); }catch(Exception e){ System.out.println(i+"missing 左括号"); } } } while(!matchstack.isEmpty()){ System.out.println(matchstack.firstElement()+"missing 右括号"); matchstack.pop(); } }
表达式：infix expression中缀表达式，也就是我们正常意义上理解的。
posfix expression 后缀表达式 prefix expression 前缀表达式
后缀表达式---->中缀表达式
具体的算法见表达式转换随笔。。
原文：http://www.cnblogs.com/bounceFront/p/5514714.html