资源简介

(共19张PPT)
3.3 栈
栈：一种操作受限的线性表，仅允许在表的
一端进行插入或删除。进行插入或删除操作
的一端称为栈顶，位于栈顶位置的元素称为
栈顶元素；相应地，将表的另一端称为栈底，
位于栈底位置的元素为栈底元素。
栈的特性
1.先进后出、后进先出
赵六
王五
李四
张三
栈顶
栈底
最后入栈的“赵六”最先出栈，最先入栈的“张三”最后出栈
2.有限序列性
栈可以是空的，也可以包含多个元素。
栈中元素呈现线性关系，栈顶元素有一个前驱点，栈底元素
有一个后继点，其他元素既有一个前驱点，又有一个后继点。
栈与队列有什么相同点和不同点？
相同点：都是一种操作受限的线性表，都具有有限序列性的特点。
不同点：队列中的元素具有先进先出、后进后出的特点，栈中的元素
则具有先进后出、后进先出的特点。
栈的基本操作
栈，一般按顺序结构存储，可以用数组实现。由于栈顶元素在数组中
的位置会发生改变，因此使用top变量来记录栈顶元素在数组中的位
置。如下图所示，①图为栈结构，②图为用数组st存储该栈。
C
B
A
栈顶：top=2
栈底：
A B C
数组st 0 1 2
top
栈的存储
①
②
栈的常用操作有建栈、入栈、出栈等。
1.建栈
在Python中，当要存储n个元素的栈时，可以用列表创建一个长度为n的栈。
例如，要使4个字母“A”“B”“C”“D”按序入栈、出栈，可以建一个
长度为4的栈st，元素初始值均为空串。为了操作方便，把指向栈顶元素的
指针变量top值设置为-1。Python代码实现如下：
top=-1
st=[“”]*4
2.入栈、出栈
入栈又叫压栈操作，把数据元素压入栈顶。每次入栈时，栈顶指针变量top值
加1，再给st[top]赋值。字母“A”“B”“C”“D”按序入栈的过程如下图
所示。
0
1
2
3
空栈
top=-1
A
B
A
C
B
A
D
C
B
A
top 0
1
2
3
top 1
0
2
3
top 2
0
1
3
top 3
0
1
2
满栈
④
②
③
①
⑤
st栈的入栈过程
Python代码实现如下：
top=top+1 #top=0
st[top]=“A” #字母A入栈
top=top+1 #top=1
st[top]=“B” #字母B入栈
top=top+1 #top=2
st[top]=“C” #字母C入栈
top=top+1 #top=3
st[top]=“D” #字母D入栈
出栈时把栈顶元素取出，同时top值减1。如果栈中没有元素时，
即top=-1，不能进行出栈操作。
Python代码实现如下：
while top>-1:
print(st[top])
top-=1
编号为1、2、3、4的4列火车，按顺序开进一个栈式结构
的站点。问：开出火车站的顺序有多少种？请写出所有可能的出栈序列。
进入栈中的元素可停留、可出栈
（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
拓展链接
用列表自带的函数和方法实现的栈
Python中用列表自带的函数和方法可以实现建栈、入栈、出栈、栈中元素个数的
统计等操作。例如：
stacklist=[] #建立一个空栈list
stacklist.append(“A”) #字母A入栈
stacklist.append(“B”) #字母B入栈
print(stacklist[1]) #输出栈顶元素，为字母B
print(len(stacklist)) #输出栈中元素的个数，为2
stacklist.pop() #弹出栈顶元素
print(len(stacklist)) #输出栈中元素的个数，为1，是字母A
练一练
1.有如下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)
程序运行结束后，输出的内容是：
A.[“A”,”B”,”C”]3 B.[“A”,”B”,”C”]2
C.[“A”,1,”C”]3 D.[“A”,1,”C”]2
D
2.给定一个字符串，删除相邻重复项。例如，字符串“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)
谢 谢

展开更多......

收起↑