资源简介

(共21张PPT)
三、 栈及其基本操作
第三章　字符串、队列和栈
知识过关
1. 栈的概念
栈是一种操作受限的线性表,仅允许在表的一端进行插入或删除操作。进行插入或删除操作的一端称为栈顶,位于栈顶位置的元素称为栈顶元素;相应地,将表的另一端称为栈底,位于栈底位置的元素为栈底元素。
2. 栈的特性
(1)先进后出、后进先出。
如上图所示,元素“D”最后进栈,最先出栈。
(2)有限序列性。
栈中的元素也是有限的。栈可以是空的,也可以包含多个元素。栈中的每一个元素都有一个前驱点(栈底元素没有前驱点)和一个后继点(栈顶元素没有后继点),呈线性关系。
3. 栈的基本操作
栈一般按顺序结构存储,可以用数组实现,常用的操作有建栈、入栈、出栈等。
操作 示意图 代码实现
建栈 # 建立了长度为4的字符串空栈
top=－1
st=[""]*4
操作 示意图 代码实现
入栈 #首先将指针变量top的值加1,然后给st[top]赋值
top=top+1
st[top]="D"
操作 示意图 代码实现
出栈 #当栈不为空时,首先将栈顶元素取出,然后将指针top的值减1
t=st[top]
top=top－1
4. 栈与队列的比较
数据结构类型 结构特性 操作特性
栈 先进后出、后进先出 只允许在栈顶进行插入和删除操作;栈底不允许任何操作
队列 先进先出、后进后出 只允许在队尾进行插入操作;只能在队首进行删除操作
典例精选
【例1】 (2023·浙江6月选考)栈s的最大长度为3,初始为空,经过一系列入栈、出栈的操作后,若元素入栈的顺序是a,b,c,d,e,f,则可能的出栈序列是(　　)
A. f,e,d,c,b,a B. c,b,a,f,e,d
C. c,a,b,d,e,f D. c,e,d,b,a,f
【解析】 本题考查栈的入栈与出栈等相关操作。题干说明“栈s的最大长度为3,初始为空”。A中,f最先出栈,说明a,b,c,d,e,f需要全部入栈后,f才能出栈,但这种情况下栈长度需要为6,不符合题意。B中,c最先出栈,此时a,b,c入栈,接着c,b,a依次出栈,此时栈s内为空,接下来f出栈,说明d,e,f需要入栈,接着f,e,d出栈,过程中栈内长度符合题意。C中,c最先出栈,此时a,b,c入栈,接着c出栈,此时栈内只有a,b,由于b是栈顶元素,所以接下来出栈元素不可能是a,错误。D中,c最先出栈,此时a,b,c入栈,接着c出栈,此时栈内a,b,接下来e出栈,需要d,e入栈,此时栈内a,b,d,e,栈长度为4,不符合题意。
B
【例2】 (2024·浙江1月选考)栈s从栈底到栈顶的元素依次为1,2,3,队列Q初始为空。
约定如下:U操作是指元素出栈后入栈,H操作是指元素出栈后再入栈。经过UUHU系列
操作后,队列中队首到队尾的元素依次是(　　)
A. 2,1,3 B. 3,1,2　
C. 1,3,2 D. 2,3,1
D
【解析】 本题考查队列以及栈的基本操作。
具体操作流程如下图所示:
因此操作结束后,队列中队首到队尾的元素依次为:2,3,1,D正确。
【例3】 (2024·浙江6月选考)栈初始为空,经过一系列入栈、出栈的操作后,栈又为空。若元素入栈的顺序为“生”“旦”“净”“末”“丑”,则所有可能的出栈序列中,以“旦”结尾的序列个数是(　　)
A. 3　 B. 4
C. 5 D. 6
【解析】 本题考查栈的基本操作。本题中入栈的顺序为“生”“旦”“净”“末”“丑”,且要求以“旦”结尾,求所有可能的出栈序列如下:
第一种出栈情况:生、净、末、丑、旦
第二种出栈情况:生、末、丑、净、旦
第三种出栈情况:生、丑、末、净、旦
第四种出栈情况:生、末、净、丑、旦
第五种出栈情况:生、净、丑、末、旦
结合以上情况,C正确。
C
【例4】 (2023·浙江1月选考)有如下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 , # ]
【解析】 本题考查栈的运用。列表stk用于模拟栈,变量top即栈顶指针。依次读取列表a中每个元素a[i],并同时随机产生0或1赋值给变量op。接下来只有两种情况会改变a[i]的值:①op为1且a[i]值不为 # 时(为字母),将a[i]中字母入栈并将其值变为 # ;②op为0且栈不为空且a[i]值为 # 时,出栈并将值赋给a[i]。A选项,当op的值每次都是0时即可实现。B选项,当op的值每次都是1时即可实现。C选项,当op的值依次是1、0、1、1、0、0、0时即可实现。D选项,a[0]、a[1]值是 # ,表明 A 、 B 均已入栈,则出栈顺序一定是 B 、 A ,故选项中a[2]、a[3]值为 A 、 B 不可能。
D
自我检测
1. 下列关于栈的说法,错. 误. 的是(　　)
A. 数据入栈、出栈的顺序为先进后出
B. 只允许对栈顶元素进行插入、删除操作
C. 可以根据位置访问栈中元素
D. 栈的实现有顺序栈和链栈两种类型
【解析】 不可以根据位置访问栈中元素,C符合题意。
C
2. 在栈的模型中,插入元素的位置(　　)
A. 只能在栈顶
B. 只能在栈底
C. 栈顶、栈底均可
D. 视情况需要,可以在栈的任意位置
【解析】 在栈的模型中,插入元素的位置只能在栈顶,A正确。
A
3. 某办公软件的“编辑”菜单中有“撤销”和“恢复撤销”选项,其中“撤销”用于恢复当前编辑的前一步状态,“恢复撤销”则是“撤销”的反过程。下列数据结构的操作中,与这个“撤销”和“恢复撤销”的过程类似的是(　　)
A. 数组　　 B. 链表　　
C. 队列　　　 D. 栈
【解析】 本题考查栈操作的基本特性。“撤销”和“恢复撤销”操作规律符合栈“先进后出,后进先出”的特性,D正确。
D
4. 下列关于队列与栈的说法,错. 误. 的是(　　)
A. 队列和栈都是线性表结构,都可以用数组实现
B. 队列的队首元素和栈顶元素都是最先进入队列
C. 队列和栈的中间元素(不包含首尾)都既有前驱点,又有后继点
D. 队列允许队尾插入、队首删除,而栈底不允许插入和删除操作
【解析】 队列的队首元素最先入列,而栈顶元素最后进栈,B符合题意。
B
5. 利用栈的“先进后出”的特点可以实现数的进制转换。有如下Python程序段,实现的是将十进制数转换为二进制数的功能,运行界面如图所示。请在画线处填入合适的代码。
s=[0]*100
top=－1
n=int(input("请输入一个整数:"))
while n>0:
　　top+=1
　　①_________________
　　n=n//2
while top >－1:
　　print(s[top],end=" ")
　　②__________
【解析】 本题考查栈的应用。利用除2取余倒排法的方法解题。①top是栈顶,该处功能是实现将取得的余数进栈操作。②此处实现的功能是将余数出栈的操作,故让指针每次减1,直到到达top=－1的位置,表明所有数据出栈完毕。
请输入一个整数:27
1　1　0　1　1
>>>
s[top]=n%2
top－=1

展开更多......

收起↑