java 数据结构中栈结构应用的两个实例
java数据结构中栈结构应用的两个实例
1、单词逆序。
要求从控制台读入一串字符,按回车结束输入,同时显示其逆序字符串。
对于颠倒顺序的操作,用栈来解决是很方便的。具体思想是把字符串中的每一个字符按顺序存入栈中,然后再一个一个的从栈中取出。这时就是按照逆序取出的字符串。
//reverse.java //stackusedtoreverseastring //torunthisprogram:C>javaReverseApp importjava.io.*;//forI/O //////////////////////////////////////////////////////////////// classStackX//定义了栈的基本结构和操作 { privateintmaxSize;//栈最大值 privatechar[]stackArray;//栈内用数组存储数据 privateinttop;//当前栈顶标号,从0开始 //-------------------------------------------------------------- publicStackX(intmax)//constructor { maxSize=max; stackArray=newchar[maxSize]; top=-1; } //-------------------------------------------------------------- publicvoidpush(charj)//putitemontopofstack { stackArray[++top]=j; } //-------------------------------------------------------------- publiccharpop()//takeitemfromtopofstack { returnstackArray[top--]; } //-------------------------------------------------------------- publiccharpeek()//peekattopofstack { returnstackArray[top]; } //-------------------------------------------------------------- publicbooleanisEmpty()//trueifstackisempty { return(top==-1); } //-------------------------------------------------------------- }//endclassStackX //////////////////////////////////////////////////////////////// classReverser//封装了单词逆序的操作 { privateStringinput;//inputstring privateStringoutput;//outputstring //-------------------------------------------------------------- publicReverser(Stringin)//constructor {input=in;} //-------------------------------------------------------------- publicStringdoRev()//reversethestring { intstackSize=input.length();//getmaxstacksize StackXtheStack=newStackX(stackSize);//makestack for(intj=0;j2.分隔符匹配
有些分割符在编程中一定是成对出现的,例如(),{},和[]等。如果发现有未匹配的分隔符,编译器会报错。因为匹配操作采取就近原则,后输入的分割符优先匹配,具有“后进先出”的特点。这个匹配操作可以用栈来实现。
具体操作是在输入过程中,如果遇到左匹配符,则将左匹配符压入栈中。如果遇到右匹配符,则从栈中取出一个数据,分析其与右匹配符是否相匹配。若匹配,则继续进行,若不匹配,则报错终止。
//brackets.java //stacksusedtocheckmatchingbrackets //torunthisprogram:C>javabracketsApp importjava.io.*;//forI/O //////////////////////////////////////////////////////////////// classStackX { privateintmaxSize; privatechar[]stackArray; privateinttop; //-------------------------------------------------------------- publicStackX(ints)//constructor { maxSize=s; stackArray=newchar[maxSize]; top=-1; } //-------------------------------------------------------------- publicvoidpush(charj)//putitemontopofstack { stackArray[++top]=j; } //-------------------------------------------------------------- publiccharpop()//takeitemfromtopofstack { returnstackArray[top--]; } //-------------------------------------------------------------- publiccharpeek()//peekattopofstack { returnstackArray[top]; } //-------------------------------------------------------------- publicbooleanisEmpty()//trueifstackisempty { return(top==-1); } //-------------------------------------------------------------- }//endclassStackX //////////////////////////////////////////////////////////////// classBracketChecker { privateStringinput;//inputstring //-------------------------------------------------------------- publicBracketChecker(Stringin)//constructor {input=in;} //-------------------------------------------------------------- publicvoidcheck() { intstackSize=input.length();//getmaxstacksize StackXtheStack=newStackX(stackSize);//makestack for(intj=0;j感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!