资源简介

(共36张PPT)
队列和栈复习
浙教版新教材(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.1 B.2 C.3 D.4
C
二、栈和队列的基本操作
存储
建队
入队
出队
存储
建栈
入栈
出栈
存储
★ 队列的存储结构：顺序结构存储（线性表结构），可以用数组来实现，也可用链表来实现。
头指针head: 记录队首元素位置
尾指针tail: 记录队尾元素的下一个位置
初始时为空列表时，head和tail 均记录下标为0的位置
★ 栈的存储结构：顺序结构存储（线性表结构），可以用数组来实现。
栈顶指针top: 记录当前栈顶元素位置
初始时为空栈时，top值为-1
存储
建队
建队1：
head=0
tail=0
que=[""]*6
建栈1：
top=-1
stack=[""]*6
建栈
建队2：
head=0
tail=0
que=[0]*6
建队3：
head=0
tail=0
que=[]
建栈2：
top=-1
stack=[0]*6
建栈3：
top=-1
stack=[]
#入队1
for i in “亚洲足球崛起”：
que[tail]=i
tail+=1
#入栈1：
for i in “亚洲足球崛起” ：
top+=1
stack[top]=i
入队
入栈
#入队2
for i in range(1,20,3)：
que[tail]=i
tail+=1
#入队3
for i in range(1,20,3)：
que.append(i)
#入栈2：
for i in range(1,20,3) ：
top+=1
stack[top]=i
#入栈3：
for i in “亚洲足球崛起” ：
stack.append(i)
#出队1、2
while head!=tail:
print(que[head])
head+=1
#出栈1、2：
while top>-1:
print(stack[top])
top-=1
出队
出栈
#出队3
head=0
while len(que)!=0:
print(que.pop(head))
head+=1
#出栈3：
while len(stack)!=0:
print(stack.pop())
top!=-1
#建队
head=tail=0
que=[""]*6
#入队
for i in “中国男足加油”：
que[tail]=i
tail+=1
#出队
while head!=tail:
print(que[head])
head+=1
Print(que)
#建栈：
top=-1
stack=[""]*6
#入栈：
for i in “中国男足加油” ：
top+=1
stack[top]=i
#出栈：
while top>-1:
print(stack[top])
top-=1
Print(stack)
测试1
VS
#建队
head=tail=0
que=[]
#入队
for i in “伊朗真真不错":
que.append(i)
#出队
tail=len(que)
while len(que)!=0:
print(que.pop(head))
print(que)
#建栈：
top=-1
stack=[]
#入栈：
for i in “伊朗真真不错":
stack.append(i)
#出栈：
while len(stack)!=0:
print(stack.pop())
print(stack)
VS
测试2
课
堂
练
习
3.判断一个长度为n的队列q为空的条件是（ ）
A.head==0 B.tail==0 C.tail==-1 D.head==tail
D
4. 用python列表模拟队列，并设置队头指针head指向队首元素，队尾指针tail指向队尾元素的下一个位置，则当head=3，tail=6时，队列中元素的个数为（ ）
A.3 B.4 C.5 D.6
A
课
堂
练
习
书P30
D
课
堂
练
习
有如下python 程序段，使用长度为3的列表q模拟队列的出队入队活动：
q=[1,2,3]
ys=[]
for i in range(4,10):
ys.append(q[0])
q[0]=q[1]
q[1]=q[2]
q[2]=i
print(ys,q)
程序运行结束后，列表ys中元素的数量为___________。
6
课
堂
练
习
例：信息的加密
1. 将字符串各字符依次入队，得到队列。
s=input(“请输入字符串：”)
que=[""]*100
head=0
tail=0
for i in range(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
索引 0 1 2 3 4 5 6 7 8 9 10 11
head
tail
S
T
R
I
N
G
取出
S
T
取出
R
I
取出
N
G
取出
T
I
取出
G
I
取出
I
head=tail
队列清空
用数组（列表）模拟的队列真的清空了么？
程序运行结束后，输出的内容是( )
课
堂
练
习
有如下Python程序段：
a=[0]*5
b=["A","B","C","D","E"]
top=-1
while top<4:
top=top+1
if top%2==0:
a[top]=b[top]
else:
a[top]=top
for i in range(2):
a.pop()
top=top-1
print(a,top)
D
A.[“A”,”B”,”C”]3 B.[“A”,”B”,”C”]2
C.[“A”,1,”C”]3 D.[“A”,1,”C”]2
课
堂
练
习
在利用栈来判断一个表达式中的括号（只有小括号）是否匹配的过程中，当遇到表达式中的一个左括号时，就让它进栈，遇到一个右括号时，就对栈进行一次出栈操作，当栈最后为空时，表示括号是配对的，否则是不配对的，现有表达式“（a+b）*c+（（d-e）*f+g）*h”，针对该表达式设计栈的大小，至少为（ ）
A.1 B.2 C.3 D.4
B
课
堂
练
习
st-=[""]* 100 ; top=-1
flag=True #标记是否有不匹配的情况
s=input("请输入数学计算式: ")
for i in range(len(s)):
if s[i]=="(":
____________
____________
elif s[i]== ")":
if top==-1:
____________
break
else:
____________
if top>=0: flag=False #栈中还有左括号
if flag: print("括号匹配”)
else: print("括号不匹配")
top=top+1
st[top]=s[i]
flag=False
top=top-1
课
堂
练
习
将一个十进制数转换为二进制数，根据入栈、出栈的步骤，
采用Python编写的完整程序及测试结果如下所示：
st=[-1]*100 #列表中元素初始值为-1
top=-1
number=int(input(“请输入十进制整数：”))
while number>0:
x=number%2
top=top+1
st[top]=x #入栈
number=number//2
while top>=0:
print(st[top],end=“”) #出栈
top=top-1
请输入十进制整数：
13
输出：
1101
字符串的实现方法？空列表的实现方法？数组？
算法思想： 1）用栈结构存放每次获得的余数
2）根据栈特征输出每次获得的余数
课
堂
练
习
下列代码段能够实现分离正整数,并输出其各位数字(用空格隔开)的功能。请在划线处填入合适的代码。
st=[0]* 10 #创建一个空栈
top=-1
num=int(input(“请输入一个正整数:"))
while num>0:
①
st[top]= ②
num=num//10
print("输出结果为:",end="")
while top>-1:
print( ③，end=" ")
top-=1
top+=1
num%10
st[top]
课
堂
练
习
给定一个字符串，删除相邻重复项。例如，字符串“accdbbdca”
删除相邻重复项的结果为“aca”。实现上述功能的python程序如下：
S=input(“请输入一个字符串：”)
stack=[] #定义一个栈
for i in S:
if _____________: #如果当前栈为空
stack.append(i)
elif i==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=[]
if num>=0:
for 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.10011010 B.11100101 C.0001 1010 D.11010
C
练一练
【举一反三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//=2
ans.append(".join(st[::-1]))
print(".join(ans))
则程序执行后,输出的结果为( )
A .0001101000101011 B.1101000101011
C.100001010100110 D.11010101011
A
练一练
【举一反三3】有如下Python程序段:
if__name__==__main__
st=LinkStack()
num=72
while num>0:
st.push(num%2)
num//=2
while not st.is_empty():
print(st.pop(),end="")
则程序输出结果为_________________。
1001000
练一练
三、循环队列
头啊
付月月
章鼎昊
李帅
宋炜涛
陈悦
head=0
tail=6
head=6
定义的列表是否为空？是否能入队？
循环队列： 将队列的队首和队尾连接起来，形成逻辑上的环状结构。
当对循环队列中的元素进行入队、出队操作时，队首指针变量和队尾指针变量可以循环指向所有位置，从而有效地解决队列中“有空闲位置却不能入队”的问题。
尝试设计
三、循环队列
#建队
head=tail=0
que=[""]*6
#入队
for i in [“头啊“, “付月月“, ”章鼎昊“, ”李帅“, ”宋炜涛“, ”陈悦“]：
que[tail]=i
tail+=1
#出队
while head!=tail:
print(que[head])
head+=1
付月月
章鼎昊
李帅
宋炜涛
陈悦
头啊
#建队
head=tail=0
que=[""]*6
#入队
for i in [“头啊“, “付月月“, ”章鼎昊“, ”李帅“, ”宋炜涛“, ”陈悦“]：
que[tail]=i
tail=(tail+1)%len(que)
#出队
while :
print(que[head])
head=(head+1)%len(que)
三、循环队列
数组中预备一个空闲单元
import random
#建队
head,tail=0,0
que=[0]*6
#入队
While head!=(tail+1)%len(q):
q[tail]=random.randint(1,9)
tail=(tail+1)%len(q)
#出队
while head!=tail:
print(que[head])
head=(head+1) %len(q)
三、循环队列
课
堂
练
习
C
课
堂
练
习
已知队列元素的个数为6，则队首指针head和队尾指针tail的值不可能的是（ ）
A.head=0，tail=6 B. head=6，tail=0
C. head=3，tail=2 D. head=3，tail=8
D
10
课
堂
练
习
课
堂
练
习
(head+1)% n
或其他等价答案
q[tail]=q[head]
c=0
课
堂
练
习
例：信息的加密的循环队列实现
1. 将字符串各字符依次入队，得到队列。
s=input(“请输入字符串：”)
que=[""]*100
head=0
tail=0
for i in range(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
重复以上操作，直至队列为空
谢谢配合
浙教版新教材(2019)《数据与数据结构》选择性必修1——3.2+3.3 队列和栈复习

展开更多......

收起↑