java 实现 stack详解及实例代码
栈是限制插入和删除只能在一个位置上进行的List，该位置是List的末端，叫做栈的顶(top)，对于栈的基本操作有push和pop，前者是插入，后者是删除。
栈也是FIFO表。
栈的实现有两种，一种是使用数组，一种是使用链表。
publicclassMyArrayStack<E>{
privateArrayList<E>list=newArrayList<>();
publicvoidpush(Ee){
list.add(e);
}
publicEpop(){
returnlist.remove(list.size()-1);
}
publicEpeek(){
returnlist.get(list.size()-1);
}
publicbooleanisEmpty(){
returnlist.size()==0;
}
}
publicclassMyLinkStack<E>{
LinkedList<E>list=newLinkedList<>();
publicvoidpush(Ee){
list.addLast(e);
}
publicEpop(){
returnlist.removeLast();
}
publicEpeek(){
returnlist.getLast();
}
publicbooleanisEmpty(){
returnlist.size()==0;
}
}
栈的应用
平衡符号
给定一串代码，我们检查这段代码当中的括号是否符合语法。
例如：[{()}]这样是合法的，但是[{]}()就是不合法的。
如下是测试代码：
publicclassBalanceSymbol{
publicbooleanisBalance(Stringstring){
MyArrayStack<Character>stack=newMyArrayStack<>();
char[]array=string.toCharArray();
for(charch:array){
if("{[(".indexOf(ch)>=0){
stack.push(ch);
}elseif("}])".indexOf(ch)>=0){
if(isMatching(stack.peek(),ch)){
stack.pop();
}
}
}
returnstack.isEmpty();
}
privatebooleanisMatching(charpeek,charch){
if((peek=='{'&&ch=='}')||(peek=='['&&ch==']')||(peek=='('&&ch==')')){
returntrue;
}
returnfalse;
}
publicstaticvoidmain(String[]args){
BalanceSymbolsymbol=newBalanceSymbol();
Stringstring="publicstaticvoidmain(String[]args){BalanceSymbolsymbol=newBalanceSymbol();}";
Stringstring2="publicstaticvoidmain(String[]args){BalanceSymbolsymbol=newBalanceSymbol([);}]";
System.out.println(symbol.isBalance(string));
System.out.println(symbol.isBalance(string2));
}
}
后缀表达式
例如一个如下输入，算出相应的结果，
3+2+3*2=?
这个在计算顺序上不同会产生不同的结果，如果从左到右计算结果是16，如果按照数学优先级计算结果是11。
如果把上述的中缀表达式转换成后缀表达式：
32+32*+
如果使用后缀表达式来计算这个表达式的值就会非常简单，只需要使用一个栈。
每当遇到数字的时候，把数字入栈。
每当遇到操作符，弹出2个元素根据操作符计算后，入栈。
最终弹出栈的唯一元素就是计算结果。
/**
*简化版本，每个操作数只一位，并且假设字符串合法
*/
publicclassPostfixExpression{
publicstaticintcalculate(Stringstring){
MyArrayStack<String>stack=newMyArrayStack<>();
char[]arr=string.toCharArray();
for(charch:arr){
if("0123456789".indexOf(ch)>=0){
stack.push(ch+"");
}elseif("+-*/".indexOf(ch)>=0){
inta=Integer.parseInt(stack.pop());
intb=Integer.parseInt(stack.pop());
if(ch=='+'){
stack.push((a+b)+"");
}elseif(ch=='-'){
stack.push((a-b)+"");
}elseif(ch=='*'){
stack.push((a*b)+"");
}elseif(ch=='/'){
stack.push((a/b)+"");
}
}
}
returnInteger.parseInt(stack.peek());
}
publicstaticvoidmain(String[]args){
System.out.println(calculate("32+32*+"));
}
}
中缀表达式转换成后缀表达式
假设只运行+，-，*，/，()这几种表达式。并且表达式合法。
a+b*c-(d*e+f)/g转换后的后缀表达式如下：
abc*+de*f+g/-
使用栈中缀转后缀步骤如下：
- 当读到操作数立即把它输出
- 如果遇到操作符入栈，如果遇到的左括号也放到栈中
- 如果遇到右括号，就开始弹出栈元素，直到遇到对应的左括号，左括号只弹出不输出。
- 如果遇到其他符号，那么从栈中弹出栈元素知道发现优先级更低的元素为止。
importjava.util.HashMap;
importjava.util.Map;
publicclassExpressionSwitch{
privatestaticMap<Character,Integer>map=newHashMap<Character,Integer>();
static{
map.put('+',0);
map.put('-',1);
map.put('*',2);
map.put('/',3);
map.put('(',4);
}
privatestaticchar[][]priority={
//当前操作符
//+-*/(
/*栈+*/{'>','>','<','<','<'},
/*顶-*/{'>','>','<','<','<'},
/*操**/{'>','>','>','>','<'},
/*作/*/{'>','>','>','>','<'},
/*符(*/{'<','<','<','<','<'},
};
publicstaticStringswitch1(Stringstring){
StringBuilderbuilder=newStringBuilder();
char[]arr=string.toCharArray();
MyArrayStack<Character>stack=newMyArrayStack<>();
for(charch:arr){
if("0123456789abcdefghijklmnopqrstuvwxyz".indexOf(ch)>=0){
builder.append(ch);
}elseif('('==ch){
stack.push(ch);
}elseif(')'==ch){
while(true&&!stack.isEmpty()){
chartmp=stack.pop();
if(tmp=='('){
break;
}else{
builder.append(tmp);
}
}
}else{
while(true){
if(stack.isEmpty()){
stack.push(ch);
break;
}
chartmp=stack.peek();
if(isPriorityHigh(tmp,ch)){
builder.append(stack.pop());
}else{
stack.push(ch);
break;
}
}
}
}
while(!stack.isEmpty()){
builder.append(stack.pop());
}
returnbuilder.toString();
}
privatestaticbooleanisPriorityHigh(chartmp,charch){
returnpriority[map.get(tmp)][map.get(ch)]=='>';
}
publicstaticvoidmain(String[]args){
System.out.println(switch1("a+b*c-(d*e+f)/g"));
}
}
通过此文，希望大家对Javastack的知识掌握，谢谢大家对本站的支持！