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

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

a1

…

an-1栈底栈顶进栈出栈3.1.1栈的定义3/85后放置的木块先取出来4/85后进先出，即后进栈的元素先出栈。每次进栈的元素都作为新栈顶元素，每次出栈的元素只能是当前栈顶元素。栈也称为后进先出表或者先进后出表。栈的主要特点：5/85栈抽象数据类型=线性结构+栈的基本运算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}基本运算：empty()：判断栈是否为空，若空栈返回真；否则返回假。push(e)：进栈操作，将元素e插入到栈中作为栈顶元素。pop()：出栈操作，返回栈顶元素。gettop()：取栈顶操作，返回当前的栈顶元素。}6/85栈元素基本运算应用程序7/85一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（）。A.edcba B.decba

C.dceab D.abcde示例方法1：用栈模拟进行判断dcba考虑C.dceabcbad不可能有出栈序列：ab8/85一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（）。A.edcba B.decba

C.dceab D.abcde示例方法2：利用判断准则判断准则：输入序列为1，2，…，n，（p1，p2，…，pn）是1，2，…，n的一种排列，利用一个栈得到输出序列（p1，p2，…，pn）的充分必要条件是不存在这样的i、j、k满足i<j<k的同时也满足pj<pk<pi。dceab违反了!pipjpk9/851～n共产生n+11C2nn种合法出栈序列。例如，n=545321合法31254不合法14235不合法10/85已知一个栈的进栈序列是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+111/852013年全国硕士研究生入学统一考试题示例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外都可能！12/85栈的实现方式线性表顺序表链表栈顺序栈链栈逻辑结构存储结构映射∩3.1.2栈的顺序存储结构及其基本运算算法实现13/85顺序栈实现a0a1…ai-1ai…an-1data列表元素索引01…i-1i…n-1top栈底利用Python列表具有动态扩展的功能。将data[0]端作为栈底，另外一端data[-1]作为栈顶。其中的元素个数len(data)恰好为栈中实际元素个数。常规做法：利用动态列表的做法：14/85（a）空栈[]a（b）元素a进栈0dcba（c）元素b、c、d进栈3210cba（d）元素d出栈210顺序栈的四要素如下：①栈空条件：len(data)==0或者notdata。②栈满条件：由于data列表可以动态扩展，所以不必考虑栈满。③元素e进栈操作：将e添加到栈顶处。④出栈操作：删除栈顶元素并返回该元素。顺序栈15/85classSqStack:def__init__(self):#构造方法self.data=[]#存放栈中元素，初始为空

#栈的基本运算算法顺序栈类SqStack16/85顺序栈的基本运算算法（1）判断栈是否为空empty()defempty(self):

#判断栈是否为空iflen(self.data)==0:returnTruereturnFalse17/85（2）进栈push(e)defpush(self,e):#元素e进栈self.data.append(e)18/85（3）出栈pop()defpop(self):

#元素出栈assertnotself.empty() #检测栈为空returnself.data.pop()19/85（4）取栈顶元素gettop()defgettop(self): #取栈顶元素assertnotself.empty() #检测栈为空returnself.data[-1]20/85?顺序栈的几个问题问题1：若采用数组data[1..m]存放栈元素，回答以下问题：（1）只能以data[1]端作为栈底吗？（2）为什么不能以data数组的中间位置作为栈底？答：（1）也可以将data[m]端作为栈底。

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

若一个栈用数组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……ntop22/85

若一个栈用数组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……ntop23/85

若一个栈用数组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……ntop24/85

若一个栈用数组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……ntop25/853.1.3顺序栈的应用算法设计示例

【例3.4】设计一个算法利用顺序栈检查用户输入的表达式中括号是否配对（假设表达式中可能含有圆括号、中括号和大括号）。并用相关数据进行测试。26/85fromSqStackimportSqStack #引用顺序栈SqStackdefisMatch(str): #判断表达式各种括号是否匹配的算法st=SqStack() #建立一个顺序栈i=0whilei<len(str):e=str[i]ife=='('ore=='['ore=='{':st.push(e) #将左括号进栈else:ife==')':ifst.empty()orst.gettop()!='(':returnFalse #栈空或栈顶不是'('返回假st.pop()ife==']':ifst.empty()orst.gettop()!='[':returnFalse #栈空或栈顶不是'['返回假st.pop()ife=='}':ifst.empty()orst.gettop()!='{':returnFalse; #栈空或栈顶不是'{'返回假st.pop()i+=1 #继续遍历strreturnst.empty()27/85#主程序print("测试1")str="([)]"ifisMatch(str):print(str+"中括号是匹配的")else:print(str+"中括号不匹配")print("测试2")str="([])"ifisMatch(str):print(str+"中括号是匹配的")else:print(str+"中括号不匹配")28/85

