第三章　字符串、队列和栈-队列和栈复习课件　 浙教版(2019)高中信息技术选修1　

队列和栈复习浙教版新教材(2019)《数据与数据结构》选择性必修1——3.2+3.3队列和栈复习一、队列的概念及特性★概念：一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。★特性：〠先进先出、后进后出

〠有限序列性——队列是一种线性表结构，元素个数有限。队列可以为空。

一、栈的概念及特性★概念：一种操作受限的线性表，仅允许在表的一端进行插入或删除。进行插入或删除操作的一端称为栈顶，位于栈顶位置的元素称为栈顶元素；相应地，将表的另一端称为栈底，位于栈底位置的元素为栈底元素。★特性：〠先进后出、后进先出

〠有限序列性——栈是一种线性表结构，元素个数有限。栈可以为空。

课堂练习1.下列事件执行过程与队列特征不相符的是（）

A.在汽车加油站排队加油时不允许插队

B.当主机运行速度与打印机的打印速度不匹配时，为打印机设置一个打印数据缓冲区

C.把书叠放成一摞，最底下的书要最后才能拿出来

D.CPU分时系统可以根据用户请求，按顺序快速运行各程序段，实现多用户“同时”工作的假象C课堂练习

2.下列事件操作的原理与栈的特征不相符的是（）

A.杂技演员表演叠罗汉时，最后上去的人总是第一个下来

B.在word、photoshop等文档或图像编辑软件中，执行“撤销”操作

C.在火车站排队买票或者在超市排队购票

D.多个函数嵌套调用时，按照“后调用先返回”的原则进行C课堂练习3.设栈s的初始状态为空，元素a,b,c,d,e,f,g,依次入栈，入栈和出栈可以交替进行，且7个元素的出栈顺序为b,d,c,f,e,a,g,则栈s的容量至少应该为（）

A.1B.2C.3D.4C二、栈和队列的基本操作存储建队入队出队存储建栈入栈出栈存储★队列的存储结构：顺序结构存储（线性表结构），可以用数组来实现，也可用链表来实现。〄头指针head:记录队首元素位置〄尾指针tail:记录队尾元素的下一个位置〄初始时为空列表时，head和tail均记录下标为0的位置★栈的存储结构：顺序结构存储（线性表结构），可以用数组来实现。〄栈顶指针top:记录当前栈顶元素位置〄初始时为空栈时，top值为-1存储建队建队1：head=0tail=0que=[""]*6建栈1：top=-1stack=[""]*6建栈建队2：head=0tail=0que=[0]*6建队3：head=0tail=0que=[]建栈2：top=-1stack=[0]*6建栈3：top=-1stack=[]#入队1foriin“亚洲足球崛起”：que[tail]=i

tail+=1#入栈1：foriin“亚洲足球崛起”：top+=1stack[top]=i入队入栈#入队2foriinrange(1,20,3)：que[tail]=i

tail+=1#入队3foriinrange(1,20,3)：que.append(i)#入栈2：foriinrange(1,20,3)

：top+=1stack[top]=i#入栈3：foriin“亚洲足球崛起”：

stack.append(i)#出队1、2whilehead!=tail:print(que[head])head+=1#出栈1、2：while

top>-1:print(stack[top])top-=1出队出栈#出队3head=0whilelen(que)!=0:print(que.pop(head))

head+=1#出栈3：whilelen(stack)!=0:print(stack.pop())top!=-1#建队head=tail=0que=[""]*6#入队foriin“中国男足加油”：que[tail]=i

tail+=1#出队whilehead!=tail:print(que[head])head+=1Print(que)#建栈：top=-1stack=[""]*6#入栈：foriin“中国男足加油”：top+=1stack[top]=i#出栈：while

top>-1:

print(stack[top])

top-=1Print(stack)测试1VS#建队head=tail=0que=[]#入队foriin“伊朗真真不错":que.append(i)#出队tail=len(que)whilelen(que)!=0:print(que.pop(head))print(que)#建栈：top=-1stack=[]#入栈：foriin“伊朗真真不错":stack.append(i)#出栈：whilelen(stack)!=0:print(stack.pop())print(stack)VS测试2课堂练习3.判断一个长度为n的队列q为空的条件是（）

A.head==0B.tail==0

C.tail==-1

D.head==tailD4.用python列表模拟队列，并设置队头指针head指向队首元素，队尾指针tail指向队尾元素的下一个位置，则当head=3，tail=6时，队列中元素的个数为（）

A.3B.4C.5D.6 A课堂练习书P30D课堂练习有如下python程序段，使用长度为3的列表q模拟队列的出队入队活动：q=[1,2,3]ys=[]foriinrange(4,10):

ys.append(q[0])

q[0]=q[1]

q[1]=q[2]

