资源简介 (共33张PPT)3.3栈情景导入PART1栈的概念与特性一 栈的概念与特性栈是一种操作受限的线性表,仅允许在表的一端的进行插入和删除蓝莓味葡萄味草莓味栈顶栈底蓝莓味葡萄味草莓味哈密瓜味推入弹出进行插入或删除操作的一端称为栈顶,位于栈顶位置的元素称为栈顶元素;相应地,将表的另一端称为栈底,位于栈底位置的元素为栈底元素。一 栈的概念与特性(1)先进后出、后进先出(last in first out ,故栈也称为后进先出表(LIFO表))由栈的定义可知,栈具备“先进后出、后进先出”的特点。(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、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栈的基本操作一 栈的基本操作1.栈的创建栈的创建方式有很多种(链栈、顺序栈),一般按照顺序存储,可以用数组来实现。由于栈顶元素在数组中的位置会发生改变,因此用top变量来记录栈顶元素在数组中的位置。当top为-1时,表示栈为空。st=[“”]*4top=-1sttop=-1一 栈的基本操作2.入栈入栈又叫压栈操作,把数据元素压入栈顶。字母“A”、“B”、“C”、“D”依次入栈。sttop=-1top=top+1st[top]=“A”topABCD一 栈的基本操作3.出栈操作出栈时把栈顶元素取出,同时top减一,当top为-1时,表示栈为空。sttop=-1print(st[top])top=top-1topABCD练习【例1】下列代码段能够实现分离正整数,并输出其各位数字(用空格隔开)的功能。请在划线处填入合适的代码。st=[0]* 10#创建一个空栈top=-1num=int(input(“请输入一个正整数:"))while num>0:①st[top]= ②num=num//10print("输出结果为:",end="")while top>-1:print( ③,end=" ")top-=1top+=1num%10st[top]例题11.十进制转二进制st=[-1]*100 #列表中元素初始值-1top=-1number=int(input("请输入十进制整数: "))while number>0:x=number % 2____________________________ #入栈number=number // 2while top>-0:print(st[top],end=‘’) #出栈______________top=top+1st[top]=xtop=top-1例题22.括号匹配在一个数学计算式“(a÷(b-c)+d)×e”中,位置1和位置4有左括号“(", 位置9和位置12有右括号“)”。 位置1的左括号与位置12的右括号相匹配,位置4的左括号与位置9的右括号相匹配。而对于数学计算式“a÷(b-c))",位置8的右括号没有可匹配的左括号。设计一个程序,判断输入的数学计算式中的括号(只有小括号)是否匹配。( ( ) )( ) )(()) ) ( (数量、位置例题22.括号匹配st-=[""]* 100top=-1flag=True #标记是否有不匹配的情况s=input("请输入数学计算式: ")for i in range(len()):if s[i]=="(":________________________elif s[i]== ")":if top==-1:____________breakelse:____________iftop>=0: #栈中还有左括号flag=Falseif flag:print("括号匹配”)else:print("括号不匹配")top=top+1st[top]=s[i]flag=Falsetop=top-1PART3列表自带函数实现栈列表自带方法1.栈的创建stacklist=[]2.字母A、B入栈stacklist.append(“A”)stacklist.append(“B”)3.输出栈顶元素print(stacklist[1])4.输出栈中元素个数print(len(stacklist))5.弹出栈顶元素stacklist.pop()……stacklistAB练习【举一反三1】有如下Python程序段:num=int(input(“请输入一个整数[-128,127]:”))st=[]if num>=0:for i in range(7):st.append(str(num%2))num//=2st.append("0")else:num=-numfor i in range(7):st.append(str(1-num%2))num//=2st.append("1")print(".join(st[::-1]))则当输入26时,程序输出结果为( )A.10011010 B.11100101 C.0001 1010 D.11010C练习【举一反三2】有如下Python程序段:s="0123456789ABCDEF“a=“1A2B”ans=[]for ch in a:num=s.index(ch)st=[]for i in range(4):st.append(str(num%2))num//=2ans.append(".join(st[::-1]))print(".join(ans))则程序执行后,输出的结果为( )A .0001101000101011 B.1101000101011C.100001010100110 D.11010101011A练习【举一反三1】有如下Python程序段:if__name__==__main__st=LinkStack()num=72while num>0:st.push(num%2)num//=2while not st.is_empty():print(st.pop(),end="")则程序输出结果为_________________。1001000PART4逆波兰表达式问题一 生成逆波兰表达式在数学表达式中,运算符总是在与之相关的两个运算符之间,在计算结果时,要考虑括号、运算符号优先性。为了程序实现方便,波兰逻辑学家J.Lukasiewicz提出了另一种方法,将运算符置于其运算对象之后,没有括号,不用考虑运算符号优先性,这种方式称为逆波兰表达式。a + ba b +6+(7-1)6 7 1 - +A * B * CA B * C *一 练习:中缀转后缀C-A*BA*(B+C)-D-A+B-C+D6+(8-2)*2/35*(17-3)+9(2+3)*5-6*4CAB*-ABC+*D-A-B+C-D+6 8 2–2*3/+5 17 3-*9+2 3+5*6 4*-一 中缀转后缀中缀表达式:9+(3-1)*3+10/2后缀表达式:栈9+(-31-*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(st)==0 or x=="(":②elif x==")":while st and st[-1]!="(":postorde_exp.append(st.pop())st.pop()else:while st and priority[st[-1]>=priority[x]: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火车进出站问题一 火车进出站14BD一 火车进出站14卡特兰数:一 火车进出站BDTHANKS 展开更多...... 收起↑ 资源预览