【例3.5】设计一个算法利用顺序栈判断用户输入的字符串表达式是否为回文。并用相关数据进行测试。29/85①用i从头开始遍历str，将前半部分字符依次进栈。②若n为奇数，i增1跳过中间的字符。③i继续遍历其他后半部分字符，每访问一个字符，则出栈一个字符，两者进行比较，如图所示，若不相等返回False。④当str遍历完毕返回True。一个字符栈…

stri

…strn-1etop┇是否相等？

解：用str存放表达式，其中含n个字符。若str的前半部分的反向序列与str的后半部分相同，则是回文，否则不是回文。判断过程如下：30/85fromSqStackimportSqStackdefisPalindrome(str): #判断是否为回文的算法st=SqStack() #建立一个顺序栈n=len(str)i=0whilei<n//2: #将str前半字符进栈st.push(str[i])i+=1 #继续遍历strifn%2==1: #n为奇数时i+=1 #跳过中间的字符whilei<n: #遍历str的后半字符ifst.pop()!=str[i]:returnFalse #若str[i]不等于出栈字符返回Falsei+=1returnTrue #是回文返回True31/85#主程序print("测试1")str="abcba"ifisPalindrome(str):print(str+"是回文")else:print(str+"不是回文")print("测试2")str="1221"ifisPalindrome(str):print(str+"是回文")else:print(str+"不是回文")32/85

【例3.6】设计最小栈。定义栈的数据结构，添加一个Getmin()方法用于返回栈中的最小元素。要求方法Getmin()、push以及pop的时间复杂度都是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）

最小元素：533/85ai┇a0data栈bj┇mindata栈最小元素为bj含data和mindata两个列表，data列表表示data栈（主栈），mindata列表表示mindata栈，后者作为存放当前最小元素的辅助栈。当元素a0，a1，…，ai（i≥1）进栈到data栈后，min栈的栈顶元素bj为a0，a1，…，ai中的最小元素（含后进栈的重复最小元素），如下图所示。解：设计满足题目要求的顺序栈类为STACK：34/85ai┇a0data栈bj┇mindata栈最小元素为bjbj为a0

…

ai中的最小元素STACK类的主要运算算法设计如下：Getmin()方法用于返回栈中的最小元素，其操作是取mindata栈的栈顶元素。进栈方法push(x)的操作是，当data栈空或者进栈元素x小于等于当前栈中最小元素（即x≤Getmin()）时，则将x进mindata栈。最后将x进data栈。出栈方法pop()的操作是，当data栈不空时，从data栈出栈元素x，若mindata栈的栈顶元素等于x，则同时从mindata栈出栈x。最后返回x。取栈顶方法gettop()的操作是，当data栈不空时，返回data栈的栈顶元素。35/85classSTACK: #含Getmin()的栈类def__init__(self): #构造方法self.data=[] #存放主栈中元素，初始为空self.__mindata=[] #存放min栈中元素，初始为空

#min栈基本运算算法def__minempty(self): #判断min栈是否空returnlen(self.__mindata)==0def__minpush(self,e): #元素进min栈self.__mindata.append(e)def__minpop(self): #元素出min栈assertnotself.__minempty() #检测min栈为空的异常returnself.__mindata.pop()def__mingettop(self): #取min栈栈顶元素assertnotself.__minempty() #检测min栈为空的异常returnself.__mindata[-1];36/85

