1、3.33.3栈栈情景导入情景导入PART1 1栈的概念与特性栈的概念与特性一一 栈的概念与特性栈的概念与特性 栈是一种操作受限的线性表，仅允许在表的一端的进行插入和删除蓝莓味葡萄味草莓味栈顶栈底蓝莓味葡萄味草莓味哈密瓜味推入弹出 进行插入或删除操作的一端称为栈顶，位于栈顶位置的元素称为栈顶元素;相应地，将表的另一端称为栈底，位于栈底位置的元素为栈底元素。一一 栈的概念与特性栈的概念与特性(1)先进后出、后进先出 （last in first out,故栈也称为后进先出表(LIFO表)）由栈的定义可知，栈具备“先进后出、后进先出”的特点。(2)有限序列性 栈中的元素是有限的。栈可以是空的，也可以
2、包含多个元素。栈中元素呈现线性关系，栈顶元素有一个前驱点，栈底元素有一个后继点，其他元素既有一个前驱点，又有一个后继点。练习练习1.元素A,B,C,D依次进栈后，栈顶元素是（）栈底元素是（）DA2.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印缓冲区，主机将要打印的数据依次写进该缓冲区，而打印机一次从该缓冲区取出数据，该缓冲区的逻辑结构应该是（）A.栈B.队列C.树D.图B练习练习3.有六个元素以6,5,4,3,2,1的顺序进栈，（）不是合法的出栈顺序A.5,4,3,6,1,2B.4,5,3,1,2,6C.3,4,6,5,2,1D.2,3,4,1,5,6C练习练习4.若元素a、b、
3、c、d、e、f依次进栈，允许进栈退栈操作交替进行，但不允许连续3次进行退栈操作，则不可能得到的出栈序列是（）A.d,c,e,b,f,aB.c,b,d,a,e,fC.b,c,a,e,f,dD.a,f,e,d,c,bDPART2 2栈的基本操作栈的基本操作一一 栈的基本操作栈的基本操作1.栈的创建 栈的创建方式有很多种（链栈、顺序栈），一般按照顺序存储，可以用数组来实现。由于栈顶元素在数组中的位置会发生改变，因此用top变量来记录栈顶元素在数组中的位置。当top为-1时，表示栈为空。st=“”*4top=-1sttop=-1一一 栈的基本操作栈的基本操作2.入栈 入栈又叫压栈操作，把数据元素压入栈
4、顶。字母“A”、“B”、“C”、“D”依次入栈。sttop=-1top=top+1sttop=“A”topABCD一一 栈的基本操作栈的基本操作3.出栈操作 出栈时把栈顶元素取出，同时top减一，当top为-1时，表示栈为空。sttop=-1print（sttop）top=top-1topABCD练习练习【例1】下列代码段能够实现分离正整数,并输出其各位数字(用空格隔开)的功能。请在划线处填入合适的代码。st=0*10#创建一个空栈top=-1num=int(input(“请输入一个正整数:)while num0:sttop=num=num/10print(输出结果为:,end=)while
5、top-1:print(，end=)top-=1top+=1num%10sttop例题例题1 11.十进制转二进制st=-1*100#列表中元素初始值-1top=-1number=int(input(请输入十进制整数:)while number0:x=number%2 _ _#入栈 number=number/2while top-0:print(sttop,end=)#出栈 _top=top+1sttop=x top=top-1例题例题2 22.括号匹配在一个数学计算式“(a(b-c)+d)e”中，位置1和位置4有左括号“(，位置9和位置12有右括号“)”。位置1的左括号与位置12的右括号相
6、匹配，位置4的左括号与位置9的右括号相匹配。而对于数学计算式“a(b-c)，位置8的右括号没有可匹配的左括号。设计一个程序，判断输入的数学计算式中的括号(只有小括号)是否匹配。()()()(数量、位置例题例题2 22.括号匹配st-=*100top=-1flag=True#标记是否有不匹配的情况s=input(请输入数学计算式:)for i in range(len():if si=(:_ elif si=):if top=-1:_ break else:_iftop=0:#栈中还有左括号 flag=Falseif flag:print(括号匹配”)else:print(括号不匹配)top=t
7、op+1sttop=siflag=Falsetop=top-1PART3 3列表自带函数实现栈列表自带函数实现栈列表自带方法列表自带方法1.栈的创建 stacklist=2.字母A、B入栈 stacklist.append(“A”)stacklist.append(“B”)3.输出栈顶元素 print(stacklist1)4.输出栈中元素个数 print(len(stacklist)5.弹出栈顶元素 stacklist.pop()stacklistAB练习练习【举一反三1】有如下Python程序段:num=int(input(“请输入一个整数-128,127:”)st=if num=0:fo
8、r i in range(7):st.append(str(num%2)num/=2 st.append(0)else:num=-num for i in range(7):st.append(str(1-num%2)num/=2 st.append(1)print(.join(st:-1)则当输入26时,程序输出结果为（）A.10011010B.11100101C.0001 1010D.11010C练习练习【举一反三2】有如下Python程序段:s=0123456789ABCDEF“a=“1A2B”ans=for ch in a:num=s.index(ch)st=for i in rang
9、e(4):st.append(str(num%2)num/=2 ans.append(.join(st:：-1)print(.join(ans)则程序执行后,输出的结果为()A.0001101000101011B.1101000101011C.100001010100110D.11010101011A练习练习【举一反三1】有如下Python程序段:if_name_=_main_ st=LinkStack()num=72 while num0:st.push(num%2)num/=2 while not st.is_empty():print(st.pop(),end=)则程序输出结果为_。10
10、01000PART4 4逆波兰表达式问题逆波兰表达式问题一一 生成逆波兰表达式生成逆波兰表达式在数学表达式中，运算符总是在与之相关的两个运算符之间，在计算结果时，要考虑括号、运算符号优先性。为了程序实现方便，波兰逻辑学家J.Lukasiewicz提出了另一种方法，将运算符置于其运算对象之后，没有括号，不用考虑运算符号优先性，这种方式称为逆波兰表达式。a+ba b+6+(7-1)6 7 1-+A*B*CA B*C*一一 练习：中缀转后缀练习：中缀转后缀 C-A*B A*(B+C)-D-A+B-C+D 6+(8-2)*2/3 5*(17-3)+9(2+3)*5-6*4CAB*-ABC+*D-A-B
11、+C-D+6 8 22*3/+5 17 3-*9+2 3+5*6 4*-一一 中缀转后缀中缀转后缀中缀表达式：9+（3-1）*3+10/2后缀表达式：栈9+(-3 1-*3*+10+/2/+一一 中缀转后缀中缀转后缀def translate(inorde_ exp):operators=()+-*/“priority=(:1,+:2,-:2,*:3,/:3 st=#当作栈使用,用来存储运算符 postorde_exp=“用来存储逆波兰表达式”exp_list=inorde_exp.split()for x in exp_list:if x not in operators:elif len(
12、st)=0 or x=(:elif x=):while st and st-1!=(:postorde_exp.append(st.pop()st.pop()else:while st and priorityst-1=priorityx:postorde_ exp.append(st.pop()st.append(x)while st:postorde_ exp.append()return .join(postorde_exp)postorde_exp.append(x)st.append(x)st.pop(x)二二 逆波兰表达式程序实现逆波兰表达式程序实现中缀表达式：9+（3-1）*3+10/2后缀表达式：9 3 1-3*+10 2/+二二 逆波兰表达式程序实现逆波兰表达式程序实现中缀表达式：9+（3-1）*3+10/2后缀表达式：9 3 1-3*+10 2/+9311b=a=3PART5 5火车进出站问题火车进出站问题一一 火车进出站火车进出站14BD一一 火车进出站火车进出站14一一 火车进出站火车进出站BDTHANKSTHANKS
