数据结构教程（Java语言描述）（第2版 微课视频版） 课件 第3章 栈和队列

第3章栈和队列3.1栈3.2队列CONTENTS提纲1/1023.1栈链栈栈的综合应用顺序栈栈的定义Java中的栈容器Stack<E>2/102栈（stack）是一种只能在同一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶（top），表的另一端称为栈底（bottom）。栈的插入操作通常称为进栈或入栈（push），栈的删除操作通常称为退栈或出栈（pop）。a0

a1

…

an-1栈底栈顶进栈出栈3.1.1栈的定义3/1024/102后进先出，即后进栈的元素先出栈。栈也称为后进先出表。栈的主要特点：5/102栈抽象数据类型=线性结构+栈的基本运算ADTStack{

数据对象：

D={ai|0≤i≤n-1，n≥0，元素ai为E类型}

数据关系：

R={r} r={<ai，ai+1>|ai，ai+1∈D，i=0，…，n-2}

基本运算： booleanempty()：判断栈是否为空，若空栈返回真；否则返回假。 voidPush(Ee)：进栈操作，将元素e插入到栈中作为栈顶元素。 Epop()：出栈操作，返回栈顶元素。 Epeek()：取栈顶操作，返回当前的栈顶元素。}6/102栈元素基本运算应用程序7/102一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（）。A.edcba B.decba

C.dceab D.abcde示例方法2：利用判断准则方法1：用栈模拟进行判断判断准则：若输入序列为1，2，…，n，给定的（p1，p2，…，pn）是1，2，…，n的一种排列，则利用一个栈得到输出序列（p1，p2，…，pn）的充分必要条件是不存在这样的i、j、k满足i<j<k的同时也满足pj<pk<pi。dceab违反了!pipjpk8/1021～n共产生n+11C2nn种合法出栈序列。例如，n=545321合法31254不合法14235不合法9/102已知一个栈的进栈序列是1，2，3，…，n，其输出序列是p1，p2，…，pn，若p1=n，则pi的值为（）。A.i B.n-i

C.n-i+1 D.不确定示例1，2，3，…，nn，…输出序列唯一p1=np2=n-1p3=n-2…pn=1pi+i=n+1即pi=n-i+110/1022013年全国硕士研究生入学统一考试题示例2.一个栈的入栈序列为1，2，3，

…，n

，其出栈序列是p1，p2，p3，…，pn。若p2=3，则p3可能取值的个数是（）。A.n-3B.n-2C.n-1D.无法确定…栈1p13p22p3n,…,41进，1出，2进，3进，3出，2出，…2p13p21p3或者1进，2进，2出，3进，3出，1出，…2p13p24p3或者1进，2进，2出，3进，3出，4进，4出，…