#主栈基本运算算法defempty(self): #判断主栈是否空returnlen(self.data)==0defpush(self,x): #元素进主栈ifself.empty()orx<=self.Getmin():self.__mindata.append(x) #栈空或者x<=min栈顶元素时进min栈self.data.append(x); #将x进主栈defpop(self): #元素出主栈assertnotself.empty() #检测主栈为空的异常x=self.data.pop() #从主栈出栈xifx==self.__mingettop(): #若栈顶元素为最小元素self.__minpop() #min栈出栈一次returnx37/85defgettop(self): #取主栈栈顶元素assertnotself.empty() #检测主栈为空的异常returnself.data[-1]defGetmin(self): #获取栈中最小元素assertnotself.empty() #检测主栈为空的异常returnself.__mindata[-1]; #返回min栈顶元素即主栈最小元素38/85#主程序st=STACK()print("\n元素5,6,3,7依次进栈")st.push(5)st.push(6)st.push(3)st.push(7)print("求最小元素并出栈")whilenotst.empty(): print("最小元素:%d"%(st.Getmin())) print("出栈元素:%d"%(st.pop()))print()39/85

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

解：为了尽量利用空间，减少溢出的可能，可以让两个的栈顶相向即进栈元素迎面增长的存储方式，为此设置两个栈的栈顶指针分别为top1和top2（均指向对应栈的栈顶元素）。a0

a1

a2

…

an-1

……

bm-1

bm-2

…

b1

b0012…M-1栈1底栈1顶栈2顶栈2底栈顶指针top1栈顶指针top2s：40/85a0

a1

a2

…

an-1

……

bm-1

bm-2

…

b1

b0012…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++。41/85栈的实现方式线性表顺序表链表栈顺序栈链栈逻辑结构存储结构映射∩3.1.4栈的链式存储结构及其基本运算算法实现42/85

初始时只含有一个头结点head并置head.next为None。这样链栈的四要素如下：栈空的条件：head.next==None。由于只有在内存溢出才会出现栈满，通常不考虑这种情况。元素e进栈操作：将包含该元素的结点s插入作为首结点。出栈操作：返回首结点值并且删除该结点。栈底栈顶…heada0an-1∧a1头结点43/85和单链表一样，链栈中每个结点的类型LinkNode如下classLinkNode: #单链表结点类def__init__(self,data=None): #构造方法self.data=data #data属性self.next=None #next属性44/85classLinkStack: #链栈类def__init__(self): #构造方法self.head=LinkNode() #头结点headself.head.next=None

#栈的基本运算算法链栈类LinkStack∧head45/85链栈的基本运算算法（1）判断栈是否为空empty()defempty(self): #判断栈是否为空ifself.head.next==None:returnTruereturnFalse∧head46/85（2）进栈push(e)defpush(self,e): #元素e进栈p=LinkNode(e)p.next=self.head.nextself.head.next=p…head∧头结点ep47/85（3）出栈pop()defpop(self): #元素出栈assertself.head.next!=None #检测空栈的异常p=self.head.next;self.head.next=p.nextreturnp.data…heade∧头结点删除p48/85（4）取栈顶元素gettop()defgettop(self): #取栈顶元素assertself.head.next!=None #检测空栈的异常returnself.head.next.data…heade∧头结点49/85问题1：在以下几种存储结构中，哪个最适合用作链栈？（1）带头结点的单链表（2）不带头结点的循环单链表（3）带头结点的双链表∧…s（1）栈顶栈底push和pop均为O(1)…s（2）栈顶栈底push和pop均为O(n)∧…s（3）栈顶栈底push和pop均为O(1)（1）最好！?链栈的几个问题50/85问题2：在一个算法中需要建立多个栈时可以选用以下三种方案之一，试问这三种方案之间相比各有什么优缺点？

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

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

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

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

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

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

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

解：这里要求利用栈的基本运算来设计算法，所以不能直接采用单链表逆置方法。先出栈st中所有元素并保存在一个数组a中，再将数组a中所有元素依次进栈。52/85fromLinkStackimportLinkStack #引用链栈SqStackdefReverse(st): #逆置栈sta=[]whilenotst.empty(): #将出栈的元素放到列表a中a.append(st.pop())forjinrange(len(a)): #将列表a的所有元素进栈st.push(a[j])returnst53/85

【例3.9】有一个含1～n的n个整数的序列a，通过一个栈可以产生多种出栈序列，设计一个算法采用链栈判断序列b（为1～n的某个排列）是否得为一个合适的出栈序列，并用相关数据进行测试。栈a序列b序列54/85