q[2]=iprint(ys,q)程序运行结束后，列表ys中元素的数量为___________。6课堂练习例：信息的加密1.将字符串各字符依次入队，得到队列。s=input(“请输入字符串：”)que=[""]*100head=0tail=0foriinrange(len(s)):que[tail]=s[i]tail+=1给定一个字符串S1,S2,…..Sn，按如下过程加密：取出第一个字符S1，将第二个字符S2放到字符串的末尾Sn后面，得到字符串S3…..Sn,S2；接着把S3取出，S4放到字符串的末尾S2后面，直到最后一个字母Sn被取出。这些字母按取出的顺序形成一个新的字符串，称为密串，请编写一个加密程序，输入一个字符串（长度小于等于100），输出该字符串的密串。2.以“STRING”为例，该字符串压入队列后先取出队首元素“S”并输出，同时head+1，队首元素变为“T”再取出“T”，加入到队尾，队首变为“R”，队尾变为“T”，head和tail均加1重复以上操作，直至队列为空队列que索引01234567891011headtailSTRING取出ST取出RI取出NG取出TI取出GI取出Ihead=tail队列清空用数组（列表）模拟的队列真的清空了么？程序运行结束后，输出的内容是()课堂练习有如下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)DA.[“A”,”B”,”C”]3

B.[“A”,”B”,”C”]2C.[“A”,1,”C”]3D.[“A”,1,”C”]2课堂练习在利用栈来判断一个表达式中的括号（只有小括号）是否匹配的过程中，当遇到表达式中的一个左括号时，就让它进栈，遇到一个右括号时，就对栈进行一次出栈操作，当栈最后为空时，表示括号是配对的，否则是不配对的，现有表达式“（a+b）*c+（（d-e）*f+g）*h”，针对该表达式设计栈的大小，至少为（）A.1B.2C.3D.4B课堂练习st-=[""]*100;top=-1flag=True #标记是否有不匹配的情况s=input("请输入数学计算式:")foriinrange(len(s)):ifs[i]=="(": ____________ ____________elifs[i]==")":iftop==-1:____________breakelse:____________iftop>=0:flag=False#栈中还有左括号ifflag:print("括号匹配”)else:print("括号不匹配")top=top+1st[top]=s[i]flag=Falsetop=top-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字符串的实现方法？空列表的实现方法？数组？算法思想：1）用栈结构存放每次获得的余数

2）根据栈特征输出每次获得的余数课堂练习下列代码段能够实现分离正整数,并输出其各位数字(用空格隔开)的功能。请在划线处填入合适的代码。st=[0]*10#创建一个空栈top=-1num=int(input(“请输入一个正整数:"))whilenum>0:

①st[top]=

②num=num//10print("输出结果为:",end="")whiletop>-1:print(③，end="")top-=1top+=1num%10st[top]课堂练习给定一个字符串，删除相邻重复项。例如，字符串“accdbbdca”删除相邻重复项的结果为“aca”。实现上述功能的python程序如下：S=input(“请输入一个字符串：”)stack=[]#定义一个栈foriinS:

if

_____________:#如果当前栈为空

stack.append(i)elifi==stack[-1]:#如果当前元素与栈顶元素相等

________#删除else:

_________print(stack)（1）当输入的字符串为“hdjjsaad”时，输出的stack的值为__________。（2）请在划线处填入合适的代码。[‘h’,’d’,’s’,’d’]stack==[]stack.pop()stack.append(i)字符串的实现方法？【举一反三1】有如下Python程序段:num=int(input(“请输入一个整数[-128,127]:”))st=[]ifnum>=0:foriinrange(7):st.append(str(num%2))num//=2st.append("0")else:num=-numforiinrange(7):st.append(str(1-num%2))num//=2st.append("1")print(".join(st[::-1]))则当输入26时,程序输出结果为（

）A.10011010 B.11100101 C.00011010 D.11010C练一练【举一反三2】有如下Python程序段:s="0123456789ABCDEF“a=“1A2B”ans=[]forchina:num=s.index(ch)st=[]foriinrange(4):st.append(str(num%2))num//=2ans.append(".join(st[::-1]))print(".join(ans))则程序执行后,输出的结果为( )A.0001101000101011 B.1101000101011 C.100001010100110 D.11010101011A练一练【举一反三3】有如下Python程序段:if__name__==__main__st=LinkStack()num=72whilenum>0:st.push(num%2)num//=2whilenotst.is_empty():print(st.pop(),end="")则程序输出结果为_________________。1001000练一练三、循环队列头啊付月月章鼎昊李帅宋炜涛陈悦head=0tail=6head=6定义的列表是否为空？是否能入队？循环队列：将队列的队首和队尾连接起来，形成逻辑上的环状结构。当对循环队列中的元素进行入队、出队操作时，队首指针变量和队尾指针变量可以循环指向所有位置，从而有效地解决队列中“有空闲位置却不能入队”的问题。尝试设计三、循环队列#建队head=tail=0que=[""]*6#入队foriin[“头啊“,“付月月“,”章鼎昊“,”李帅“,”宋炜涛“,”陈悦“]：que[tail]=i

tail+=1#出队whilehead!=tail:print(que[head])head+=1付月月章鼎昊李帅宋炜涛陈悦头啊#建队head=tail=0que=[""]*6#入队foriin[“头啊“,“付月月“,”章鼎昊“,”李帅“,”宋炜涛“,”陈悦“]：que[tail]=i

tail=(tail+1)%len(que)#出队while

?:

print(que[head])

head=(head+1)%len(que)三、循环队列数组中预备一个空闲单元importrandom#建队head,tail=0,0que=[0]*6#入队Whilehead!=(tail+1)%len(q):

q[tail]=random.randint(1,9)

tail=(tail+1)%len(q)#出队while