栈 课件【考点打靶+定向训练】浙教版（2019）高中信息技术选修1

3.3栈栈：一种操作受限的线性表，仅允许在表的一端进行插入或删除。进行插入或删除操作的一端称为栈顶，位于栈顶位置的元素称为栈顶元素；相应地，将表的另一端称为栈底，位于栈底位置的元素为栈底元素。栈的特性1.先进后出、后进先出赵六王五李四张三栈顶栈底最后入栈的“赵六”最先出栈，最先入栈的“张三”最后出栈2.有限序列性栈可以是空的，也可以包含多个元素。栈中元素呈现线性关系，栈顶元素有一个前驱点，栈底元素有一个后继点，其他元素既有一个前驱点，又有一个后继点。栈与队列有什么相同点和不同点？相同点：都是一种操作受限的线性表，都具有有限序列性的特点。不同点：队列中的元素具有先进先出、后进后出的特点，栈中的元素则具有先进后出、后进先出的特点。栈的基本操作栈，一般按顺序结构存储，可以用数组实现。由于栈顶元素在数组中的位置会发生改变，因此使用top变量来记录栈顶元素在数组中的位置。如下图所示，①图为栈结构，②图为用数组st存储该栈。CBA栈顶：top=2栈底：ABC数组st012top栈的存储①②栈的常用操作有建栈、入栈、出栈等。1.建栈在Python中，当要存储n个元素的栈时，可以用列表创建一个长度为n的栈。例如，要使4个字母“A”“B”“C”“D”按序入栈、出栈，可以建一个长度为4的栈st，元素初始值均为空串。为了操作方便，把指向栈顶元素的指针变量top值设置为-1。Python代码实现如下：top=-1st=[“”]*42.入栈、出栈入栈又叫压栈操作，把数据元素压入栈顶。每次入栈时，栈顶指针变量top值加1，再给st[top]赋值。字母“A”“B”“C”“D”按序入栈的过程如下图所示。0123空栈top=-1ABACBADCBAtop0123top1023top2013top3012满栈④②③①⑤st栈的入栈过程Python代码实现如下：top=top+1#top=0st[top]=“A”#字母A入栈top=top+1#top=1st[top]=“B”#字母B入栈top=top+1#top=2st[top]=“C”#字母C入栈top=top+1#top=3st[top]=“D”#字母D入栈出栈时把栈顶元素取出，同时top值减1。如果栈中没有元素时，即top=-1，不能进行出栈操作。Python代码实现如下：whiletop>-1:print(st[top])top-=1编号为1、2、3、4的4列火车，按顺序开进一个栈式结构的站点。问：开出火车站的顺序有多少种？请写出所有可能的出栈序列。进入栈中的元素可停留、可出栈（1）出栈序列以火车“①”开头为例，只能是“①”进“①”出，剩下“②③④”，则有：出入栈方式出栈序列②进②出，③进③出，④进④出①②③④②进②出，③进，④进④出，③出①②④③②进，③进③出，②出，④进④出①③②④②进，③进③出，④进④出，②出①③④②②进，③进，④进④出，③出，②出①④③②出栈序列以火车“②”开头为例，只能是“①”进，“②”进，“②”出，剩下“③④”入栈，则有：出入栈方式出栈序列①出，③进③出，④进④出②①③④①出，③进，④进④出，③出②①④③③进③出，①出，④进④出②③①④③进③出，④进④出，①出②③④①③进，④进④出，③出，①出②④③①出栈序列以火车“③”开头为例，只能是“①”进，“②”进，“③”进，“③”出，剩下“④”，则有：出入栈方式出栈序列②出，①出，④进④出③②①④②出，④进④出，①出③②④①④进④出，②出，①出③④②①出栈序列以火车“④”开头为例，只能是“①”进，“②”进，“③”进，“④”进，“④”进，“④”出，则有：④③②①。栈的应用实例将一个十进制数转换为二进制数，根据入栈、出栈的步骤，采用Python编写的完整程序及测试结果如下所示：st=[-1]*100#列表中元素初始值为-1top=-1number=int(input(“请输入十进制整数：”))whilenumber>0:x=number%2top=top+1st[top]=x#入栈number=number//2whiletop>=0:print(st[top],end=“”)#出栈top=top-1请输入十进制整数：13输出：1101拓展链接用列表自带的函数和方法实现的栈Python中用列表自带的函数和方法可以实现建栈、入栈、出栈、栈中元素个数的统计等操作。例如：stacklist=[]#建立一个空栈liststacklist.append(“A”)#字母A入栈stacklist.append(“B”)#字母B入栈print(stacklist[1])#输出栈顶元素，为字母Bprint(len(stacklist))#输出栈中元素的个数，为2stacklist.pop()#弹出栈顶元素print(len(stacklist))#输出栈中元素的个数，为1，是字母A练一练1.有如下Python程序段：a=[0]*5b=[“A”,”B”,”C”,”D”,”E”]top=-1whiletop<4:top=top+1iftop%2==0:a[top]=b[top]else:a[top]=topforiinrange(2):a.pop()top=top-1print(a,top)程序运行结束后，输出的内容是：A.[“A”,”B”,”C”]3B.[“A”,”B”,”C”]2C.[“A”,1,”C”]3D.[“A”,1,”C”]2D2.给定一个字符串，删除相邻重复项。例如，字符串“accdbbdca”删除相邻重复项的结果为“aca”。实现上述功能的python程序如下：S=input(“请输入一个字符串：”)stack=[]#定义一个栈foriinS:if______①________:#如果当前栈为空stack.append(i)elifi==stack[-1]:#如果当前元素与栈顶元素相等_______②________#删除else:_