解：建立一个整型链栈st，用i、j分别遍历a、b序列（初始值均为0），在a序列没有遍历完时循环：①将a[i]进栈，i++。②栈不空并且栈顶元素与b[j]相同时循环：出栈元素e，j++。

在上述过程结束后，如果栈空返回True表示b序列是a序列的出栈序列，否则返回False表示b序列不是a序列的出栈序列。55/85fromLinktackimportLinkStack #引用链栈LinkStackdefisSerial(a,b,n): #判断b是否为a的出栈序列算法st=LinkStack() #建立一个链栈i,j=0,0whilei<n: #遍历a序列st.push(a[i])i+=1 #i后移whilenotst.empty()andst.gettop()==b[j]:st.pop() #出栈j+=1 #j后移returnst.empty() #栈空返回True否则返回False56/85#主程序n=4a=[1,2,3,4]print("测试1")b=[1,3,2,4]ifisSerial(a,b,n):print(b,"是合法的出栈序列")else:print(b,"不是合法的出栈序列")print("测试2")c=[4,3,1,2]ifisSerial(a,c,n):print(c,"是合法的出栈序列")else:print(c,"不是合法的出栈序列")57/85求解问题中需要临时保存一些数据元素：先保存的后处理：栈先保存的先处理：队列3.1.6栈的综合应用58/85exp：仅包含“+”、“-”、“*”、“/”、正整数和小括号的合法数学表达式—中缀表达式。后缀表达式：就是运算符在操作数的后面，已经考虑了运算符的优先级，不包含括号，只含操作数和运算符。123*+1+2*3简单表达式求值59/85exp求值过程将表达式exp转换成后缀表达式postexp。对该后缀表达式求值。Python列表表示60/85设计求表达式值的类ExpressClassclassExpressClass:

#求表达式值类def__init__(self,str): #构造方法self.exp=str #存放中缀表达式self.postexp=[] #存放后缀表达式defgetpostexp(self): #返回postexpreturnself.postexpdefTrans(self): #将exp转换为postexp

…defgetValue(self): #计算后缀表达式postexp的值

…61/85exp

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

…

op2

