资源简介

(共78张PPT)
课时3　栈
第三章　字符串、队列和栈
1.通过问题解决，理解栈的概念和特性。2.掌握栈的基本操作，并能编程实现。
目 录
CONTENTS
知识梳理
01
例题精析
02
随堂检测
03
巩固与提升
04
知识梳理
1
1.栈的概念
(1)栈也是一种操作受限的线性表，仅允许表的______进行插入或删除操作。
(2)进行插入或删除操作的一端称为______，位于栈顶位置的元素称为栈顶元素；表的另一端为______，位于栈底位置的元素称为栈底元素。
一端
栈顶
栈底
2.栈的特性
(1)____________或____________。
(2)_______________。
栈可以是空的，也可以包含多个元素。
3.栈的基本操作
(1)栈的创建
在存储n个元素的栈时，可以用列表创建一个长度为n的栈。
(2)入栈(push)、出栈(pop)
入栈操作：入栈也叫______操作，把数据元素压入栈顶，每次入栈时，栈顶指针变量top值______，再给st[top]赋值。
先进后出
后进先出
有限序列性
压栈
加1
出栈操作：出栈时把栈顶元素取出，同时__________________。如果栈中没有元素时，即top＝－1，不能进行出栈操作。
top值减1
4.使用列表模拟栈操作
a＝[]　#建栈
a.append(″data1″)　#入栈
a.append(″data2″)　#入栈
a.append(″data3″)　#入栈
print(a.pop())　#出栈
print(a.pop())　#出栈
print(a.pop())　#出栈
5.建立stack类并进行栈操作
class Stack()：
def_ _init_ _(self)：　#建栈
self.my_stack＝[]
def push(self，data)：　#入栈
self.my_stack.append(data)
def pop(self)：　#出栈
return self.my_stack.pop()
def size(self)：　#栈空判断
return len(self.my_stack)
def isEmpty(self)：
return self.my_stack＝＝[]
stack＝Stack()
a＝[″data1″，″data2″，″data3″]
for item in a：　#入栈
stack.push(item)
print(″栈中元素个数为：″，stack.size())
while not stack.isEmpty(): #出栈
print(stack.pop())
例题精析
2
例1 若某栈的容量是 3，即栈内最多只能容纳 3 个元素，若其某个出栈序列是a，b，c，d，e，那么它可能的入栈序列是(　　)
A.c，b，a，e，d B.d，c，b，a，e
C.b，c，a，e，d D.a，e，d，c，b
A
解析　A选项c，b，a依次入栈，a，b，c依次出栈，接着e，d入栈后再出栈。B选项a要出栈，d，c，b，a需入栈，栈空间超过3。C选项b先于c入栈，则c需先出栈。D选项a入栈并出栈后，剩余4个元素入栈，超过栈容量。
变式训练　有1个栈初始为空，其元素入栈顺序依次为s，t，r，w，u，y，m，若经过进栈和出栈操作后，栈底至栈顶元素分别为t，w，y，则第3个出栈元素为(　　)
解析　根据栈的特性，在栈中元素后进先出，因此第1个入栈和出栈的元素是s，第3个入栈第2个出栈的元素是r，第5个入栈第3个出栈的元素是u。
C
A.m B.w C.u D.s
例2 公交车上有时候会出现人太多无法挤到后门下车而从前门下车的情况，因此若一个序列在有3个或以下元素时按队列方式离开序列，但在3个以上元素时按栈方式离开序列，则对于依次进入序列的xl，x2，x3，x4，x5，x6，离开序列的顺序可能为(　　)
A.x1，x4，x6，x2，x3，x5 B.x4，x1，x6，x2，x3，x5
C.x1，x2，x3，x6，x4，x5 D.x6，x5，x4，x3，x1，x2
解析　A选项x1小于3个元素按队列方式出列，x4进入序列时，还有x2，x3，x4共3个元素，按队列方式出列，也就是x2出列，如果按栈离开，则必须x5进入序列，那就是x5先出。B选项x4按出栈方式离开，剩下x1，x2，x3，因此x1按队列方式离开。当x5、x6进入序列，x6按出栈方式离开。剩下3个按队列方式离开。C选项x1，x2，x3按队列方式离开，则x4，x5，x6进入序列后只能按队列方式离开。D选项x6先离开，全部元素进入序列，前面3个元素按出栈方式离开，后面3个元素只能是按队列方式离开。
B
变式训练　设栈S和队列Q的初始状态为空，元素x1、x2、x3、x4、x5、x6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序依次为x2、x4、x3、x6、x5、x1，则栈S的容量至少应该为(　　)
A.2 B.3 C.4 D.5
解析　本题主要考查的是栈和队列的特点。栈的特点是先进后出，而队列的特点是先进先出，根据出队顺序可知，出栈的顺序依次为x2、x4、x3、x6、x5、x1，在x2出栈前，栈里的元素为x2和x1，共2个元素；在x4出栈前，栈里的元素为x4、x3和x1，共3个元素； 在x3出栈前，栈里的元素为x3和x1，共2个元素； x6出栈前，栈里的元素为x6、x5和x1，共3个元素； 在元素x5出栈前，栈里的元素为x5、x1，共2个元素，因此，栈的最小容量应为3。
B
例3 有如下 Python 程序段：
s＝input(″输入一个字符串″)
st＝[″″]*6；st[0]＝s[0]
top＝0
for i in range(1，len(s))：
　if top>＝0 and s[i]＝＝st[top]：
　 top－＝1
　else：
　 top＋＝1
　st[top]＝s[i]
print(st[：top＋1])
A.ABABB B.AAABA C.BAABA D.BBABA
解析　本题考查栈的性质。栈初始值有一个元素s[0]，从索引位置1开始遍历s，如果s[i]与栈顶元素相同，进行出栈操作，否则进行入栈操作。A、B和D选项栈中元素有ABA。C选项栈中元素只有A。
C
变式训练　有如下 Python 程序段：
st＝[0]*10
cnt，top＝0，－1
s＝input()
for i in range(0，len(s)，2):
　t＝s[i]
　 n＝int(s[i＋1])
　 if t＝＝'A'：
　 for j in range(n):
　 　　top＋＝1
　 　　　st[top]＝cnt
　　　　cnt＋＝1
　　elif t＝＝'P'：
　while top！＝－1 and n>0:
　　　　top－＝1
　　　n－＝1
print(st[0：top＋1])
若输入 s 的值为″A1P2A3P2A2″，则程序的输出结果是(　　)
A.[5，6] B.[2，5，6]
C.[4，5] D.[1，4，5]
解析　对字符串s两个一组进行遍历，如果t为A，将n个cnt入栈，如果是p，对n个元素进行出栈。0入栈，0出栈，1、2、3入栈，3和2出栈，4、5入栈，因此从栈底到栈顶分别为1，4，5。
D
例4 有如下Python程序段：
import random
a＝['A'，'B'，'#'，'#'，'C'，'D'，'#']
stk＝[0]*len(a)；top＝－1
for i in range(len(a))：
　op＝random.randint(0，1) # 随机生成0或1
　if op＝＝1 and a[i]！＝ '#'：
　　　top＋＝1；stk[top]＝a[i]
　　　　a[i]＝'#'
　　　elif op＝＝0 and top！＝－1 and a[i]＝＝'#'：
　 　　　a[i]＝stk[top]；top－＝1
A.['A'，'B'，'#'，'#'，'C'，'D'，'#'] B.['#'，'#'，'#'，'#'，'#'，'#'，'#']
C.['#'，'B'，'#'，'#'，'C'，'D'，'A'] D.['#'，'#'，'A'，'B'，'C'，'D'，'#']
解析　本题考查栈的应用。若op＝1，且'#'时要入栈，是字母时，if语句与elif语句都不执行。若op＝0，栈不空且a[i]值为'#'，把栈顶值代替当前元素，且进行出栈操作。A选项，当op的值每次都是0时即可实现；B选项，当op的值每次都是1时即可实现；选项C，当op的值依次是1、0、1、1、0、0、0时即可实现。选项D，a[0]、a[1]值是'#'，表明A、B均已入栈，选项不符合出栈顺序。
D
变式训练　有如下 Python 程序段：
import random
p＝″abcde*″；st＝[″″]*len(p)；s＝″″
top＝－1
i＝0
while i<＝5：
　m＝random.randint(0，1)
　 if m＝＝0：
top＋＝1
st[top]＝p[i]
i＋＝1
　elif len(st)>0:
s＋＝st[top]
top－＝1
print(s)
执行上述程序段后，输出结果可能的是(　　)
A.a* B.cdabe
C.abcde* D.cdba
解析　若产生的随机数m值为0，进行入栈操作。否则出栈后并连接到字符串s中。则于最后一个字符*一旦入栈后，i的值为5，结束循环，就不可能出栈。B选项a比b先入栈，出栈顺序应相反。D选项abc先入栈，c出栈，d入栈后出栈，最后a出栈。
D
随堂检测
3
A.a和c B.a和b C.b和d D.c和d
B
解析　a比b先入栈，因此a在b的后面出栈。
2.用I表示入栈操作，0表示出栈操作，若元素入栈的顺序为ABCDE，为了得到ADCEB的出栈顺序，则由I和0表示的操作串是(　　)
A.I0III00I00 B.I0II0I00I0
C.IIII00I000 D.I0III0000
A
解析　A入栈、出栈；BCD入栈，DC出栈；E入栈，EB出栈。
3.利用栈求逆波兰表达式(表达式由操作数和运算符组成)的方法是：从左往右扫描该表达式，遇到操作数时入 栈；遇到运算符时，把处于栈上方的两个元素依次出栈，用运算符计算，并把计算结果压入栈中。如此反复 操作，直至表达式扫描结束。当用该算法求逆波兰表达式abcd－*e/＋f－的值时 (abcdef 表示不同的操作数)，所使用栈的深度至少为(　　)
A.3 B.4 C.5 D.6
B
解析　abcd依次进栈，栈深度为4，遇到“－”，进行c－d操作后，计算结果重新进栈(栈深度为3)，遇到“*”，进行b*(c－d)操作后重新进栈(深度为2)，接着“e”进栈(栈深度为3)最大深度为4。
4.有如下 Python 程序段：
C
st＝[0] * 10
a＝[4，6，1，7，2，8，6]
top＝0; st[top]＝a[0]
for i in range(1，len(a))：
　while top ！＝－1 and a[i]top－＝1
　top＋＝1
　st[top]＝a[i]
执行该程序段后，变量 top 的值为(　　)
A.－1 B.1 C.2 D.3
解析　栈中初始有一个值，从索引位置1开始遍历，当遍历到的数比栈顶小时，将栈顶元素出栈，自身入栈。遍历到1时，让4和6出栈。7入栈，2使得7出栈，8入栈，6使得8出栈，因此栈中有1、2和6共3个元素，top值为2。
5.有如下Python程序段：
a＝[2，1，5，7，3]
n＝len(a)
s1＝[－1]*n；top1＝－1
s2＝[－1]*n；top2＝－1
for i in range(n)：
　while top1！＝－1 and a[i]　 top2＋＝1；s2[top2]＝s1[top1]；top1－＝1
　top1＋＝1；s1[top1]＝a[i]
while top2！＝－1：
　top1＋＝1；s1[top1]＝s2[top2]；top2－＝1
A
A.top1＝＝5 B.top2＝＝－1
C.s1[0]＝＝1 D.s1[3]＝＝7
解析　本题考查栈的基本应用。遍历列表a中数据，若栈s1不空，且s1栈顶元素大于等于a[i]时，不断地将s1中元素出栈，并入栈s2中，将a[i]入栈s1。因此栈s1中元素有1，3，栈s2中有元素[2，7，5]，最后将栈s2中元素出栈并加入到栈s1中，因此栈s1中最终结果为[1，3，5，7，2]。
6.有如下程序段：
s＝list(input(″输入一个字符串s：″)) # list 函数将s 转换为列表
top＝－1
a＝[0]*100
i＝0
while i　if s[i]＝＝'('：
　top＋＝1
　　　a[top]＝i
　elif s[i]＝＝')'：
　 st＝a[top]
　 top－＝1
　s＝s[：st]＋s[i－1：st：－1]＋s[i＋1：]
　i－＝2
　i＋＝1
print(″.join(s)) #将s 中元素以字符连接成一个新的字符串
执行该程序段后，输入“(ed(y(oc))p)”，输出结果是(　　)
A.pycode B.codepy C.pcodey D.copyde
A
解析　本题考查栈的性质和基本操作。遇到'('对应的下标入栈，遇到')'，元素出栈。同时列表元素重新组合，组合原则：二端不动，最内层配对括号内的元素翻转，同时这对括号抛弃。算法过程：
(ed(y(oc))p)→(ed(yco)p)→(edocyp)→pycode。
7.有如下 Python 程序段：
import random
q＝[″A″，″B″，″C″，″D″，″#″]
head，tail＝0，4
s＝[0]*5
top＝－1
for i in range(5):
　t＝random.randint(0，1)　　 #随机生成 0 或 1
　if t＝＝0 and head　top＋＝1；s[top]＝q[head]
　head＋＝1
　elif t＝＝1 and top！＝－1:
　 s[top]＝0；top－＝1
B
解析　本题考查队列和栈的基本操作。A选项t产生全0时，q中队列元素依次出队入栈，最后t＝0且head＝＝tail时，没有任何操作。B选项D要出栈，ABC都入栈且出栈，执行的次数超过5次。C选项t依次产生1，1，1，1，1时q中队列元素不出队也不入栈。D选项t依次产生0，0，1，0，0时AB先后入栈，然后B出栈，最后CD依次入栈。
8.有如下 Python 程序段：
a＝[1，2，3，4，5] ; b＝[3，2，5，1，4]
stack＝[] ; i＝j＝0
while i　stack.append(a[i]) #将 a[i]添加到 stack 末尾
　i＋＝1
　while len(stack)>0 and stack[－1]＝＝b[j]:
　stack.pop() #移除 stack 末尾元素
　j＋＝1
C
执行该程序段后，stack 中的元素个数为(　　)
A.0 B.1 C.2 D.3
解析　stack是一个栈，b是一个队列。遍历数组a，将a[i]进行入栈操作，当栈不为空，且栈顶元素与队首元素相等，不断地将数据进行出栈和出队操作。1，2，3入栈，3，2出栈出队，4，5入栈，5出栈出队，栈中元素有1和4。
4
巩固与提升
基础巩固
能力提升
1.栈s的最大长度为4，初始已有两个元素在栈内，栈底为a，栈顶为b，经过一系列入栈、出栈操作，若元素入栈的顺序是c，d，e，f，则可能的出栈序列为(　　)
A.c，a，b，e，f，d B.b，d，f，e，c，a
C.a，b，d，c，e，f D.b，e，f，c，d，a
B
解析　A选项和C选项都出现了 a 在 b 前面出栈的情况，因此选项错误；D选项f 出栈时栈内的元素为(栈底)c，d(栈顶)，因此不可能 c 出栈，选项错误。
2.有一个队列和一个栈，其中队列中队首到队尾的元素依次为3，15，8，7，栈中栈顶到栈底的元素依次为6，9，12，10。现在有两种操作，操作S是指队列中1个元素出队后入栈，操作Q是栈中1个元素出栈后入队。则经过QSSQSQQS操作后，队列中队首到队尾的元素依次是(　　)
A.6，15，8，3 B.10，15，8，3
C.3，6，15，7 D.3，10，15，7
A
解析　队列特征为先进先出，有4次出队，因此队列中3，15，8，7全部出队。Q出栈入队，因此6先入队，15和3在栈中，接着15入队，8出队入栈，因此后面是8和3。
3.用“除二取余”法将十进制转换为二进制数，用栈的方法操作，需要把得到的余数依次入栈，除尽后再把余数出栈即可。若要将十进制数n(0≤n<64)转换为二进制数，则设置栈的长度至少为(　　)
A.3 B.4 C.5 D.6
D
解析　十进制数n(0≤n＜64)转换为二进制数，得到最大的是6位二进制数。
4.已知栈k的入栈顺序为2，7，3，1，6，9，第2个出栈的是6，第5个出栈的是2，则最后出栈的元素是(　　)
A.7 B.3 C.1 D.9
D
解析　2是第1个入栈，当2出栈时，栈为空，只有9入栈再出栈。
5.已知字符“a”的ASCII码值为97，有如下Python程序段：
que＝[″″]*20
head，tail＝0，0
for i in range(3)：
　que[tail]＝chr(97＋i)
　 tail＋＝1
st＝[″b″，″c″，″d″，″a″]
top＝3
while head－1:
　if st[top]＝＝que[head]：
head＋＝1
A
　else：
que[tail]＝st[top]
tail＋＝1
　top－＝1
print(que[head：tail])
执行该程序段，则输出的结果是(　　)
A.['c'，'d'，'c'] B.['c'，'c'，'d']
C.['c'，″，'d'] D.['c'，'d']
解析　第1个循环让abc依次入队。当队列和栈不为空时，如果栈顶元素和队首元素相同，则进行出队和出栈操作，否则将栈顶元素出栈并入队。栈顶和队首均为″a″，出队和出栈操作，接着″d″入队，″d″出栈，接着″c″入队，″c″出栈，队列中元素为″bcdc″，接着″b″出队和出栈。
6.用栈的思想编写进制转换中的“除二取余法”的Python程序如下：
st＝[－1]*100
top＝－1
n＝int(input(″请输入一个十进制数″))
while n>0：
n∥＝2
while top！＝－1：
　　print(st[top]，end＝″″)
　　top－＝1
D
方框处的代码由以下三条语句组成：①st[top]＝x　②x＝n%2　③top＋＝1下列语句顺序正确的是(　　)
A.①②③ B.①③② C.②①③ D.②③①
解析　入栈必先移动top指针，入栈元素为x，先对x进行除2的余数赋值。
7.有如下Python程序段：
s＝input(″请输入一个仅由小写英文字母组成的字符串：″)
st＝[″″]*len(s)
top＝－1
t＝[－1]*26
for i in range(len(s)):
　id＝ord(s[i])－97
　 if t[id]＝＝－1：
　top＋＝1
　st[top]＝s[i]
　t[id]＝top
　else：
　 first＝t[id]
　while top>＝first and top！＝－1:
　　num＝ord(st[top])－97
　　t[num]＝－1; top－＝1
print(st[：top＋1])
若从键盘输入的值为″hellopython″，则输出的值为(　　)
A.['o'，'n'] B.['h'，'e'，'n']
C.['h'，'e'，'l'，'o'，'p'，'y'，'t'，'n'] D.['h'，'e'，'o'，'p'，'y'，'t'，'h'，'o'，'n']
A
解析　遍历字符串s，将每个字母转换成0～25之间对应的数字。t列表是每个字母出现在栈中位置的桶。若字母不在栈中，将该字母入栈，同时记录该字母为当前栈顶位置。若该字母已经存在于栈中，将后入栈的字母进行出栈操作，并在桶中作－1的标记。最后一个h让前面所有字母出栈，因此栈中只有o和n。
8.有如下Python程序段：
import random
s＝[3，2，7，6，9]
st＝[0]*len(s)
top＝－1；i＝0
while i　op＝random.randint(0，1)
　if top＝＝－1 or op＝＝0 and s[i]>st[top]：
　top＋＝1
　st[top]＝s[i]
B
　elif top>＝1 and op＝＝1 and s[i]>st[top－1]：
　st[top]＝s[i]
　i＋＝1
while top！＝－1：
　　　print(st[top]，end＝″ ″)
　　　top－＝1
解析　本题考查栈的应用。当栈空入栈，因此3肯定在栈中。当op为0且s[i]>st[top]时，s[i]入栈，若产生op的值一直为1，则栈中只有3；入栈的元素比栈中元素大，2小于3，因此2不可能入栈，若7没有入栈，则6可能入栈。
9.如下Python 程序段的功能是判断一个表达式中的括号(只有小括号)是否匹配，
exp＝input(″请输入表达式：″)
top＝－1；n＝len(exp)∥2；flag＝True
stack＝[″″]*n
for ch in exp:
　if ch＝＝″(″：
　 if ①____________：
　　　flag＝False；break
top＋＝1；stack[top]＝″(″
　　elif ch＝＝″)″：
　
if top<0：
　　　　flag＝False；break
top－＝1
if ②____________：
　print(″括号匹配″)
else：
　　print(″括号不匹配″)
则划线处应填入的代码是(　　)
A.① top>＝n ② flag and top＝＝0
B.① top＝＝n－1 ② flag and top＝＝0
C.① top>＝n ② flag and top＝＝－1
D.① top＝＝n－1 ② flag and top＝＝－1
D
解析　本题考查栈的基本操作。n值为len(exp)∥2，如果是″(″，进行入栈操作，如果栈顶指针为n，若再入栈，则左括号超出总字符串长度的一半，说明左括号的数量大于右括号。否则进行出栈操作，一个右括号匹配一个左括号，若在出栈前，栈为空，说明左括号少了。遍历完后，用右括号对左括号进行出栈操作，如果栈为空，说明两者数量相等。
10.某栈入栈序列为“A、B、C、D、E”，若第一个出栈的元素为“C”，最后一个出栈的元素为“E”，则可能的出栈序列有(　　)
A.3种 B.4种 C.5种 D.6种
A
解析　C要出栈，栈中有A和B，E最后一个出栈，因此E最后入栈并马上出栈，那么D可能在A前面，AB之间和B之后三个位置出栈。
11.有如下 Python 程序：
s1＝[0]*5; s2＝[0]*5; top1＝－1；top2＝－1
a＝[9，2，5，6，1]
for i in range (len(a))：
　while top1！＝－1 and a[i]　 top2＋＝1
　s2[top2]＝s1[top1]
　top1－＝1
　top1＋＝1; s1[top1]＝a[i]
　while top2！＝1：
D
　top1＋＝1
　s1[top1]＝s2[top2]
　top2－＝1
print (s1[top1])
执行程序后的输出结果是(　　)
A.1 B.5 C.6 D.9
解析　本题考查栈的相关知识。若 a[i]12.有如下 Python 程序段：
import random
lst＝['A'，'B'，'C'，'D']
st＝[0] * len(lst)
i，top＝0，－1
while i　k＝random.randint(0，1)
　 if k＝＝0：
　 top＋＝1
　st[top]＝lst[i]
　i＋＝1
　　elif top！＝－1：
　lst[i]＝st[top]
　top－＝1
B
A.['A'，'B'，'C'，'D'] B.['A'，'B'，'A'，'C']
C.['A'，'A'，'C'，'D'] D.['A'，'A'，'C'，'A']
解析　当k的值为0时，进行入栈操作；当k的值为1且栈不为空，进行出栈并替换lst[i]操作。由于i＋＝1操作发生在入栈过程中，因此必须要有4个元素出栈，但栈中可能有元素未出栈。A选项当随机数4次均为0，全部元素均在栈中。C选项随机数依次为0，1，0，0，有两个元素在栈中。D选项随机数依次为0，1，0，1，A先入栈，出栈后替换B，原B位置上的A再次入栈，最后替换D。B选项当i的值为2时，AB在栈中，应该B先出栈。
13.有如下 Python 程序段：
a＝{'<'：0，'('：1，'['：2，'{'：3，'>'：4，')'：5，']'：6，
'}'：7}
s1＝input()
s＝[8，0，0，0，0，0，0，0，0]
top＝0；flag＝True
for x in s1：
　 k＝a[x]
　if k<4：
if s[top]　　 flag＝False
　　　break
top＋＝1
s[top]＝k
else：
if s[top]！＝k－4:
　　　flag＝False
　　　break
top－＝1
if flag and top＝＝0:
　print(″YES″)
else：
　　　print(″NO″)
若输出结果为“NO”，则 s1 输入的值是(　　)
A.{}[]()<> B.[()]{<>} C.{[<()>]} D.{()[<>]}
C
解析　本题考查栈的操作。遍历字符串s1并取出在字典中的值k，如果是符号的左半部分，并且栈顶元素大于等于k，将k值入栈。若k大于等于4，且栈顶元素等于k－4，出栈一个元素。当flag为True且栈中只剩下一个元素，输出YES，否则输出NO。A选项{在字典中键值为3，入栈，}在字典中键值为7，满足条件栈顶元素等于k－4，让栈顶元素出栈，其他符号均成对，相同方法处理。B选项[和(对应的键值分别为2和1，2入栈后，1小于栈顶2，1也入栈，接着)和]让1和2依次出栈。{键值大于<键值，相同方法处理。C选项<和(对应的键值分别为0和1，当遍历到(时s[top]14.有如下Python程序段：
import random
s＝″Happy″
stk＝[″″]*len(s)；top＝－1
i＝0；res＝″″
while i　 if random.randint(0，1)＝＝0 or top＝＝－1：
　top＋＝1；stk[top]＝s[i]
　elif s[i]>stk[top]：
　res＋＝stk[top]；top－＝1
　i－＝1
　i＋＝1
while top>＝0：
　res＋＝stk[top]；top－＝1
print(res)
A
解析　分为产生随机数为0、随机数为1且s[i]>stk[top]和随机数为1且s[i]<＝stk[top]三种情况，在第2种情况中，让较小的元素先出栈，同时i减1。第3种情况既不入栈，也不出栈，因此s中可能有部分元素未入栈。B选项H入栈，a让H先出栈，a入栈，p让a入栈，p和p均入栈，y分两种让两个p出栈，最后在while结构中y出栈。C选项产生的随机数均为0。D选项a让H出栈，a入栈，随机数为0，p入栈，第2个p随机数为1，不入栈。y让p和a出栈。A选项a不可能让p出栈。
15.判断某序列b是否是入栈序列a＝[1，2，3，4，5]的出栈序列，程序如下：
a＝[1，2，3，4，5]
b＝list(map(int，input().split()))
stack＝[]
i＝j＝0
while i　 stack.append(①____________)
　 i＋＝1
　 while len(stack)>0 and ②____________：
　stack.pop()
　j＋＝1
if len(stack)＝＝0 and j＝＝len(a):
　print(b，'是'，a，'的出栈序列')
else：
　　print(b，'不是'，a，'的出栈序列')
划线处应填写的语句是(　　)
A.①a[i]　②stack[－1]＝＝a[j]
B.①a[i]　②stack[－1]＝＝b[j]
C.①b[i]　②stack[－1]＝＝b[i]
D.①b[i]　②stack[－1]＝＝a[j]
B
解析　本题考查栈的操作与程序实现。由第6行的添加操作和第9行的删除操作可以判断stack用于存储栈元素。可以通过将a元素不断入栈，看能否形成和b一样的出栈序列。第①空应该让a中的元素入栈，填写a[i]。而出栈时，需要判定栈顶元素是否和b序列中当前元素是否一致，一致才能出栈，尽可能形成与b一样的序列。
16.自从学习了不同进制之后，小明设计了一个计算不同进制数的加法器，并用Python编程实现。输入一个加法算式，加数可以是十进制数、二进制数或者十六进制数，程序的功能是输出它们的和。例如输入形如“1010B＋1DH＋109D＝”的加法算式后，执行程序输出“和是148”的结果。Python程序如下：
s＝input('输入一个混合进制的加法算式：')
dic＝{'B'：2，'D'：10，'H'：16}
st＝[″]*100
top，i，x，m＝－1，0，0，0
while i　　　if s[i]＝＝'＋' or s[i]＝＝'＝'：
　　　 m＝①____________
　　　top＝top－1
　　　t＝0
　　　while top！＝－1：
　　　if st[top]>＝'A' and st[top]<＝'F'：
　　　　　　　st[top]＝ord(st[top])－ord('A')＋10
　　　else：
　　　　　　st[top]＝int(st[top])
　　　②____________
　　　t＝t＋1
　　　top＝top－1
　else：
　　　③____________
　　　st[top]＝s[i]
　i＝i＋1
print('和是'，x)
(1)将划线处代码补充完整。
(2)若输入”101B＋DH＋100D”，输出的结果是________。
答案　(1)①dic[st[top]]　 ②x＝x＋st[top]*m**t　 ③ top＝top＋1　(2)118
解析　程序可知st列表中保存着当前加数的每一位。如对于式子“1010B＋1DH＋109D＝”，当读到第一个加号时，st列表的值为[‘1’，‘0’，’1’，’0’，’B’]，读到第二加号时，st的值是[‘1’，‘D’，‘H’]，读到最后’＝’号时，st的值是[‘1’，‘0’，‘9’，‘D’]。①st列表的最后一位是进制编号，读取st最后一位，通过字典dic得到进制值。②使用权值法把st列表中保存的进制数转化为十进制数。③读取到加数的每一位数字，都保存在st列表中的相应位置。(2)由于式子中的最后一位不是’＋’或者’＝’， 所以st列表中的最后一个数字没有加上。
17.某种密码设计方法如下：给定两个数组，数组元素由数字 1～9 组成，从中选出 k(k 小于等于两个数组长度之和)个数字拼接成一个新的数，同一数组中取出的数字保持其在原数组中的相对顺序，每个数组中至少有 1 个数被选中，满足该条件的最大数即为密码，程序运行界面如图所示。
请输入数组1：3　4　6　5　7　8
请输入数组2：9　1　2　5　8　3　4
请输入k：6
密码为：987834
请回答下列问题：
(1)程序部分代码如下，请在划线处填入正确的代码。
def select_num(nums，k):
　stack＝[0]*len(nums)；top＝－1；cnt＝len(nums)－k
　for num in nums:
　 while cnt>0 and top！＝－1 and stack[top]　　　top－＝1；cnt－＝1
　top＋＝1
　①____________
　while cnt>0：
num1＝input(″请输入数组 1：″)
num2＝input(″请输入数组 2：″)
num1＝list(map(int，num1.split(″ ″)))
num2＝list(map(int，num2.split(″ ″)))
k＝int(input(″请输入 k：″))
②____________
for i in range(1，k):
　a＝select_num(num1，i)
　③____________
　c＝merge(a，b)
　if c>m：
m＝c
print(″密码为：″＋str(m))
(2)加框处的程序代码有误，请改正。
答案　(1)①stack[top]＝num　②m＝0
③b＝select_num(num2，k－i)
(2)i解析　本题考查栈和数据的归并。(1)①函数select_num的功能是在数字串nums取出的数字位置不变的k个长度子串。cnt初值为len(nums)－k，即需要去除的数字个数，遍历数字串nums并将数字入栈，若当前的数字比栈顶数字大，则需将栈中数字出栈，让栈中形成一个递减的系列，每出栈一个cnt减1，当cnt值为0时，则不再出栈。②对m赋初值0。③主程序外循环i的值从1循环到k，采用枚举的思想，分别从一个数组num1中选出1到k－1个数字，则从另一个数组2中选出k－1到1个数字，所以第③空应填入b＝select_num(num2，k－i)。(2)自定义函数merge(a，b)用于将a、b两个数组的值合并按顺序合并成最大数，变量 i、j分别指向ab两个数组中待合并区间的初始位置，根据if j＝＝len(b) or i＝b[j]可知当只剩下a列表中的数据未处理或者a数组的值大于b数组的值则c＋＝a[i]，否则当 i＝＝len(a) or j课时目标
1.通过问题解决，理解栈的概念和特性。2.掌握栈的基本操作，并能编程实现。
1.栈的概念
(1)栈也是一种操作受限的线性表，仅允许表的________进行插入或删除操作。
(2)进行插入或删除操作的一端称为________，位于栈顶位置的元素称为栈顶元素；表的另一端为______，位于栈底位置的元素称为栈底元素。
2.栈的特性
(1)____________或____________。
(2)____________。
栈可以是空的，也可以包含多个元素。
3.栈的基本操作
(1)栈的创建
在存储n个元素的栈时，可以用列表创建一个长度为n的栈。
(2)入栈(push)、出栈(pop)
入栈操作：入栈也叫________操作，把数据元素压入栈顶，每次入栈时，栈顶指针变量top值________，再给st[top]赋值。
出栈操作：出栈时把栈顶元素取出，同时____________。如果栈中没有元素时，即top＝－1，不能进行出栈操作。
4.使用列表模拟栈操作
a＝[]　#建栈
a.append(″data1″)　#入栈
a.append(″data2″)　#入栈
a.append(″data3″)　#入栈
print(a.pop())　#出栈
print(a.pop())　#出栈
print(a.pop())　#出栈
5.建立stack类并进行栈操作
class Stack()：
def_ _init_ _(self)：　#建栈
self.my_stack＝[]
def push(self，data)：　#入栈
self.my_stack.append(data)
def pop(self)：　#出栈
return self.my_stack.pop()
def size(self)：　#栈空判断
return len(self.my_stack)
def isEmpty(self)：
return self.my_stack＝＝[]
stack＝Stack()
a＝[″data1″，″data2″，″data3″]
for item in a：　#入栈
stack.push(item)
print(″栈中元素个数为：″，stack.size())
while not stack.isEmpty(): #出栈
print(stack.pop())
例1 若某栈的容量是 3，即栈内最多只能容纳 3 个元素，若其某个出栈序列是a，b，c，d，e，那么它可能的入栈序列是(　　)
A.c，b，a，e，d B.d，c，b，a，e
C.b，c，a，e，d D.a，e，d，c，b
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有1个栈初始为空，其元素入栈顺序依次为s，t，r，w，u，y，m，若经过进栈和出栈操作后，栈底至栈顶元素分别为t，w，y，则第3个出栈元素为(　　)
A.m B.w C.u D.s
例2 公交车上有时候会出现人太多无法挤到后门下车而从前门下车的情况，因此若一个序列在有3个或以下元素时按队列方式离开序列，但在3个以上元素时按栈方式离开序列，则对于依次进入序列的xl，x2，x3，x4，x5，x6，离开序列的顺序可能为(　　)
A.x1，x4，x6，x2，x3，x5
B.x4，x1，x6，x2，x3，x5
C.x1，x2，x3，x6，x4，x5
D.x6，x5，x4，x3，x1，x2
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　设栈S和队列Q的初始状态为空，元素x1、x2、x3、x4、x5、x6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序依次为x2、x4、x3、x6、x5、x1，则栈S的容量至少应该为(　　)
A.2 B.3 C.4 D.5
例3 有如下 Python 程序段：
s＝input(″输入一个字符串″)
st＝[″″]*6；st[0]＝s[0]
top＝0
for i in range(1，len(s))：
　if top>＝0 and s[i]＝＝st[top]：
　 top－＝1
　else：
　 top＋＝1
　st[top]＝s[i]
print(st[：top＋1])
运行程序段，输入以下字符串，运行后的值与其它三项不同的是(　　)
A.ABABB B.AAABA C.BAABA D.BBABA
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有如下 Python 程序段：
st＝[0]*10
cnt，top＝0，－1
s＝input()
for i in range(0，len(s)，2):
　t＝s[i]
　 n＝int(s[i＋1])
　 if t＝＝'A'：
　 for j in range(n):
　 　　top＋＝1
　 　　　st[top]＝cnt
　　　　cnt＋＝1
　　elif t＝＝'P'：
　while top！＝－1 and n>0:
　　　　top－＝1
　　　n－＝1
print(st[0：top＋1])
若输入 s 的值为″A1P2A3P2A2″，则程序的输出结果是(　　)
A.[5，6] B.[2，5，6]
C.[4，5] D.[1，4，5]
例4 有如下Python程序段：
import random
a＝['A'，'B'，'#'，'#'，'C'，'D'，'#']
stk＝[0]*len(a)；top＝－1
for i in range(len(a))：
　op＝random.randint(0，1) # 随机生成0或1
　if op＝＝1 and a[i]！＝ '#'：
　　　top＋＝1；stk[top]＝a[i]
　　　　a[i]＝'#'
　　　elif op＝＝0 and top！＝－1 and a[i]＝＝'#'：
　 　　　a[i]＝stk[top]；top－＝1
执行该程序段后，a的值不可能的是(　　)
A.['A'，'B'，'#'，'#'，'C'，'D'，'#']
B.['#'，'#'，'#'，'#'，'#'，'#'，'#']
C.['#'，'B'，'#'，'#'，'C'，'D'，'A']
D.['#'，'#'，'A'，'B'，'C'，'D'，'#']
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有如下 Python 程序段：
import random
p＝″abcde*″；st＝[″″]*len(p)；s＝″″
top＝－1
i＝0
while i<＝5：
　m＝random.randint(0，1)
　 if m＝＝0：
top＋＝1
st[top]＝p[i]
i＋＝1
　elif len(st)>0:
s＋＝st[top]
top－＝1
print(s)
执行上述程序段后，输出结果可能的是(　　)
A.a* B.cdabe C.abcde* D.cdba
1.若已知元素的入栈顺序是a, b, c, d，其出栈序列为Q1, Q2, Q3, Q4，则Q2, Q4不可能是(　　)
A.a和c B.a和b C.b和d D.c和d
2.用I表示入栈操作，0表示出栈操作，若元素入栈的顺序为ABCDE，为了得到ADCEB的出栈顺序，则由I和0表示的操作串是(　　)
A.I0III00I00 B.I0II0I00I0 C.IIII00I000 D.I0III0000
3.利用栈求逆波兰表达式(表达式由操作数和运算符组成)的方法是：从左往右扫描该表达式，遇到操作数时入 栈；遇到运算符时，把处于栈上方的两个元素依次出栈，用运算符计算，并把计算结果压入栈中。如此反复 操作，直至表达式扫描结束。当用该算法求逆波兰表达式abcd－*e/＋f－的值时 (abcdef 表示不同的操作数)，所使用栈的深度至少为(　　)
A.3 B.4 C.5 D.6
4.有如下 Python 程序段：
st＝[0] * 10
a＝[4，6，1，7，2，8，6]
top＝0; st[top]＝a[0]
for i in range(1，len(a))：
　while top ！＝－1 and a[i]top－＝1
　top＋＝1
　st[top]＝a[i]
执行该程序段后，变量 top 的值为(　　)
A.－1 B.1 C.2 D.3
5.有如下Python程序段：
a＝[2，1，5，7，3]
n＝len(a)
s1＝[－1]*n；top1＝－1
s2＝[－1]*n；top2＝－1
for i in range(n)：
　while top1！＝－1 and a[i]　 top2＋＝1；s2[top2]＝s1[top1]；top1－＝1
　top1＋＝1；s1[top1]＝a[i]
while top2！＝－1：
　top1＋＝1；s1[top1]＝s2[top2]；top2－＝1
运行该程序段后，下列表达式不成立的是 (　　)
A.top1＝＝5 B.top2＝＝－1
C.s1[0]＝＝1 D.s1[3]＝＝7
6.有如下程序段：
s＝list(input(″输入一个字符串s：″)) # list 函数将s 转换为列表
top＝－1
a＝[0]*100
i＝0
while i　if s[i]＝＝'('：
　top＋＝1
　　　a[top]＝i
　elif s[i]＝＝')'：
　 st＝a[top]
　 top－＝1
　s＝s[：st]＋s[i－1：st：－1]＋s[i＋1：]
　i－＝2
　i＋＝1
print(″.join(s)) #将s 中元素以字符连接成一个新的字符串
执行该程序段后，输入“(ed(y(oc))p)”，输出结果是(　　)
A.pycode B.codepy C.pcodey D.copyde
7.有如下 Python 程序段：
import random
q＝[″A″，″B″，″C″，″D″，″#″]
head，tail＝0，4
s＝[0]*5
top＝－1
for i in range(5):
　t＝random.randint(0，1)　　 #随机生成 0 或 1
　if t＝＝0 and head　top＋＝1；s[top]＝q[head]
　head＋＝1
　elif t＝＝1 and top！＝－1:
　 s[top]＝0；top－＝1
执行该程序后，s 的值不可能的是(　　)
A.['A'，'B'，'C'，'D'，0] 　　 B.['D'，0，0，0，0]
C.[0，0，0，0，0] 　 　D.['A'，'C'，'D'，0，0]
8.有如下 Python 程序段：
a＝[1，2，3，4，5] ; b＝[3，2，5，1，4]
stack＝[] ; i＝j＝0
while i　stack.append(a[i]) #将 a[i]添加到 stack 末尾
　i＋＝1
　while len(stack)>0 and stack[－1]＝＝b[j]:
　stack.pop() #移除 stack 末尾元素
　j＋＝1
执行该程序段后，stack 中的元素个数为(　　)
A.0 B.1 C.2 D.3
课时3　栈
知识梳理
1.(1)一端　(2)栈顶　栈底
2.(1)先进后出　后进先出　(2)有限序列性
3.(2)压栈　加1　top值减1
例题精析
例1　A　[A选项c，b，a依次入栈，a，b，c依次出栈，接着e，d入栈后再出栈。B选项a要出栈，d，c，b，a需入栈，栈空间超过3。C选项b先于c入栈，则c需先出栈。D选项a入栈并出栈后，剩余4个元素入栈，超过栈容量。]
变式训练　C　[根据栈的特性，在栈中元素后进先出，因此第1个入栈和出栈的元素是s，第3个入栈第2个出栈的元素是r，第5个入栈第3个出栈的元素是u。]
例2　B　[A选项x1小于3个元素按队列方式出列，x4进入序列时，还有x2，x3，x4共3个元素，按队列方式出列，也就是x2出列，如果按栈离开，则必须x5进入序列，那就是x5先出。B选项x4按出栈方式离开，剩下x1，x2，x3，因此x1按队列方式离开。当x5、x6进入序列，x6按出栈方式离开。剩下3个按队列方式离开。C选项x1，x2，x3按队列方式离开，则x4，x5，x6进入序列后只能按队列方式离开。D选项x6先离开，全部元素进入序列，前面3个元素按出栈方式离开，后面3个元素只能是按队列方式离开。]
变式训练　B　[本题主要考查的是栈和队列的特点。栈的特点是先进后出，而队列的特点是先进先出，根据出队顺序可知，出栈的顺序依次为x2、x4、x3、x6、x5、x1，在x2出栈前，栈里的元素为x2和x1，共2个元素；在x4出栈前，栈里的元素为x4、x3和x1，共3个元素； 在x3出栈前，栈里的元素为x3和x1，共2个元素； x6出栈前，栈里的元素为x6、x5和x1，共3个元素； 在元素x5出栈前，栈里的元素为x5、x1，共2个元素，因此，栈的最小容量应为3。]
例3　C　[本题考查栈的性质。栈初始值有一个元素s[0]，从索引位置1开始遍历s，如果s[i]与栈顶元素相同，进行出栈操作，否则进行入栈操作。A、B和D选项栈中元素有ABA。C选项栈中元素只有A。]
变式训练　D　[对字符串s两个一组进行遍历，如果t为A，将n个cnt入栈，如果是p，对n个元素进行出栈。0入栈，0出栈，1、2、3入栈，3和2出栈，4、5入栈，因此从栈底到栈顶分别为1，4，5。]
例4　D　[本题考查栈的应用。若op＝1，且'#'时要入栈，是字母时，if语句与elif语句都不执行。若op＝0，栈不空且a[i]值为'#'，把栈顶值代替当前元素，且进行出栈操作。A选项，当op的值每次都是0时即可实现；B选项，当op的值每次都是1时即可实现；选项C，当op的值依次是1、0、1、1、0、0、0时即可实现。选项D，a[0]、a[1]值是'#'，表明A、B均已入栈，选项不符合出栈顺序。]
变式训练　D　[若产生的随机数m值为0，进行入栈操作。否则出栈后并连接到字符串s中。则于最后一个字符*一旦入栈后，i的值为5，结束循环，就不可能出栈。B选项a比b先入栈，出栈顺序应相反。D选项abc先入栈，c出栈，d入栈后出栈，最后a出栈。]
随堂检测
1.B　[a比b先入栈，因此a在b的后面出栈。]
2.A　[A入栈、出栈；BCD入栈，DC出栈；E入栈，EB出栈。]
3.B　[abcd依次进栈，栈深度为4，遇到“－”，进行c－d操作后，计算结果重新进栈(栈深度为3)，遇到“*”，进行b*(c－d)操作后重新进栈(深度为2)，接着“e”进栈(栈深度为3)最大深度为4。]
4.C　[栈中初始有一个值，从索引位置1开始遍历，当遍历到的数比栈顶小时，将栈顶元素出栈，自身入栈。遍历到1时，让4和6出栈。7入栈，2使得7出栈，8入栈，6使得8出栈，因此栈中有1、2和6共3个元素，top值为2。]
5.A　[本题考查栈的基本应用。遍历列表a中数据，若栈s1不空，且s1栈顶元素大于等于a[i]时，不断地将s1中元素出栈，并入栈s2中，将a[i]入栈s1。因此栈s1中元素有1，3，栈s2中有元素[2，7，5]，最后将栈s2中元素出栈并加入到栈s1中，因此栈s1中最终结果为[1，3，5，7，2]。]
6.A　[本题考查栈的性质和基本操作。遇到'('对应的下标入栈，遇到')'，元素出栈。同时列表元素重新组合，组合原则：二端不动，最内层配对括号内的元素翻转，同时这对括号抛弃。算法过程：(ed(y(oc))p)→(ed(yco)p)→(edocyp)→pycode。]
7.B　[本题考查队列和栈的基本操作。A选项t产生全0时，q中队列元素依次出队入栈，最后t＝0且head＝＝tail时，没有任何操作。B选项D要出栈，ABC都入栈且出栈，执行的次数超过5次。C选项t依次产生1，1，1，1，1时q中队列元素不出队也不入栈。D选项t依次产生0，0，1，0，0时AB先后入栈，然后B出栈，最后CD依次入栈。]
8.C　[stack是一个栈，b是一个队列。遍历数组a，将a[i]进行入栈操作，当栈不为空，且栈顶元素与队首元素相等，不断地将数据进行出栈和出队操作。1，2，3入栈，3，2出栈出队，4，5入栈，5出栈出队，栈中元素有1和4。]

展开更多......

收起↑