专题16　栈 学案（含解析）2025届高中信息技术.DOCXVIP

专题16栈

学习目标1.画出栈的示意图，理解入栈和出栈的操作；

2.通过出栈顺序，推算入栈顺序，理解栈的后进先出的基本特性；

3.根据栈的性质，实现栈的算法实现.

栈主要用于计算过程中保存的临时数据，是一种只能在数组一端进行存取的数据结构，最大特点是数据在存取时，无需查询，时间复杂度为O(1)，后存的数据先被取出。栈中元素必须满足先进后出原则。由于栈顶指针top指向栈中最后一个元素的索引位置，因此栈中元素的个数为top＋1，出栈时往往先要读取栈顶元素，再向下移动指针，入栈时，需先向上移动指针，再存入数据。

(2023年6月浙江省选考)有如下Python程序段：

importrandom

a＝[A，B，#，#，C，D，#]

stk＝[0]*len(a)；top＝－1

foriinrange(len(a))：

op＝random.randint(0，1)#随机生成0或1

ifop＝＝1anda[i]！＝#：

top＋＝1；stk[top]＝a[i]

a[i]＝#

elifop＝＝0andtop！＝－1anda[i]＝＝#：

a[i]＝stk[top]；top－＝1

执行该程序段后，a的值不可能的是()

A.[A，B，#，#，C，D，#]

B.[#，#，#，#，#，#，#]

C.[#，B，#，#，C，D，A]

D.[#，#，A，B，C，D，#]

重难点1栈的后进先出特性

同队列一样，栈也是一种操作受限的线性表，为了减少查询的时间，仅允许在表的一端进行插入或删除。进行插入或删除操作的一端称为栈顶，位于栈顶位置的元素称为栈顶元素；相应地，将表的另一端称为栈底，位于栈底位置的元素为栈底元素。栈具备“先进后出，后进先出”的特点。

例1栈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

变式1栈S最大长度为3，若元素a，b，c，d依次入栈，则可能的出栈序列为()

A.d，c，b，a B.b，a，d，c

C.c，a，b，d D.c，d，a，b

例2栈S从栈底到栈顶的元素依次为1，2，3，队列Q初始为空。约定：U操作是指元素出栈后入队，H操作是指元素出队后再入队。经过UUHU系列操作后，队列中队首到队尾的元素依次为()

A.2，1，3 B.3，1，2

C.1，3，2 D.2，3，1

变式2队列Q和栈S的初始值均为空，数字入栈先后顺序为1、2、3、4、5。P表示入栈，T表示元素出栈以后入队。在进行一系列P、T操作后，队列中从队首到队尾的元素依次为2、1、4、5，则对应的P、T操作是()

A.PPTTPPTPT B.PTPTPPPTT

C.PPTTPPPTT D.PPTTPTPPT

重难点2栈的算法实现

入栈也叫压栈操作，把数据元素压入栈顶。与队列(tail指向队尾下一个元素的位置)不同的是，栈顶指针指向栈顶元素，每次入栈时，栈顶指针变量top值加1，再给st[top]赋值。出栈时把栈顶元素取出，同时栈顶指针变量top值减1。如果栈中没有元素时，即top＝－1，不能进行出栈操作。

例1有如下Python程序段：

s＝″abbacabcbbcc″；s1＝″″

st＝[″″]*100；top＝－1

foriins：

iftop＝＝－1ori！＝st[top]:

top＋＝1；st[top]＝i

else：

top＝top－1

whiletop＝0：

s1＝st[top]＋s1；top－＝1

print(s1)

执行该程序段后，变量s1的值是()

A.″acba″ B.″cbac″ C.″abca″ D.″cabc″

变式1有如下Python程序段：

fromrandomimportrandint

a＝[5，3，2，7，4]

i＝0；top＝－1

st＝[0]*5

whilei＝len(a)－1:

n＝randint(1，2)#randint(1，2)随机生成1或2

ifn%2＝＝0:

top＋＝1

st[top]＝a[i]

i＋＝1

eliftop＝0:

top－＝1

print(st)

运行该程序，输出结果不可能的是()

A.[5，3，2，7，4] B.[4，2，0，0，0]

C.[5，7，4，0，0] D.[3，2，5，7，0]

例2有如下