…op1┊┊opor栈比较优先级：P(op1)>P(op2)，才能将op2直接进栈，否则出栈直到满足该条件62/85while(若exp未读完){从exp读取字符ch;ch为数字：将后续的所有数字均依次存放到postexp中;ch为左括号'('：将'('进栈到opor;ch为右括号')'：将opor栈中与值匹配的'('后进栈的运算符依次出栈

并存放到postexp中,再将'('退栈;

若ch的优先级高于栈顶运算符优先级，则将ch进栈；否则出栈并存放

到postexp中,再将ch进oper栈;}字符串exp扫描完毕,则退栈opor的所有运算符并存放到postexp中转换过程63/85表达式“(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#存入postexp[56,20,'-',4]/(+由于opor中'('以前没有运算符，则直接将'+'进opor栈[56,20,'-',4]/(+2将2#存入postexp[56,20,'-',4,2]/(+)将opor栈中'('以前的运算符依次出栈并存入postexp，然后将'('出栈[56,20,'-',4,2,'+']/exp扫描完毕，将opor栈中所有运算符出栈并存入postexp，得到最后的后缀表达式[56,20,'-',4,2,'+','/']64/85defTrans(self): #将exp转换为postexpopor=SqStack() #定义运算符栈i=0 #i作为exp的索引whilei<len(self.exp): #遍历expch=self.exp[i] #提取str[i]字符chifch=="(": #判定为左括号,将左括号进栈opor.push(ch)elifch==")": #判定为右括号whilenotopor.empty()andopor.gettop()!="(":e=opor.pop() #将栈中最近"("之前的运算符退栈self.postexp.append(e) #退栈运算符添加到postexpopor.pop() #再将(退栈65/85elifch=="+"orch=="-": #判定为加或减号whilenotopor.empty()andopor.gettop()!="(":e=opor.pop() #将栈中不低于ch的所有运算符退栈self.postexp.append(e) #退栈运算符添加到postexpopor.push(ch) #再将"+"或"-"进栈elifch=="*"orch=="/": #判定为"*"或"/"号whilenotopor.empty():e=opor.gettop()ife!="("and(e=="*"ore=="/"):e=opor.pop()#将栈中不低于ch优先级的所有运算符退栈self.postexp.append(e) #退栈运算符添加到postexpelse:breakopor.push(ch) #再将"*"或"/"进栈66/85else: #处理数字字符d=""whilech>="0"andch<="9": #判定为数字d+=ch #提取所有连续的数字字符i+=1ifi<len(self.exp):ch=self.exp[i]else:breaki-=1 #退一个字符self.postexp.append(int(d)) #连续数字符转换为整数运算数i+=1 #继续处理其他字符67/85whilenotopor.empty(): #此时exp扫描完毕,栈不空时循环e=opor.pop() #将栈中所有运算符退栈并添加到postexpself.postexp.append(e)68/85后缀表达式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栈中唯一的数值即为表达式值69/85后缀表达式[56,20,'-',4,2,'+','/']的求值过程ch序列说明st栈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即为所求70/85defgetValue(self): #计算后缀表达式postexp的值opand=SqStack() #定义运算数栈i=0whilei<len(self.postexp): #遍历postexpopv=self.postexp[i] #从后缀表达式中取一个元素opvifopv=="+": #判定为"+"号a=opand.pop() #退栈取运算数ab=opand.pop() #退栈取运算数bc=b+a #计算copand.push(c) #将计算结果进栈elifopv=="-": #判定为"-"号a=opand.pop() #退栈取运算数ab=opand.pop() #退栈取运算数bc=b-a #计算copand.push(c) #将计算结果进栈71/85elifopv=="*": #判定为"*"号 a=opand.pop() #退栈取运算数a b=opand.pop() #退栈取运算数b c=b*a #计算c opand.push(c) #将计算结果进栈elifopv=="/": #判定为"/"号 a=opand.pop() #退栈取运算数a b=opand.pop() #退栈取运算数b asserta!=0 #检测a为0的情况 c=b/a #计算c opand.push(c) #将计算结果进栈else: #处理运算数 opand.push(opv) #将运算数opv进栈i+=1 #继续处理postexp的其他元素

returnopand.gettop()

#栈顶元素即为求值结果72/85主程序str="(56-20)/(4+2)"print("中缀表达式:"+str)obj=ExpressClass(str)obj.Trans()print("后缀表达式:",obj.getpostexp())print("求值结果:%g"%(obj.getValue()))73/85求表达式值的两个步骤可以合并起来，不必产生后缀表达式：将所有遇到的运算数进opand栈。在opor出栈一个运算符op时，从opand中依次出栈两个运算数a、b，执行c=bopa运算，将c进opand栈。74/85手工转换产生中缀表达式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/-75/851、若栈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年全国硕士研究生入学统一考试题示例按求后缀表达式值的过程操作！76/852．假设栈初始为空，将中缀表达式a/b+(c*d-e*f)/g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是（）。A．+(*-B．+(-*C．/+(*-*D．/+-*2014年全国硕士研究生入学统一考试题示例按中缀转换为后缀表达式的过程操作！77/851032443210出口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}};78/85方位3(i-1,j)(i+1,j)(i,j-1)方位0方位1方位2(i,j)(i,j+1)试探顺序dx=[-1,0,1,0]#x方向的偏移量dy=[0,1,0,-1]#y方向的偏移量79/85回溯回溯回溯当前方块(i，j)前一方块…继续找其他路径迷宫问题的搜索过程用栈记录走过的路径路径：由方块和方块之间的走向（方位）构成相邻方块方块di80/85classBox: #方块类def__init__(self,i1,j1,di1): #构造方法self.i=i1 #方块的行号self.j=j1 #方块的列号self.di=di1 #di是可走相邻方位的方位号相邻方块当前方块di81/85di=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入口→↑→

↓→↓↓↓10324432105582/85defmgpath(xi,yi,xe,ye): #求一条从(xi,yi)到(xe,ye)的迷宫路径globalmg #迷宫数组为全局变量st=SqStack() #定义一个顺序栈dx=[-1,0,1,0]#x方向的偏移量dy=[0,1,0,-1]#y方向的偏移量e=Box(xi,yi,-1)#建立入口方块对象st.push(e) #入口方块进栈mg[xi][yi]=-1 #为避免来回找相邻方块,将进栈的方块置为-1whilenotst.empty(): #栈不空时循环b=st.gettop() #取栈顶方块,称为当前方块ifb.i==xeandb.j==ye: #找到了出口,输出栈中所有方块构成一条路径forkinrange(len(st.data)): print("["+str(st.data[k].i)+','+str(st.data[k].j)+"]",end='')returnTrue #找到一条路径后返回True83/85find=False #否则继续找路径di=b.diwhiledi<3andfind==False: #找b的一个相邻可走方块di+=1 #找下一个方位的相邻方块i,j=b.i+dx[di],b.j+dy[di] #找b的di方位的相邻方块(i,j)ifmg[i][j]==0: #(i,j)方块可走find=Trueiffind: #找到了一个相邻可走方块(i,j)b.di=di #修改栈顶方块的di为新值b1=Box(i,j,-1) #建立相邻可走方块(i,j)的对象b1st.push(b1) #b1进栈mg[i][j]=-1 #为避免来回找相邻方块else: #没有路径可走,则退栈mg[b.i][b.j]=0 #恢复当前方块的迷宫值st.pop() #将栈顶方块退栈returnFalse #没有找到迷宫路径,返回False84/85xi,yi=1,1xe,ye=4,4print("一条迷宫路径:",end='')ifnotmgpath(xi,yi,xe,ye): #(1,1)->(4,4)print("不存在迷宫路径")设计主程序→↑→

↓→↓↓↓10324432105585/85为什么找到的路径不一定是最短路径？如何求所有的迷宫路径？86/85链队队列的综合应用顺序队队列的定义Python中的双端队列deque双端队列优先队列3.2队列87/76队列（queue）是一种只能在不同端进行插入或删除操作的线性表。进行插入的一端称做队尾（rear），进行删除的一端称做队头或队首（front）。队列的插入操作通常称为进队或入队（push），队列的删除操作通常称为出队或离队（pop）。3.2.1队列的定义a0

a1

…

an-1队头队尾进队出队88/76先买餐的人先出队89/76先进先出，即先进队的元素先出队。每次进队的元素作为新队尾元素，每次出队的元素只能是队头的元素。队列也称为先进先出表。队列的主要特点：90/76队列抽象数据类型=线性结构+队列的基本运算ADTQueue{数据对象：D={ai|0≤i≤n-1，n≥0}数据关系：R={r}r={<ai，ai+1>|ai，ai+1∈D，i=0，…，n-2}基本运算：empty()：判断队列是否为空，若队列为空，返回真，否则返回假。push(e)：进队，将元素e进队作为队尾元素。pop()：出队，从队头出队一个元素。gethead()：取队头，返回队头元素而不出队。}91/76【例3.10】若元素进队顺序为1234，能否得到3142的出队序列？

解：进队顺序为1234，则出队的顺序也为1234（先进先出），所以不能得到3142的出队序列。92/76队列的实现方式线性表顺序表链表队列顺序队链队逻辑结构存储结构映射∩3.2.2队列的顺序存储结构及其基本运算算法实现93/76…a0

a1

…

an-1

…frontrear用data列表来存放队列中元素。约定队头指针为front（实际上是队头元素的前一个位置），队尾指针为rear（正好是队尾元素的位置）。为了简单，使用固定容量的列表data（容量为常量MaxSize）。94/761.非循环队列初始时置front和rear均为-1（front==rear）元素进队，rear增加1元素出队列，front增加1…a0

a1

…

an-1

…frontrear95/7643210（a）空队-1frontrearedcb（b）5个元素进队43210-1arearfrontedcb（c）出队1次43210-1rearfront（c）出队4次43210-1rearfront96/76初始时置front和rear均为-1（front==rear），该顺序队的四要素如下：队空条件：front==rear。队满（上溢出）条件：rear==MaxSize-1（因为每个元素进队都让rear增1，当rear到达最大下标时不能再增加。元素e进队操作：rear增1，将元素e放在该位置（进队的元素总是在尾部插入的）。出队操作：front增1，取出该位置的元素（出队的元素总是在队头出来的）。97/76MaxSize=100 #假设容量为100classSqQueue: #非循环队列类def__init__(self): #构造方法self.data=[None]*MaxSize #存放队列中元素self.front=-1 #队头指针self.rear=-1 #队尾指针

#队列的基本运算算法非循环队列类SqQueue98/76非循环队列的基本运算算法（1）判断队列是否为空empty()defempty(self): #判断队列是否为空returnself.front==self.rear43210-1frontrear99/76（2）进队push(e)defpush(self,e): #元素e进队assertnotself.rear==MaxSize-1 #检测队满self.rear+=1self.data[self.rear]=eedcb43210-1rearfront43210-1rearfront假溢出！100/76（3）出队pop()defpop(self): #出队元素assertnotself.empty() #检测队空self.front+=1returnself.data[self.front]101/76（4）取队头元素gethead()defgethead(self): #取队头元素assertnotself.empty() #检测队空returnself.data[self.front+1]102/762.循环队列

把data数组的前端和后端连接起来，形成一个循环数组，即把存储队列元素的表从逻辑上看成一个环，称为循环队列（也称为环形队列）。MaxSize=8arearfrontdcbe解决假溢出edcbafrontrear103/76

循环队列首尾相连，当队尾指针rear=MaxSize-1时，再前进一个位置就应该到达0位置，这可以利用数学上的求余运算（％）实现：队首指针循环进1：front=(front+1)％MaxSize队尾指针循环进1：rear=(rear+1)％MaxSize104/76MaxSize=4，初始front=rear=00123frontrear（a）空队a0123frontrear（b）a进队ba0123frontrear（c）b进队cba0123frontrear（d）c进队dcba0123frontrear（e）d进队问题：如何区分队空和队满足？105/76顺序队（含循环队列和非循环队列）通过front和rear标识队列状态，一般是采用它们的相对值即|front-rear|实现的。若data数组的容量为m，则队列的状态有m+1种，分别是队空、队中有1个元素、队中有2个元素、…、队中有m个元素（队满）。front和rear的取值范围均为0～m-1，这样|front-rear|只有m个值。显然m+1种状态不能直接用|front-rear|区分，因为必定有两种状态不能区分。为此让队列中最多只有m-1个元素，这样队列恰好只有m种状态了，就可以通过front和rear的相对值区分所有状态了。如何设计队空队满的条件？106/76

在规定队中最多只有m-1个元素时，设置队空条件仍然是rear==front。当队列有m-1个元素时一定满足(rear+1)%MaxSize==front。

这样，循环队列在初始时置front=rear=0，其四要素如下：队空条件：rear==front。队满条件：(rear+1)%MaxSize==front（相当于试探进队一次，若rear达到front，则认为队满了）。元素e进队：rear=(rear+1)%MaxSize，将元素e放置在该位置。元素出队：front=(front+1)%MaxSize，取出该位置的元素。107/76MaxSize=100 #全局变量，假设容量为100classCSqQueue: #循环队列类def__init__(self): #构造方法self.data=[None]*MaxSize #存放队列中元素self.front=0 #队头指针self.rear=0 #队尾指针#队列的基本运算算法循环队列类SqQueue108/76循环队列的基本运算算法（1）判断队列是否为空empty()defempty(self): #判断队列是否为空returnself.front==self.rear109/76（2）进队push(e)defpush(self,e): #元素e进队assert(self.rear+1)%MaxSize!=self.front #检测队满self.rear=(self.rear+1)%MaxSizeself.data[self.rear]=e110/76（3）出队pop()defpop(self): #出队元素assertnotself.empty() #检测队空self.front=(self.front+1)%MaxSizereturnself.data[self.front]111/76（4）取队头元素gethead()defgethead(self): #取队头元素assertnotself.empty() #检测队空head=(self.front+1)%MaxSize #求队头元素的位置returnself.data[head]112/763.2.3顺序队的应用算法设计示例

【例3.11】在CSqQueue循环队列类中增加一个求元素个数的算法size()。对于一个整数循环队列qu，利用队列基本运算和size()算法设计进队和出队第k（k≥1，队头元素的序号为1）个元素的算法。113/76cnt=(rear-front)=3MaxSize=501234frontrearabc01234frontrearabccnt=(rear-front)=-2

cnt=(rear-front+MaxSize)=3cnt=(rear-front+MaxSize)=8

cnt=(rear-front+MaxSize)%MaxSize=3

cnt=(rear-front+MaxSize)%MaxSize=3

114/76defsize(self): #返回队中元素个数

return((self.rear-self.front+MaxSize)%MaxSize)在CSqQueue循环队列类中增加size()