java数据结构中栈怎么应用

魁首哥

作者

java数据结构中栈怎么应用

本篇内容主要讲解“java数据结构中栈怎么应用”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“java数据结构中栈怎么应用”吧!

1.声明一个栈接口SStack

packagech05;publicinterfaceSStack<T>{booleanisEmpty();//判断栈是否为空voidpush(Tx);//元素x入栈Tpop();//出栈，返回栈顶元素Tpeek();//返回栈顶元素，但不出栈}

2.定义顺序栈类SeqStack<T>，包括数据元素的对象数组和栈顶元素下标两个私有成员变量，构造方法可实例化容量为size大小的空顺序栈，调用类中成员方法实现顺序栈的入栈、出栈、获取栈顶元素等操作，重写toString()方法获取顺序栈的字符串描述。

packagech05;publicclassSeqStack<T>implementsSStack<T>{Object[]element;inttop;//构造方法，创建一个空栈，存储容量大小sizepublicSeqStack(intsize){element=newObject[size];top=-1;}//判断栈是否为空@OverridepublicbooleanisEmpty(){returntop==-1;}//元素x入栈@Overridepublicvoidpush(Tx){if(x==null){return;}//若栈满，则扩充栈容量if(this.top==element.length-1){Object[]temp=this.element;element=newObject[temp.length*2];for(inti=0;i<temp.length;i++){element[i]=temp[i];}}//入栈this.element[++top]=x;}//出栈，返回栈顶元素@OverridepublicTpop(){if(top!=-1){return(T)this.element[this.top--];}returnnull;}//返回栈顶元素，但不出栈@OverridepublicTpeek(){if(top!=-1){return(T)this.element[this.top];}returnnull;}//返回顺序栈中所有元素的描述字符串，形式为"（,）"，覆盖Object类的toString()方法publicStringtoString(){//自栈顶输出到栈底Stringstr="";if(top>=0){str="(";for(inti=top;i>=0;i--){str+=element[i]+",";}str=str.substring(0,str.length()-1);str+=")";}else{//空栈str="()";}returnstr;}}

3.定义结点类Node<T>，包括数据域和地址域两个成员变量，构造方法实例化结点，重写toString()方法获取结点的字符串描述。

packagech05;publicclassNode<T>{publicTdata;publicNode<T>next;publicNode(Tdata,Node<T>next){this.data=data;this.next=next;}publicNode(){this(null,null);}}

4.定义链式栈类LinkedStack<T>：

packagech05;publicclassLinkedStack<T>implementsSStack<T>{privateNode<T>top;publicLinkedStack(){top=newNode<>();}@OverridepublicbooleanisEmpty(){returntop.next==null?true:false;}@Overridepublicvoidpush(Tx){if(x==null){return;}//生成新结点Node<T>q=newNode<>(x,null);q.next=top.next;top.next=q;}@OverridepublicTpop(){Telem=null;if(top.next!=null){elem=top.next.data;top.next=top.next.next;}returnelem;}@OverridepublicTpeek(){Telem=null;if(top.next!=null){elem=top.next.data;}returnelem;}//返回顺序栈中所有元素的描述字符串，形式为"（,）"，覆盖Object类的toString()方法publicStringtoString(){Stringstr="";Node<T>p=top.next;if(p!=null){str="(";while(p!=null){str+=p.data+",";p=p.next;}str=str.substring(0,str.length()-1);str+=")";}else{str="()";}returnstr;}}

5.括号匹配

packagech07;importjava.util.Scanner;publicclassBracket{//括号匹配publicstaticStringisMatched(Stringinfix){SeqStack<Character>stack=newSeqStack<Character>(infix.length());for(inti=0;i<infix.length();i++){charch=infix.charAt(i);switch(ch){case'(':stack.push(ch);break;case')':if(stack.isEmpty()||!stack.pop().equals('(')){return"expect(";}}}returnstack.isEmpty()?"":"expect)";}//测试括号匹配算法publicstaticvoidmain(String[]args){//括号匹配Scannerr=newScanner(System.in);System.out.print("输入括号表达式：");Stringinfix=r.nextLine();System.out.println(isMatched(infix));}}

6.表达式求值（后缀表达式）：

packagech05;importjava.util.Scanner;publicclassExpressionPoland{//括号匹配publicstaticStringisMatched(Stringinfix){SeqStack<Character>stack=newSeqStack<Character>(infix.length());for(inti=0;i<infix.length();i++){charch=infix.charAt(i);switch(ch){case'(':stack.push(ch);break;case')':if(stack.isEmpty()||!stack.pop().equals('(')){return"expect(";}}}returnstack.isEmpty()?"":"expect)";}//将中缀表达式转换为后缀表达式publicstaticStringBuffertoPostfix(Stringinfix){SeqStack<Character>stack=newSeqStack<Character>(infix.length());StringBufferpostfix=newStringBuffer(infix.length()*2);inti=0;System.out.println("\n求后缀表达式过程：");System.out.println("字符"+"\tstack\t\tpostfix");while(i<infix.length()){//对表达式中的每个字符进行处理charch=infix.charAt(i);//第i个字符System.out.print(ch+"\t");//输出第i个字符switch(ch){//判断字符类别//+、-运算符case'+':case'-'://当栈不空且栈顶运算符优先级高时，包括+、-、*、/while(!stack.isEmpty()&&!stack.peek().equals('(')){//栈中的'('优先级最低postfix.append(stack.pop()+"");//将出栈的运算符追加到后缀表达式中（空格间隔）}stack.push(ch);//第i个字符入栈i++;break;case'*':case'/'://当栈不空且栈顶运算符优先级高时，包括*、/while(!stack.isEmpty()&&(stack.peek().equals('*')||stack.peek().equals('/'))){postfix.append(stack.pop()+"");//将出栈的运算符追加到后缀表达式中（空格间隔）}stack.push(ch);//第i个字符入栈i++;break;case'(':stack.push(ch);//'('入栈i++;break;case')':Characterout=stack.pop();while(out!=null&&!out.equals('(')){//若干运算符出栈，直到'('出栈postfix.append(out+"");//将出栈的运算符追加到后缀表达式中（空格间隔）out=stack.pop();}i++;break;default:while(i<infix.length()&&ch>='0'&&ch<='9'){//获取运算的整数postfix.append(ch);//将数字追加到后缀表达式中i++;if(i<infix.length()){ch=infix.charAt(i);//下一位字符}}postfix.append("");//运算数以空格间隔}System.out.printf("%-18s",stack.toString());//输出每个运算符或运算数处理后栈中的内容System.out.println(postfix);//输出每个运算符或运算数处理后的后缀表达式}while(!stack.isEmpty()){//栈中运算符全部出栈postfix.append(stack.pop());}returnpostfix;}//计算后缀表达式的值publicstaticinttoValue(StringBufferpostfix){LinkedStack<Integer>stack=newLinkedStack<Integer>();intvalue=0;System.out.println("\n计算过程：");for(inti=0;i<postfix.length();i++){charch=postfix.charAt(i);if(ch>='0'&&ch<='9'){Strings="";while(ch!=''){//求运算数s+=ch;i++;ch=postfix.charAt(i);}stack.push(Integer.parseInt(s));//将运算数入栈}else{if(ch!=''){inty=stack.pop();//第二个运算数intx=stack.pop();//第一个运算数switch(ch){case'+':value=x+y;break;case'-':value=x-y;break;case'*':value=x*y;break;case'/':value=x/y;break;}//switch//输出计算表达式if(y>=0){System.out.println(x+(ch+"")+y+"="+value);}else{System.out.println(x+(ch+"")+"("+y+")"+"="+value);}//计算结果入栈stack.push(value);}}}returnstack.pop();//返回栈中计算的最终结果}//测试表达式求值算法publicstaticvoidmain(String[]args){Scannerr=newScanner(System.in);//表达式求值System.out.print("输入表达式：");Stringinfix=r.nextLine();Stringmatch=isMatched(infix);if(match.equals("")){//括号匹配StringBufferpostfix=toPostfix(infix);System.out.println("\n后缀表达式:"+postfix);System.out.println("\n计算结果："+toValue(postfix));}else{//括号不匹配System.out.println("表达式错误："+match);}}}

运行结果如下：