，1出p3除了3外都可能！11/102栈的实现方式线性表顺序表链表栈顺序栈链栈逻辑结构存储结构映射∩3.1.2栈的顺序存储结构及其基本运算算法实现12/10243210（a）空栈-1topa（b）元素a进栈43210-1topdcba（c）元素b、c、d进栈43210-1topcba（d）元素d出栈43210-1top顺序栈栈中元素个数=top+113/10243210（a）空栈-1topa（b）元素a进栈43210-1topdcba（c）元素b、c、d进栈43210-1topcba（d）元素d出栈43210-1top初始时置栈顶指针top=-1，顺序栈的四要素如下：栈空的条件为top==-1。栈满（栈上溢出）的条件为top==capacity-1，这里采用动态扩展容量的方式，即满时将data数组的容量扩大两倍。元素e进栈操作是先将栈顶指针top增1，然后将元素e放在栈顶指针处。出栈操作是先将栈顶指针top处的元素取出，然后将栈顶指针减1。顺序栈14/102publicclassSqStackClass<E> { //顺序栈泛型类finalintinitcapacity=10; //顺序栈的初始容量(常量)privateintcapacity; //存放顺序栈的容量privateE[]data; //存放顺序栈中元素privateinttop; //存放栈顶指针publicSqStackClass(){

//构造方法，实现data和size初始化data=(E[])newObject[initcapacity];//强制转换为E类型数组capacity=initcapacity;

top=-1;}privatevoidupdatecapacity(intnewcapacity){ //改变栈容量E[]newdata=(E[])newObject[newcapacity]; //newcapacity≥top+1for(inti=0;i<=top;i++) //复制原来的元素newdata[i]=data[i];capacity=newcapacity; //设置新容量data=newdata; //仍由data标识数组}

//栈的基本运算算法}顺序栈泛型类SqStackClass<E>15/102顺序栈的基本运算算法（1）判断栈是否为空empty()publicbooleanempty(){ //判断栈是否为空returntop==-1;}43210-1top16/102（2）进栈push(e)publicvoidpush(Ee){ //元素e进栈if(top==capacity-1) //顺序栈空间满时倍增容量updatecapacity(2*(top+1));top++; //栈顶指针增1data[top]=e;}17/102（3）出栈pop()publicEpop() {} //出栈操作if(empty())thrownewIllegalArgumentException("栈空");Ee=(E)data[top];top--;if(top+1>initcapacity&&top+1==capacity/4)//满足条件容量减半updatecapacity(capacity/2);returne;}18/102（4）取栈顶元素peek()publicEpeek(){} //取栈顶元素操作if(empty())thrownewIllegalArgumentException("栈空");return(E)data[top];}19/102?顺序栈的几个问题问题1：若采用数组data[1..m]存放栈元素，回答以下问题：（1）只能以data[1]端作为栈底吗？（2）为什么不能以data数组的中间位置作为栈底？

（1）也可以将data[m]端作为栈底。

（2）栈中元素是从栈底向栈顶方向生长的，如果以data数组的中间位置作为栈底，那么栈顶方向的另外一端空间就不能使用，造成空间浪费，所以不能以data数组的中间位置作为栈底。←栈元素1……m20/102

若一个栈用数组data[1..n]存储，初始栈顶指针top为n+1，则以下元素x进栈的正确操作是（）。A.top++;data[top]=x; B.data[top]=x;top++;

C.top--;data[top]=x; D.data[top]=x;top--;

初始栈顶指针top为n+1，说明data[n]端作为栈底，在进栈时top应递减，由于不存在data[n+1]的元素，所以在进栈时应先将top递减，再将x放在top处（top指向栈顶元素）。答案为C。问题2：←栈元素1……ntop21/102

若一个栈用数组data[1..n]存储，初始栈顶指针top为n+1，则以下元素x出栈的正确操作是（）。

A.x=data[top];top++; B.top++;x=data[top];C.x=data[top];top--; D.top--;x=data[top];

进栈操作是：top--;data[top]=x（top指向栈顶元素）;出栈操作与进栈操作相反，应该为x=data[top];top++;。题答案为A。ai

……1……ntop22/102

若一个栈用数组data[1..n]存储，初始栈顶指针top为1，则以下元素x进栈的正确操作是（）。A.top++;data[top]=x; B.data[top]=x;top++;C.top--;data[top]=x; D.data[top]=x;top--;

初始栈顶指针top为1，说明data[1]端作为栈底，在进栈时top应递增，由于存在data[1]的元素，所以在进栈时应先将x放在top处，

再top递增（top指向栈顶元素的前一个位置！）。答案为B。栈元素→1……ntop23/102

若一个栈用数组data[1..n]存储，初始栈顶指针top为1，则以下元素x出栈的正确操作是（）。A.x=data[top];top++; B.top++;x=data[top];C.x=data[top];top--; D.top--;x=data[top];

进栈操作是：B.data[top]=x;top++;（top指向栈顶元素的前一个位置）。出栈操作与进栈操作相反，应该为top--;x=data[top]。题答案为D。……ai1……ntop24/1023.1.3顺序栈的应用算法设计示例

【例3.4】设计一个算法利用顺序栈检查用户输入的表达式中括号是否配对（假设表达式中可能含有圆括号、中括号和大括号）。并用相关数据进行测试。25/102publicclassExam3_4{}publicstaticbooleanisMatch(Stringstr){//判断算法inti=0;chare,x;SqStackClass<Character>st=newSqStackClass<Character>();

//建立一个顺序栈while(i<str.length()){e=str.charAt(i);if(e=='('||e=='['||e=='{')

st.push(e);

//将左括号进栈26/102else{if(e==')'){if(st.empty())returnfalse; //栈空返回falseif(st.peek()!='(')returnfalse;//栈顶不匹配返回假st.pop();}elseif(e==']'){if(st.empty())returnfalse; //栈空返回falseif(st.peek()!='[')returnfalse;//栈顶不匹配返回假

st.pop();}elseif(e=='}'){if(st.empty())returnfalse; //栈空返回falseif(st.peek()!='{')returnfalse;//栈顶不匹配返回假st.pop();}}i++; //继续遍历str}if(st.empty())returntrue; //栈空返回trueelsereturnfalse; //栈不空返回false}27/102publicstaticvoidmain(String[]args){System.out.println("测试1");Stringstr="([)]";if(isMatch(str))System.out.println(str+"中括号是匹配的");elseSystem.out.println(str+"中括号不匹配");System.out.println("测试2");str="([])";if(isMatch(str)) System.out.println(str+"中括号是匹配的");else System.out.println(str+"中括号不匹配");}}测试1([)]中括号不匹配测试2([])中括号是匹配的28/102

【例3.6】有1～n的n个元素，通过一个栈可以产生多种出栈序列，设计一个算法判断序列b是否得为一个合适的出栈序列，并给出操作过程。要求用相关数据进行测试。例如，n=512345，12354是合适的出栈序列。51234，45123不是合适的出栈序列。29/102用栈模拟。将进栈序列1～n存放到数组a中。判断a序列通过一个栈算是否得到出栈序列b。令i、j分别遍历a、b数组（初始值均为0），反复执行以下操作直到a或者b数组遍历完：

（1）若栈空，a[i]进栈，i++。

（2）若栈不空，如果栈顶元素≠b[j]，将a[i]进栈，i++。

（3）否则，出栈一个元素，j++。简单地说就是当栈顶元素=b序列当前元素，出栈一次，否则将a序列的当前元素进栈。当该过程结束，再将栈中与b序列相同的元素依次出栈。如果b序列遍历完（j==n）说明b序列是合法的出栈序列，返回true，否则不是合法的出栈序列，返回false。30/102importjava.util.*;publicclassExam3_6{staticStringop="";publicstaticbooleanisSerial(int[]b){inti,j,n=b.length;Integere;int[]a=newint[n];

SqStackClass<Integer>st=newSqStackClass<Integer>();

for(i=0;i<n;i++)a[i]=i+1; //将1～n放入数组a中i=0;j=0;用字符串op记录所有的栈操作。31/102while(i<n&&j<n){ //a和b均没有遍历完if(st.empty()||(st.peek()!=b[j])){//栈空或者栈顶不是b[j]st.push(a[i]); //a[i]进栈op+="元素"+a[i]+"进栈\n";i++;}else{ //否则出栈e=st.pop();op+="元素"+e+"出栈\n"; j++;}}while(!st.empty()&&st.peek()==b[j]){//将栈中与b相同元素出栈e=st.pop();j++;}if(j==n)returntrue; //是出栈序列时返回trueelsereturnfalse; //不是出栈序列时返回false}32/102publicstaticvoidsolve(int[]b) { //求解算法for(inti=0;i<b.length;i++)System.out.print(""+b[i]);if(isSerial(b)){System.out.println("是合法的出栈序列");System.out.println(op);}elseSystem.out.println("不是合法的出栈序列");}33/102publicstaticvoidmain(String[]args){System.out.println("测试1");int[]b={1,3,2,4};solve(b);System.out.println("测试2");int[]c={4,3,1,2};solve(c);}}测试11324是合法的出栈序列

元素1进栈

元素1出栈

元素2进栈

元素3进栈

元素3出栈

元素2出栈

元素4进栈

元素4出栈测试24312不是合法的出栈序列34/102进一步简化判断过程i从1开始（因为进栈序列为1～n）、j遍历b数组（初始值为0），在i<=n时循环：

（1）将i进栈，i++。

（2）栈不空并且栈顶元素与b[j]相同时循环：出栈元素e，j++。

在上述过程结束后，如果栈空返回true，否则返回false。例如，n=5，输入序列为1～5，b序列为（3，2，1，5，4）142351～n（输入序列）处理完并且栈空

Yes35/102publicstaticbooleanisSerial1(int[]b){ //简化的算法inti,j,n=b.length;Integere;int[]a=newint[n];

SqStackClass<Integer>st=newSqStackClass<Integer>();

for(i=0;i<n;i++)a[i]=i+1; //将1～n放入数组a中i=0;j=0;while(i<n) { //a没有遍历完st.push(a[i]);op+="元素"+a[i]+"进栈\n";i++;

while(!st.empty()&&st.peek()==b[j]){e=st.pop(); //b[j]与栈顶匹配的情况op+="元素"+e+"出栈\n";j++;}}returnst.empty(); //栈空返回true;否则返回false}a序列栈stb序列36/102POJ1363—铁轨问题37/102

【例3.7】设有两个栈S1和S2，它们都采用顺序栈存储，并且共享一个固定容量的存储区s[0..M-1]，为了尽量利用空间，减少溢出的可能，请设计这两个栈的存储方式。共享栈问题38/102a1

a2

a3

…

an

……

bm

bm-1

…

b2

b1012…M-1栈1底栈1顶栈2顶栈2底栈顶指针top1栈顶指针top2s：栈S1空的条件是top1=-1。栈S1满的条件是top1=top2-1；元素e进栈S1（栈不满时）的操作是：top1++;s[top1]=e。元素e出栈S1（栈不空时）的操作是：e=s[top1];top1--。栈S2空的条件是top2=M。栈S2满的条件是top2=top1+1。元素e进栈S2（栈不满时）的操作是：top2--;s[top2]=e。元素e出栈S2（栈不空时）的操作是：e=s[top2];top2++。39/102

请设计包含Getmin()函数的栈。定义栈的数据结构，要求添加一个Getmin()函数，能够得到栈的最小元素。要求函数Getmin()、push以及pop的时间复杂度都是O(1)。栈基本运算Getmin()顺序栈的扩展40/102

设计顺序栈（data，top），其中data[]数组存放栈中元素，top为栈顶指针（初始值为-1）。为了求栈中最小元素的Getmin()函数的时间复杂度为O(1)，需要保存当前栈的最小元素，但仅仅一个最小元素是不够的。例如：push(5); //栈元素：（5）

最小元素：5push(6); //栈元素：（6，5）

最小元素：5push(3); //栈元素：（3，6，5）

最小元素：3push(7); //栈元素：（7，3，6，5）

最小元素：3pop(); //栈元素：（3，6，5）

最小元素：3pop(); //栈元素：（6，5）

最小元素：5参考答案41/102栈中元素：a1

a2…ai…an-1

an栈底栈顶元素mindata[i]保存a1～ai的最小元素的序号┊mindata[i]┊min栈栈底栈顶42/1027365data栈20min栈栈中元素：5637例012343/102由于可能有连续的进栈和出栈操作，所以仅仅保存一个最小元素会得不到正确的结果。设置一个辅助栈（mindata，mintop），它保存当前data栈中最小元素的下标。进栈操作：当栈空或者进栈元素x小于当前栈中最小元素时，将x的下标进min栈。退栈操作：若栈顶元素为最小元素，将其下标从min栈退栈，否则不从min栈退栈。设计思路44/102importjava.util.*;classStack{

//栈扩展finalintMaxSize=100;int[]data; //元素栈int[]mindata; //min栈inttop;intmintop;publicStack(){

//构造方法data=newint[MaxSize];mindata=newint[MaxSize];top=-1;mintop=-1;}publicbooleanempty(){

//判断栈空否returntop==-1;}45/102publicintpeek(){

//获取栈顶元素if(empty()) //栈空抛出异常

thrownewIllegalArgumentException("栈空");returndata[top]; //返回栈顶元素

}publicintGetmin(){

//获取栈中最小元素

if(empty()) //栈空抛出异常thrownewIllegalArgumentException("栈空");returndata[mindata[mintop]]; //返回栈中最小元素

}调用Getmin()不改变两个栈中元素！46/102publicvoidpush(intx){

//元素x进栈if(top==MaxSize-1) //栈满抛出异常thrownewIllegalArgumentException("栈满");;if(empty()||x<Getmin()){ //栈空或者x小于min栈顶元素

mintop++; //将x在栈中的下标进min栈

mindata[mintop]=top+1;}top++; //将x进栈

data[top]=x;}47/102publicintpop(){

//退栈并返回退栈元素

if(empty()) //栈空抛出异常

thrownewIllegalArgumentException("栈空");;intx=data[top];if(top==mindata[mintop]) //若栈顶元素为要出栈的最小元素

mintop--; //将其下标从min栈中退栈

top--;returnx;}}上述所有基本运算算法的时间复杂度均为O(1)，空间换时间！48/102publicclasstmp{publicstaticvoidmain(String[]args){Stackst=newStack();System.out.printf("\n元素5,6,3,7依次进栈\n");st.push(5);st.push(6);st.push(3);st.push(7);System.out.printf("求最小元素并出栈\n");while(!st.empty()){System.out.printf("最小元素:%d\n",st.Getmin());System.out.printf("出栈元素:%d\n",st.pop());}System.out.println();}}测试程序49/102能不能在min直接存放元素值？?不能！因为栈中元素可能重复出现1541栈底栈顶data栈1min栈pop()时data栈出栈元素1与min栈栈顶元素相同，若此时min栈也出栈，结果错误反例50/102但可以改为将多个当前最小的元素都进min栈！publicintGetmin(){

//获取栈中最小元素if(empty()) //栈空抛出异常thrownewIllegalArgumentException("栈空");returnmindata[mintop];

//返回栈中最小元素}publicvoidpush(intx){

//元素x进栈if(top==MaxSize-1) //栈满抛出异常thrownewIllegalArgumentException("栈满");;if(empty()||x<=Getmin()){ //栈空或者x小于min栈顶元素mintop++; //将x在栈中的下标进min栈

mindata[mintop]=x;}top++; //将x进栈data[top]=x;}51/102publicintpop(){

//退栈并返回退栈元素if(empty()) //栈空抛出异常thrownewIllegalArgumentException("栈空");;intx=data[top];if(x==mindata[mintop]) //若栈顶元素为要出栈的最小元素mintop--; //将其下标从min栈中退栈

top--;returnx;}min栈空间开销大一些！52/102栈的实现方式线性表顺序表链表栈顺序栈链栈逻辑结构存储结构映射∩3.1.4栈的链式存储结构及其基本运算算法实现53/102

初始时只含有一个头结点head并置head.next为null。这样链栈的四要素如下：栈空的条件：head.next==null。由于只有在内存溢出才会出现栈满，通常不考虑这种情况。元素e进栈操作：将包含该元素的结点s插入作为首结点。出栈操作：返回首结点值并且删除该结点。栈底栈顶…heada0an-1∧a1头结点54/102和单链表一样，链栈中每个结点的类型LinkNode<E>如下classLinkNode<E>{

//链栈结点泛型类Edata;LinkNode<E>next;publicLinkNode(){ //构造方法next=null;}publicLinkNode(Ed){ //重载构造方法data=d;next=null;}}55/102publicclassLinkStackClass<E>{

//链栈泛型类LinkNode<E>head; //存放头结点publicLinkStackClass(){ //构造方法head=newLinkNode<E>(); //创建头结点head.next=null; //设置为空栈}

//栈的基本运算算法}链栈类模板LinkStackClass<E>56/102链栈的基本运算算法（1）判断栈是否为空empty()publicbooleanempty(){

//判断栈是否为空returnhead.next==null;}∧head57/102（2）进栈push(e)publicvoidpush(Ee) { //元素e进栈LinkNode<E>s=newLinkNode<E>(e); //新建结点s

s.next=head.next;

//将结点s插入到表头

head.next=s;}…head∧头结点es58/102（3）出栈pop()publicEpop() { //出栈操作if(empty())thrownewIllegalArgumentException("栈空");Ee=(E)head.next.data; //取首结点值head.next=head.next.next; //删除原首结点returne;}…heade∧头结点删除59/102（4）取栈顶元素peek()publicEpeek(){ //取栈顶元素操作if(empty())thrownewIllegalArgumentException("栈空");Ee=(E)head.next.data; //取首结点值returne;}…heade∧头结点60/102问题1：在以下几种存储结构中，哪个最适合用作链栈？（1）带头结点的单链表（2）不带头结点的循环单链表（3）带头结点的双链表∧…s（1）栈顶栈底push和pop均为O(1)…s（2）栈顶栈底push和pop均为O(n)∧…s（3）栈顶栈底push和pop均为O(1)（1）最好！链栈的几个问题61/102问题2：在一个算法中需要建立多个栈时可以选用以下三种方案之一，试问这三种方案之间相比各有什么优缺点？

（1）分别用多个顺序存储空间建立多个独立的顺序栈。

（2）多个栈共享一个顺序存储空间。

（3）分别建立多个独立的链栈。

（1）优点是每个栈仅用一个顺序存储空间时，操作简单。缺点是分配空间小了，容易产生溢出，分配空间大了，容易造成浪费，各栈不能共享空间。

（2）优点是多个栈仅用一个顺序存储空间，充分利用了存储空间，只有在整个存储空间都用完时才会产生溢出。缺点是当栈个数大于等于3时其中一个栈满时需要向左、右查询有无空闲单元的过程复杂且十分耗时。

（3）优点是多个链栈一般不考虑栈的溢出，采用动态空间分配具有良好的适应性。缺点是栈中元素要以指针相链接，比顺序存储多占用了存储空间。62/1023.1.5链栈的应用算法设计示例

【例3.8】设计一个算法利用栈的基本运算将一个整数链栈中所有元素逆置。例如链栈st中元素从栈底到栈顶为（1，2，3，4），逆置后为（4，3，2，1）。

这里要求利用栈的基本运算来设计算法，所以不能直接采用单链表逆置方法。先出栈st中所有元素并保存在一个数组a中，再将数组a中所有元素依次进栈。63/102publicstaticLinkStackClass<Integer>

Reverse(LinkStackClass<Integer>st){int[]a=newint[MaxSize];inti=0;while(!st.empty()){ //将出栈的元素放到数组a中a[i]=st.pop();i++;}for(intj=0;j<i;j++) //将数组a的所有元素进栈st.push(a[j]);returnst;}64/102

定义栈的数据结构，要求添加一个popk()函数，能够出栈第k（1≤k≤栈中元素个数，栈顶元素为1）。栈基本运算popk()链栈的扩展65/102参考答案这里并没有要求只能用栈的基本运算！…heada1an∧ak栈顶…离栈顶的第k个结点删除66/102publicEpopk(intk){if(k<1)thrownewIllegalArgumentException("k错误");LinkNode<E>pre=head; //pre为第k个结点的前驱结点inti=0;while(i<k-1&&pre!=null){i++;pre=pre.next;}if(pre.next==null)thrownewIllegalArgumentException("k错误");Ex=pre.next.data;pre.next=pre.next.next;returnx;}在LinkNode<E>中增加如下方法：67/102publicstaticvoidmain(String[]args){LinkStackClass<Integer>st= newLinkStackClass<Integer>();System.out.printf("\n元素5,4,3,2,1依次进栈\n");st.push(5);st.push(4);st.push(3);st.push(2);st.push(1);intk=2;System.out.printf("出栈第%d个元素:%d\n", k,st.popk(k));k=2;System.out.printf("出栈第%d个元素:%d\n", k,st.popk(k));k=3;System.out.printf("出栈第%d个元素:%d\n", k,st.popk(k));k=1;System.out.printf("出栈第%d个元素:%d\n", k,st.popk(k));k=1;System.out.printf("出栈第%d个元素:%d\n", k,st.popk(k));System.out.println();}测试程序12345栈顶68/102Java中提供了Stack栈容器。Stack容器只有一个出口即栈顶，可以在栈顶插入（进栈）和删除（出栈）元素。Stack容器不允许顺序遍历。由于stack采用泛型（类模板）设计，更高效和通用，在编程中尽量使用Stack！3.1.6Java中的栈容器Stack<E>69/102Stack容器主要的成员函数如下：booleanempty()：判断栈是否为空。intsize()：返回栈中元素个数。Epush(E

item)：把对象压入栈顶，即进栈操作。Epop()：移除栈顶对象，并作为此函数的值返回该对象，即出栈操作。Epeek()：查看栈顶对象，但不从栈中移除它，即返回栈顶元素操作。intsearch(Object

o)：返回元素o在栈中的位置，该位置从栈顶开始往下算，栈顶为1。booleancontains(Object

o)：如果栈中包含指定的元素o，则返回true；否则返回false。70/102importjava.util.*;publicclassStackapp{publicstaticvoidmain(String[]args){Stack<String>st=newStack<String>();//建立String栈对象stst.push("a"); //进栈顺序:a,b,c,d,est.push("b");st.push("c");st.push("d");st.push("e");System.out.println("empty():"+st.empty());

//输出:flaseSystem.out.println("peek():"+st.peek());

//输出:eSystem.out.println("search(Objecto):"+st.search("a"));

//输出:5System.out.println("search(Objecto):"+st.search("e"));

//输出:1System.out.println("search(Objecto):"+st.search("no"));

//输出:-1while(!st.isEmpty()) //出栈顺序:e,d,c,b,aSystem.out.println(st.pop()+"");System.out.println("empty():"+st.empty());

//输出:true}}71/102求解问题中需要临时保存一些数据元素：先保存的后处理：栈先保存的先处理：队列3.1.7栈的综合应用72/102exp：仅包含“+”、“-”、“*”、“/”、正整数和小括号的合法数学表达式—中缀表达式。后缀表达式：就是运算符在操作数的后面，已经考虑了运算符的优先级，不包含括号，只含操作数和运算符。123*+1+2*3简单表达式求值73/102exp求值过程：将表达式exp转换成后缀表达式postexp。对该后缀表达式求值。74/102exp

postexp使用运算符栈opor：先出栈的运算符先做运算！exp：…op1

…

op2

…op1┊┊opor栈比较优先级只有P(op2)>P(op1)，才能将op2直接进栈，否则出栈直到满足该条件75/102exp

postexp遇到'('：直接进栈。遇到')'：出栈运算符

postexp，直到栈顶为')'，出栈'('。76/102while(若exp未读完){

从exp读取字符ch;ch为数字：将后续的所有数字均依次存放到postexp中;ch为左括号'('：将'('进栈到opor;ch为右括号')'：将opor栈中'('以前的运算符依次出栈并存放到postexp中,再将'('退栈;

若ch的优先级高于栈顶运算符优先级，则将ch进栈；否则出栈并存放到postexp中,最后将ch进oper栈;}字符串exp扫描完毕,则退栈opor的所有运算符并存放到postexp中转换过程77/102表达式“(56-20)/(4+2)”转换成后缀表达式的过程ch操

作postexpopor栈(将'('进opor栈(56将56存入postexp中，并插入一个字符'#'56#(-由于opor中'('以前没有字符，则直接将'-'进opor栈56#(-20将20#存入postexp中56#20#(-)将栈opor中'('以前的运算符依次出栈并存入postexp，然后将'('出栈56#20#-/将'/'进opor栈56#20#-/(将'('进opor栈56#20#-/(4将4#存入postexp56#20#-4#/(+由于opor中'('以前没有运算符，则直接将'+'进opor栈56#20#-4#/(+2将2#存入postexp56#20#-4#2#/(+)将opor栈中'('以前的运算符依次出栈并存入postexp，然后将'('出栈56#20#-4#2#+/exp扫描完毕，将opor栈中所有运算符依次出栈并存入postexp，得到最后的后缀表达式56#20#-4#2#+/78/102publicvoidTrans(){

//将算术表达式exp转换成后缀表达式postexpStack<Character>opor=newStack<Character>();inti=0; //i作为exp的下标charch,e;while(i<exp.length()){ //exp表达式未扫描完时循环ch=exp.charAt(i);;if(ch=='(')opor.push(ch); //判定为左括号,将其进栈elseif(ch==')'){ //判定为右括号while(!opor.empty()&&opor.peek()!='('){

//将栈中最近(之前的运算符退栈并存入postexpe=opor.pop();postexp+=e;}opor.pop(); //将(退栈}79/102elseif(ch=='+'||ch=='-'){ //判定为加或减号while(!opor.empty()&&opor.peek()!='('){

//将栈中不低于ch的所有运算符退栈并存入postexpe=opor.pop();postexp+=e;}opor.push(ch); //再将'+'或'-'进栈}elseif(ch=='*'||ch=='/'){ //判定为'*'或'/'号while(!opor.empty()&&opor.peek()!='(' &&(opor.peek()=='*'||opor.peek()=='/')){

//将栈中不低于ch的所有运算符退栈并存入postexpe=opor.pop();postexp+=e;}opor.push(ch); //再将'*'或'/'进栈}80/102else { //处理数字字符while(ch>='0'&&ch<='9'){ //判定为数字postexp+=ch;i++; //将连续的数字放入postexpif(i<exp.length())ch=exp.charAt(i);elsebreak;}i--; //退一个字符postexp+='#'; //用#标识一个数值串结束}i++; //继续处理其他字符}81/102while(!opor.empty()){ //此时exp扫描完毕,栈不空时循环e=opor.pop(); //将栈中所有运算符退栈并放入postexppostexp+=e;}}82/102后缀表达式postexp求值使用运算数栈opandwhile(若postexp未读完){

从postexp读取字符ch;ch为'+'：从opand栈出栈两个数值a和b,计算c=b+a;将c进栈opand;ch为'-'：从opand栈出栈两个数值a和b,计算c=b-a;将c进栈opand;ch为'*'：从opand栈出栈两个数值a和b,计算c=b*a;将c进栈opand;ch为'/'：从opand栈出栈两个数值a和b,若a不零,计算c=b/a;将c

进栈opand;ch为数字字符：将连续的数字串转换成数值d,将d进栈opand;}opand栈中唯一的数值即为表达式值83/102后缀表达式“56#20#-4#2#+/”的求值过程ch序列说明opand栈56#遇到56#，将56进栈5620#遇到20#，将20进栈56,20-遇到“-”，出栈两次，将56-20=36进栈364#遇到4#，将4进栈36,42#遇到2#，将2进栈36,4,2+遇到“+”，出栈两次，将4+2=6进栈36,6/遇到“/”，出栈两次，将36/6=6进栈6postexp扫描完毕，算法结束，栈顶数值6即为所求84/102publicdoublegetValue(){

//计算后缀表达式postexp的值Stack<Double>opand=newStack<Double>();doublea,b,c,d;inti=0;charch;while(i<postexp.length()){ //遍历postexp串ch=postexp.charAt(i); //从后缀表达式中取一个字符chswitch(ch){ case'+': //判定为'+'号a=opand.pop(); //退栈取数值ab=opand.pop(); //退栈取数值bc=b+a; //计算copand.push(c); //将计算结果进栈break;85/102case'-': //判定为'-'号 a=opand.pop(); //退栈取数值a b=opand.pop(); //退栈取数值b c=b-a; //计算c opand.push(c); //将计算结果进栈 break;case'*': //判定为'*'号 a=opand.pop(); //退栈取数值a b=opand.pop(); //退栈取数值b c=b*a; //计算c opand.push(c); //将计算结果进栈 break;case'/': //判定为'/'号 a=opand.pop(); //退栈取数值a b=opand.pop(); //退栈取数值b if(a!=0){ c=b/a; //计算c opand.push(c); //将计算结果进栈 } else thrownewArithmeticException("运算错误:除零"); break;86/102default: //处理数字字符d=0; //将连续数字符转换成数值存到d中while(ch>='0'&&ch<='9'){ //判定为数字字符d=10*d+(ch-'0');i++;ch=postexp.charAt(i);}opand.push(d); //将数值d进栈break;}i++; //继续处理其他字符}returnopand.peek(); //栈顶元素即为求值结果}87/102求表达式值的两个步骤可以合并起来，不必产生后缀表达式：将所有遇到的运算数进opand栈。在opor出栈一个运算符op时，从opand中依次出栈两个运算数a、b，执行c=bopa运算，将c进opand栈。88/102HDU1237—简单计算器89/102手工转换产生后缀表达式5+2*(1+6)-8/25+(2*(1+6))-8/25+(2*(1+6))-(8/2)(5+(2*(1+6)))-(8/2)((5+(2*(1+6)))-(8/2))加括号((5+(2*(1+6)))-(8/2))除括号5216+*+82/-90/1021、若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作：

（1）从S1中依次弹出两个操作数a和b；

（2）从S2中弹出一个运算符op；

（3）执行相应的运算bopa；

（4）将运算结果压入S1中。

假定S1中的操作数依次是5，8，3，2（2在栈顶），S2中的运算符依次是*，-，+（+在栈顶）。调用3次F()后，S1栈顶保存的值是（

）。A.-15 B.15 C.-20 D.202018年全国硕士研究生入学统一考试题示例按求后缀表达式值的过程操作！91/1022．假设栈初始为空，将中缀表达式a/b+(c*d-e*f)/g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是（）。A．+(*-B．+(-*C．/+(*-*D．/+-*2014年全国硕士研究生入学统一考试题示例按中缀转换为后缀表达式的过程操作！92/1021032443210出口55入口求迷宫问题一个迷宫图求从入口到出口的一条简单路径int[][]mg={{1,1,1,1,1,1},{1,0,1,0,0,1},{1,0,0,1,1,1},{1,0,1,0,0,1},{1,0,0,0,0,1},{1,1,1,1,1,1}};93/102方位3(i-1,j)(i+1,j)(i,j-1)方位0方位1方位2(i,j)(i,j+1)试探顺序94/102回溯回溯回溯当前方块(i，j)前一方块…继续找其他路径迷宫问题的搜索过程用栈记录走过的路径路径：由方块和方块之间的走向（方位）构成相邻方块方块di95/102classBox{

//方块类inti; //方块的行号intj; //方块的列号intdi; //di是下一可走相邻方位的方位号publicBox(inti1,intj1,intdi1) {//构造方法i=i1;j=j1;di=di1;}}Stack<Box>st; //建立一个栈相邻方块当前方块di96/102di=2di=1di=2di=2di=1di=1di=0di=1di=2[1,1][2,1][2,2]:×[3,1][4,1][4,2][4,3][3,3][3,4][4,4]1032443210出口55入口→↑→

↓→↓↓↓10324432105597/102classMazeClass{

//用栈求解一条迷宫路径类finalintMaxSize=20;int[][]mg; //迷宫数组intm,n; //迷宫行列数publicMazeClass(intm1,intn1){ //构造方法m=m1;n=n1;mg=newint[MaxSize][MaxSize];}publicvoidSetmg(int[][]a){ //设置迷宫数组for(inti=0;i<m;i++)for(intj=0;j<n;j++) mg[i][j]=a[i][j];}98/102booleanmgpath(intxi,intyi,intxe,intye){

//求一条从(xi,yi)到(xe,ye)的迷宫路径inti,j,di,i1=0,j1=0;booleanfind;Boxbox,e;

Stack<Box>st=newStack<Box>();

//建立一个空栈st.push(newBox(xi,yi,-1)); //入口方块进栈mg[xi][yi]=-1; //为避免来回找相邻方块,将其置为-1while(!st.empty()){ //栈不空时循环box=st.peek(); //取栈顶方块,称为当前方块i=box.i;j=box.j;di=box.di;if(i==xe&&j==ye){ //找到了出口,输出一条路径intcnt=1;while(!st.empty()){e=st.pop();System.out.print("["+e.i+","+e.j+"]");