夜雨聆风学习资料网 资料列表 开通 VIP 用登录 / 注册 ⌄
PDF

003-第三讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt

查看资料信息、公开预览和下载状态。

共 221 页PDF · 2.2MB
下载

文档在线预览

公开展示前 10 页
100%
1
《003-第三讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第1页预览
2
《003-第三讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第2页预览
3
《003-第三讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第3页预览
4
《003-第三讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第4页预览
5
《003-第三讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第5页预览
6
《003-第三讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第6页预览
7
《003-第三讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第7页预览
8
《003-第三讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第8页预览
9
《003-第三讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第9页预览
10
《003-第三讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第10页预览

本文档共 221 页 剩余 211 页未展示,请下载后查阅

下载

文档文本内容

第三讲:栈
主讲人:刘财政
B站:@计算机考研刘财政考纲要求CON T EN T S
目录
考点一 栈的概念 ★★★★
考点二 栈的顺序结构 ★★
考点三 栈的链式结构
考点四 栈的应用 ★★★★★考纲框架CON T EN T S
目录
考点一 栈的概念 ★★★★
考点二 栈的顺序结构 ★★
考点三 栈的链式结构
考点四 栈的应用 ★★★★★【栈的定义和概念】考点一: 栈的概念
【问题】嵌套调用:在函数的执行过程中调用其他函数,返回到哪里?
【想法】为保证函数嵌套调用的正确执行,返回到调用位置。
A
主
函 D
B
数
E
main
C
用栈保存,返回最后进栈的位置
在实际问题的处理过程中,有些数据具有后到先处理的特点考点一: 栈的概念
【问题】 判断给定表达式中所含括号是否正确配对。
【想法】 配对原则:右括号与其前面最近的尚未配对的左括号相配对。
顺序扫描表达式,将右括号与已经扫描过的最后一个尚未配对的左括号进行配对。
5 + ( (3 + 2) ×8 – 7) ÷ 3 5 + ( (3 + 2) ×8 – 7) ) ÷ 3
如何保存已经扫描过的尚未配对的左括号,并对其实施配对操作?
用栈保存,扫描到左括号进栈,扫描到右括号出栈
在实际问题的处理过程中,有些数据具有后到先处理的特点考点一: 栈的概念
【问题】 上述的操作能否使用线性表来实现?
操作不
确定性
线性表
链表遍
顺序表移
动元素难 历难考点一: 栈的概念
栈的定义
栈:限定仅在一端进行插入和删除操作的线性表(运算受限的线性表)
插入位置:1 ~ n+1
栈顶
线性表
(a , …, a , a )
删除位置:1 ~ n
1 n-1 n
插入位置:n+1
栈顶
栈底 栈底
栈
删除位置:n
栈示意图
栈顶(top):允许插入和删除的一端称为栈顶
栈底(bottom):另一端称为栈底考点一: 栈的概念
栈的术语:
进栈 出栈
➢ 允许进行插入、删除操作的一端称为栈顶。
➢ 表的另一端称为栈底。
栈顶
➢ 当栈中没有数据元素时,称为空栈。
➢ 栈的插入操作通常称为进栈或入栈。
➢ 栈的删除操作通常称为退栈或出栈。
栈底
栈示意图考点一: 栈的概念
栈的主要特点是“后进先出”,即后进栈的元素先出栈。栈也称为后进先出表
(Last In First Out,LIFO)。
假设死胡同的宽度恰好 走进死胡同的5人要按相
只够正一个人 反次序退出
死胡同就是一个栈!【栈的操作】考点一: 栈的概念
插入 删除 插入:入栈、进栈、压栈
删除:出栈、弹栈
c
空栈:不含任何数据元素的栈
b
条件判断
a
此时执行出栈操作,哪个元素可以出栈呢?考点一: 栈的概念
假设有四个元素按A、B、C,D的次序依次进栈,且每个元素只允许进一次栈,
则可能的出栈序列有多少种?
D
情况一
C
出栈:D, C,B,A
B
A
栈只是对插入和删除操作的位置进行了限制
并没有限定插入和删除操作进行的时间考点一: 栈的概念
假设有四个元素按A、B、C,D的次序依次进栈,且每个元素只允许进一次栈,
则可能的出栈序列有多少种?
情况二
出栈:A, B,C,D
CDAB
栈只是对插入和删除操作的位置进行了限制
并没有限定插入和删除操作进行的时间考点一: 栈的概念
假设有四个元素按A、B、C,D的次序依次进栈,且每个元素只允许进一次栈,
则可能的出栈序列有多少种?
情况三
D
出栈:A, D,C,B
C
BA
栈只是对插入和删除操作的位置进行了限制
并没有限定插入和删除操作进行的时间考点一: 栈的概念
从上面的进栈和出栈的顺序情形,可以看出虽然进栈顺序是一定的,但是出栈
顺序不确定,因为在进栈后,可以随时做出栈操作 。
➢ 给定n个元素,出栈的顺序一共有多少种呢?
➢ 公式: 给定n个元素,出栈的顺序的情形满足卡特兰数,计算公式是:
1
𝑛
𝐶 。
2𝑛
𝑛+1【政哥题型总结】考点一: 栈的概念
1、一个栈的输入序列为1,2,3,4,5,则下列序列中不可能是栈的输出序列的是( )。
A.2,3,4,1,5 B.5,4,1,3,2
C.2,3,1,4,5 D.1,5,4,3,2考点一: 栈的概念
1、一个栈的输入序列为1,2,3,4,5,则下列序列中不可能是栈的输出序列的是( )。
A.2,3,4,1,5 B.5,4,1,3,2
C.2,3,1,4,5 D.1,5,4,3,2
选项A:【可能】
出栈: 2,3,4,1,5
342
15考点一: 栈的概念
1、一个栈的输入序列为1,2,3,4,5,则下列序列中不可能是栈的输出序列的是( )。
A.2,3,4,1,5 B.5,4,1,3,2
C.2,3,1,4,5 D.1,5,4,3,2
5
选项B:【不可能】
4
出栈: 5,4,1,3,2
3
2
1考点一: 栈的概念
2、一个栈的入栈序列为1,2,3,…,n ,其出栈序列是p,p,p,…,p。
1 2 3 n
若p=2,则p可能取值的个数是( )多少?
2 3
A.n-3 B.n-2 C.n-1 D. 无法确定考点一: 栈的概念
2、一个栈的入栈序列为1,2,3,…,n ,其出栈序列是p,p,p,…,p。
1 2 3 n
若p=2,则p可能取值的个数是( )多少?
2 3
A.n-3 B.n-2 C.n-1 D. 无法确定
C【解析】给定一个序列,出栈顺序是不确定的。出
栈序列为p ,p ,p ,…,p 。若p =2,会有两种情况:
1 2 3 n 2
(1)p 是1,此时操作是push(1),pop(1),push(2),
1
pop(2),此时p =3,4,…,n。
3
42351考点一: 栈的概念
2、一个栈的入栈序列为1,2,3,…,n ,其出栈序列是p,p,p,…,p。
1 2 3 n
若p=2,则p可能取值的个数是( )多少?
2 3
A.n-3 B.n-2 C.n-1 D. 无法确定
C【解析】给定一个序列,出栈顺序是不确定的。
出栈序列为p ,p ,p ,…,p 。若p =2,会有两种情况:
1 2 3 n 2
(2)p 是 3 , 此 时 操 作 是 push(1) , push(2) ,
1
3
push(3),pop(3),pop(2),此时p =1,4,…,n。
3
综上,p 的可能取值有n-1个。 2
3
541THANKSCON T EN T S
目录
考点一 栈的概念 ★★★★
考点二 栈的顺序结构 ★★
考点三 栈的链式结构
考点四 栈的应用 ★★★★★考纲框架考纲框架
顺序栈的定义
顺序栈的性质
顺序栈的操作
对顶栈(共享栈)【顺序栈的定义】考点二: 栈的顺序结构
1、栈的抽象数据类型定义
ADT Stack
DataModel
栈中元素具有相同类型及后进先出特性,相邻元素具有前驱和后继关系
Operation
InitStack:栈的初始化
DestroyStack :栈的销毁
Push:入栈
Pop:出栈
GetTop:取栈顶元素
Empty:判空
endADT考点二: 栈的顺序结构
2、栈的存储结构
栈中元素逻辑关系与线性表的相同,栈可以采用与线性表相同的存储结构。
逻辑结构
栈
顺序表 链 表
顺序栈 链栈
存储结构考点二: 栈的顺序结构
3、顺序栈:栈的顺序存储结构
0 1 2 3 4 5 6 7 8
a b c
top
如何改造数组实现栈的顺序存储呢?
如何表示栈底:用数组的一端作为栈底
如何表示栈顶:设变量top存储栈顶元素所在的下标的下一个位置考点二: 栈的顺序结构
0 1 2 … STACKSIZE-1
3、顺序栈:栈的顺序存储结构
a b c
动态顺序栈
top
#define STACK_SIZE 100 /* 栈初始数组大小 */
#define STACKINCREMENT 10 /* 存储空间分配增量 */
#typedef int ElemType ;
typedef struct sqstack{
ElemType *bottom; /* 栈不存在时值为NULL */
ElemType *top; /* 栈顶指针 */
int stacksize ; /* 当前已分配空间,以元素为单位 */
} SqStack ;考点二: 栈的顺序结构
0 1 2 … STACKSIZE-1
3、顺序栈:栈的顺序存储结构
a b c
静态顺序栈
top
#define STACKSIZE 100 /*假定栈元素最多100个*/
typedef int ElemType; /*定义栈元素的数据类型,假设为int型*/
typedef struct
{
ElemType data[ S T A C K S I Z E ]; /*存放栈元素的数组*/
int top; /*栈顶位置,栈顶元素在数组中的下标*/
} SeqStack;【顺序栈的性质】考点二: 栈的顺序结构
1、顺序栈的各种状态
top
4 4 e 4 top 4
3 3 3 3
d d
2 2 2 2
c c
1 top 1 b 1 b 1
top 0 a 0 a 0 a 0
(a)空栈 (b)a进栈 (c)b、c、d、e进栈 (d)出栈一次
顺序栈4要素: ⚫ 栈空条件:top=0
⚫ 栈满条件:top=MaxSize
⚫ 进栈e操作:将e放在top处;top++;
⚫ 退栈操作: top--;从top处取出元素e;考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
➢ 栈空?
➢ 栈满?
➢ top指针指向哪里?
➢ bottom指针指向哪里?
➢ 栈中元素个数如何算?
Answer:取决于栈的初始化考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
① 初始化时,top = bottom = -1
(a)初始化
4
3
2
1
0
top考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
① 初始化时,top = bottom = -1
(a)初始化 (b)a进栈
4 4
3 3
2 2
1
1
a
0
0
top
top
入栈操作:s->top++; //栈顶指针增1
s->data[s->top]=a; //元素a放在栈顶指针处考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
① 初始化时,top = bottom = -1
(a)初始化 (b)a进栈 (c)b、c、d、e进栈
4 4 top e 4
3 3 d 3
2 2 c 2
1 1 b 1
0 top a 0 a 0
top
➢ top指向栈顶元素(移动端)
➢ bottom指向-1(固定端)考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
① 初始化时,top = bottom = -1
(a)初始化 (b)a进栈 (c)b、c、d、e进栈 (d)e出栈
4
4 4 top e 4 top e
3
3 3 d 3 d
2
2 2 c 2 c
1 1 b 1 b 1
0 top a 0 a 0 a 0
top
出栈:x= s->data[s->top];
s->top--;//栈顶指针减1考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
① 初始化时,top = bottom = -1
(a)初始化 (b)a进栈 (c)b、c、d、e进栈 (d)e出栈
4
4 4 top e 4
3 3 d 3 top d 3
2
2 2 c 2 c
1 1 b 1 b 1
0 top a 0 a 0 a 0
top
➢ top指向栈顶元素(移动端)
➢ bottom指向-1(固定端)考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
① 初始化时,top = bottom = -1
(a)初始化 (b)a进栈 (c)b、c、d、e进栈 (d)e出栈
4
4 4 top e 4
3 3 d 3 top d 3
2
2 2 c 2 c
1 1 b 1 b 1
0 top a 0 a 0 a 0
top
➢ 栈中元素个数 top+1 个考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
① 初始化时,top = bottom = -1
(d)e出栈
(a)初始化 (b)a进栈 (c)b、c、d、e进栈
4
4 4 top e 4
3 3 d 3 top d 3
2
2 2 c 2 c
1 1 b 1 b 1
0 top a 0 a 0 a 0
top
➢ 当top+1>= n时(栈满)考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
② 初始化时,top = bottom = 0
(a)初始化
4
3
2
1
top 0考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
② 初始化时,top = bottom = 0
(a)初始化 (b)a进栈
4 4
3 3
2 2
1 1
top top a
0
0
入栈操作:s->data[s->top]=a; //元素a放在栈顶指针处
s->top++; //栈顶指针增1考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
② 初始化时,top = bottom = 0
(a)初始化 (b)a进栈 (c)b、c、d、e进栈
top
4 4 e 4
3 3 d 3
2 2 c 2
1 top 1 b 1
top 0 a 0 a 0
➢ top指向栈顶元素的下一个空位置(移动端)
➢ bottom指向0(固定端)考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
② 初始化时,top = bottom = 0
(a)初始化 (b)a进栈 (c)b、c、d、e进栈 (d)e出栈
top
top
4
4 4 e 4 e
3
3 3 d 3 d
2
2 2 c 2 c
1 top 1 b 1 b 1
top 0 a 0 a 0 a 0
出栈:s->top--; //栈顶指针减1
x= s->data[s->top];考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
② 初始化时,top = bottom = 0
(d)e出栈
(a)初始化 (b)a进栈 (c)b、c、d、e进栈
top
top
4
4 4 e 4 e
3
3 3 d 3 d
2
2 2 c 2 c
1 top 1 b 1 b 1
top a 0
0 a 0 a 0
➢ top指向栈顶元素的下一个空位置(移动端)
➢ bottom指向0(固定端)考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
② 初始化时,top = bottom = 0
(a)初始化 (b)a进栈 (c)b、c、d、e进栈 (d)e出栈
top
top 4
4 4 e 4
3
3 3 d 3 d
2
2 2 c 2 c
1 top 1 b 1 b 1
top a 0
0 a 0 a 0
➢ 栈中元素个数 top个考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
② 初始化时,top = bottom = 0
(a)初始化 (b)a进栈 (c)b、c、d、e进栈 (d)e出栈
top
top 4
4 4 e 4
3
3 3 d 3 d
2
2 2 c 2 c
1 top 1 b 1 b 1
top a 0
0 a 0 a 0
➢ 当top>= n时(栈满)考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
③初始化时,top = bottom = n
(a)初始化
top
4
3
2
1
0考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
③初始化时,top = bottom = n
(a)初始化 (b)a进栈
top
top
4 a 4
3 3
2 2
1 1
0
0
入栈操作:s->top--; //栈顶指针减1
s->data[s->top]=a; //元素a放在栈顶指针处考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
③初始化时,top = bottom = n
(a)初始化 (b)a进栈 (c)b、c、d、e进栈
top
4 top a 4 a 4
3 3 b 3
2 2 c 2
1 1 d 1
0 0 top e 0
➢ top指向栈顶元素(移动端)
➢ bottom指向n(固定端)考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
③初始化时,top = bottom = n
(a)初始化 (b)a进栈 (c)b、c、d、e进栈 (d)e出栈
top
4 top a 4 a 4 a 4
3 3 b 3 b 3
2 2 c 2 c 2
1 1 d 1 d 1
0 0 top e 0 top e 0
出栈操作:x = s->data[s->top];
s->top++; //栈顶指针加1考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
③初始化时,top = bottom = n
(a)初始化 (b)a进栈 (c)b、c、d、e进栈 (d)e出栈
top
4 top a 4 a 4 a 4
3 3 b 3 b 3
2 2 c 2 c 2
1 1 d 1 top d 1
0 0 top e 0 0
➢ top指向栈顶元素(移动端)
➢ bottom指向n(固定端)考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
③初始化时,top = bottom = n
(a)初始化 (b)a进栈 (c)b、c、d、e进栈 (d)e出栈
top
4 top a 4 a 4 a 4
3 3 b 3 b 3
2 2 c 2 c 2
1 1 d 1 top d 1
0 0 top e 0 0
➢ 栈中元素个数 n-top个考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
③初始化时,top = bottom = n
(a)初始化 (b)a进栈 (c)b、c、d、e进栈 (d)e出栈
top
4 top a 4 a 4 a 4
3 3 b 3 b 3
2 2 c 2 c 2
1 1 d 1 top d 1
0 0 top e 0 0
➢ 当n-top>= n时(栈满)考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
④初始化时,top = bottom = n-1
(a)初始化
4
top
3
2
1
0考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
④初始化时,top = bottom = n-1
(a)初始化 (b)a进栈
top 4 top a 4
3 3
2 2
1 1
0
0
入栈操作:s->data[s->top]=a; //元素a放在栈顶指针处
s->top--; //栈顶指针减1考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
④初始化时,top = bottom = n-1
(a)初始化 (b)a进栈 (c)b、c、d、e进栈
top 4 a 4 a 4
3 top 3 b 3
2 2 c 2
1 1 d 1
0 0 e 0
top
➢ top指向栈顶元素的下一个空位置(移动端)
➢ bottom指向n-1(固定端)考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
④初始化时,top = bottom = n-1
(a)初始化 (b)a进栈 (c)b、c、d、e进栈 (d)e出栈
4
4 a
a
top
4 a 4
3
3 b
b
3 top 3
2
2 c
c
2 2
d 1 d 1
1
1 e 0
e 0
0 0 top
top
出栈操作:s->top++; //栈顶指针加1
x = s->data[s->top];考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
④初始化时,top = bottom = n-1
(a)初始化 (b)a进栈 (c)b、c、d、e进栈 (d)e出栈
4
4 a
a
top
4 a 4
3
3 b
b
3 top 3
2
2 c
c
2 2
d 1 d 1
1
1 top
0
e 0
0 0
top
➢ 元素个数n-top -1个考点二: 栈的顺序结构
2、栈的顺序存储的临界条件
假设C语言中开辟[0…n-1]共n个空间存储栈元素( StackSize =5为例)
④初始化时,top = bottom = n-1
(a)初始化 (b)a进栈 (c)b、c、d、e进栈 (d)e出栈
4
4 a
a
top
4 a 4
3
3 b
b
3 top 3
2
2 c
c
2 2
d 1 d 1
1
1 top
0
e 0
0 0
top
➢ 当n-top-1>=n时,栈满【静态顺序栈的操作】考点二: 栈的顺序结构
1、静态顺序栈的基本操作
(1)判空:S.top = 0
(2)判满:S.top >= STACK_SIZE
push(e);
(3)进栈:ቊ
t + +;
t − −;
(4)出栈:ቊ
pop();
(5)获取栈顶元素: GetTop()考点二: 栈的顺序结构
2、栈的初始化,栈的初始化就是分配一个STACK_SIZE大小的数组空间。初
始化top的值0,初始化栈的空间大小是STACK_SIZE。
// 初始化栈
void InitStack(SqStack& s) {
s.top = 0; // 栈空时栈顶指针为0
}
0 1 2 … STACK_SIZE-1
top考点二: 栈的顺序结构
3、压栈(元素进栈); 参考顺序栈的性质中第二种情形中的图示。进栈之前先
判断栈是否已满。按照第二种情形,将元素放入栈中。因为静态栈一旦分配
数组空降,其位置不定不变了,只需要一个top指针就行,其中数组的下标0
就默认是bottom了,不用表示。
0 1 2 … STACK_SIZE-1
a b c
top
0 1 2 … STACK_SIZE-1
a b c x
top考点二: 栈的顺序结构
3、压栈(元素进栈); 参考顺序栈的性质中第二种情形中的图示。进栈之前先
判断栈是否已满。按照第二种情形,将元素放入栈中。因为静态栈一旦分配
数组空降,其位置不定不变了,只需要一个top指针就行,其中数组的下标0
就默认是bottom了,不用表示。
栈满:top==StackSize
// 成功,返回true
// 失败,返回false
什么情况下无法入栈?
bool push(SqStack& s, ElemType e) {
if (s.top == STACKSIZE) {
时间复杂度?
return false; // 栈满
}
s.data[s.top++] = e; // 元素e压入栈顶,栈顶指针加1
return true;
}考点二: 栈的顺序结构
4、弹栈(元素出栈);参考顺序栈的性质中第二种情形中的图示。进栈之前先
判断栈是否已空。如果栈不空,先将top--, 再弹出元素。
0 1 2 … STACK_SIZE-1
a b c x
top
0 1 2 … STACK_SIZE-1
a b c
top考点二: 栈的顺序结构
4、弹栈(元素出栈);参考顺序栈的性质中第二种情形中的图示。进栈之前先
判断栈是否已空。如果栈不空,先将top--, 再弹出元素。
// 成功,返回true
栈空:top==0
// 失败,返回false
bool pop(SqStack& s, ElemType& e) {
什么情况下无法出栈?
if (s.top == 0) {
return false; // 栈空
}
e = s.data[--s.top]; // 栈顶元素出栈,栈顶指针减1
return true;
}考点二: 栈的顺序结构
5、获取栈顶元素,并用e保存栈顶元素。
// 成功,返回true
// 失败,返回false
bool GetTop(SqStack& s, ElemType& e) {
if (s.top == 0) {
return false; // 栈空
}
e = s.data[s.top - 1]; // 栈顶元素
return true;
}【动态顺序栈的操作】考点二: 栈的顺序结构
1、动态顺序栈的基本操作
(1)判空:S.top== S.bottom
(2)判满:S.top-S.bottom >= S.STACKSIZE
push(e);
(3)进栈:ቊ
t + +;
t − −;
(4)出栈:ቊ
pop();
(5)获取栈顶元素: GetTop()考点二: 栈的顺序结构
2、栈的初始化,栈的初始化就是分配一个STACKSIZE大小的数组空间。
并且初始化S.top = S.bottom,初始化栈空间的大小。
// 成功,返回true
// 失败,返回false
bool InitStack(SqStack& s) {
s.bottom = (ElemType*)malloc(STACKSIZE * sizeof(ElemType));
if (!s.bottom) {
return false;
}
s.top = s.bottom; // 栈空时栈顶指针和栈底指针相等
s.stacksize = STACKSIZE; // 栈初始大小为STACKSIZE
return true;
}考点二: 栈的顺序结构
3、压栈(元素进栈);参考顺序栈的性质中第二种情形中的图示。进栈之前先判
断栈是否已满。如果当前栈满,将从新开辟一个新空间,对应的代码是
S.bottom=(ElemType *)realloc((S.STACKINCREMENT+STACK_SIZE)
*sizeof(ElemType));此时大家注意,这个新空间不是再原有空间的基础上增加,
而是重新找一个连续空间。考点二: 栈的顺序结构
// 成功,返回true
// 失败,返回false
bool push(SqStack& s, ElemType e) {
if (s.top - s.bottom >= s.stacksize) { // 栈满,追加存储空间
s.bottom = (ElemType*)realloc(
s.bottom, (s.stacksize + STACKINCREMENT) * sizeof(ElemType));
if (!s.bottom) { return false; }
s.top = s.bottom + s.stacksize; // 更新栈顶指针
s.stacksize += STACKINCREMENT; // 更新栈大小
}
*s.top++ = e; // 元素e压入栈顶,栈顶指针加1
return true;
}考点二: 栈的顺序结构
从这里我们可以看出,动态栈会伴随着程序的执行,其位置会发生改变,因此
需要bottom和top标定栈的空间的位置。若空间分配成功,按照第二种情形,
将元素放入栈中。考点二: 栈的顺序结构
4、弹栈(元素出栈);参考顺序栈的性质中第二种情形中的图示。出栈之前先
判断栈是否已空。如果栈不空,先将top--, 再弹出元素。
// 成功,返回true
// 失败,返回false
bool pop(SqStack& s, ElemType& e) {
if (s.top == s.bottom) {
return false; // 栈空
}
e = *--s.top; // 栈顶元素出栈,栈顶指针减1
return true;
}考点二: 栈的顺序结构
5、获取栈顶元素,并用e保存栈顶元素。
// 成功,返回true
// 失败,返回false
bool GetTop(SqStack& s, ElemType& e) {
if (s.top == s.bottom) {
return false; // 栈空
}
e = *(s.top - 1); // 不改变栈顶指针
return true;
}【政哥题型总结】考点二: 栈的顺序结构
1、若一个栈以向量V[1..n]存储,初始栈顶指针top为n+1,则下面x进栈的正确
操作是( )
A.top:=top+1; V [top]:=x B. V [top]:=x; top:=top+1
C. top:=top-1; V [top]:=x D. V [top]:=x; top:=top-1考点二: 栈的顺序结构
1、若一个栈以向量V[1..n]存储,初始栈顶指针top为n+1,则下面x进栈的正确
操作是( )
A.top:=top+1; V [top]:=x B. V [top]:=x; top:=top+1
C. top:=top-1; V [top]:=x D. V [top]:=x; top:=top-1
解析
(a)初始化 (b)a进栈
top
top
4 a 4
3 3
2 2
1 1
0
0
入栈操作:s->top--; //栈顶指针减1
s->data[s->top]=a; //元素a放在栈顶指针处考点二: 栈的顺序结构
1、若一个栈以向量V[1..n]存储,初始栈顶指针top为n+1,则下面x进栈的正确
操作是( )
A.top:=top+1; V [top]:=x B. V [top]:=x; top:=top+1
C. top:=top-1; V [top]:=x D. V [top]:=x; top:=top-1
C【解析】若一个栈以向量V[1..n]存储,初始栈顶指针top为n+1,说明栈初始
化时,top初始化在高地址,所以在进行入栈时需要先让top--,再push元素。考点二: 栈的顺序结构
2、在顺序栈中,假定以高端地址作为栈底,以 top 作为栈顶,则当做出栈处理
时,top 的变化为()。
A、不变 B、top=0
C、top=top -1 D、top=top+1考点二: 栈的顺序结构
2、在顺序栈中,假定以高端地址作为栈底,以 top 作为栈顶,则当做出栈处理
时,top 的变化为()。
A、不变 B、top=0
C、top=top -1 D、top=top+1
解析
(a)初始化 (b)a进栈
top
top
4 a 4
3 3
2 2
1 1
0
0
入栈操作:s->top--; //栈顶指针减1
s->data[s->top]=a; //元素a放在栈顶指针处考点二: 栈的顺序结构
2、在顺序栈中,假定以高端地址作为栈底,以 top 作为栈顶,则当做出栈处理
时,top 的变化为()。
A、不变 B、top=0
C、top=top -1 D、top=top+1
D【解析】以高端地址作为栈底,以 top 作为栈顶,在进行入栈时需要先让
top--,再push元素。那么需要进行出栈时,需要让top++;【对顶栈(共享栈)】考点二: 栈的顺序结构
1、共享栈定义
若需要用到两个相同类型的栈,可用一个数组data[0.. STACK_SIZE-1]
来实现这两个栈,这称为共享栈。
0 1 … … STACK_SIZE-1
data考点二: 栈的顺序结构
栈的一端不动,元素向另外一端伸展,
把两个栈的栈底设置在数组的两端
0 1 … n-1 … STACK_SIZE-1
data a a … a … b … b b
1 2 n m 2 1
top1 top2
栈1 栈2考点二: 栈的顺序结构
0 1 … n-1 … STACK_SIZE-1
data a a … a … b … b b
1 2 n m 2 1
top1 top2
栈1 栈2
共享栈的4要素:
⚫ 栈空条件,栈1空:top1==-1;栈2空:top2==MaxSize
⚫ 栈满条件:top1==top2-1
⚫ 元素x进栈操作,进栈1操作:top1++;data[top1]=x;进栈2操作:top2--
;data[top2]=x;
⚫ 出栈x操作,出栈1操作,x=data[top1];top1--;出栈2操作,
x=data[top2];top2++;【政哥题型总结】考点二: 栈的顺序结构
1.若双栈共享空间S[0..n-1],初始时top =-1、top =n,则判栈满为真的条件
1 2
是( )。
A.top ==top B.top -top ==1
1 2 1 2
C.top +top ==n D.top -top ==1
1 2 2 1考点二: 栈的顺序结构
D【解析】假如有两个顺序栈,我们可以让两个栈共享同一片存储空间,这片
存储空间不单独属于任何一个栈,两个栈的栈底在这片存储空间的两端,当元
素入栈时,两个栈的栈顶指针相向而行,这样的栈称为对顶栈。当|top -
1
top |==1时,表示共享栈满。这里初始化时,top =-1、top =n,所以top -
2 1 2 2
top ==1时,栈满。
1考点二: 栈的顺序结构
2.两个栈共享一个数组空间的好处是()。
A.减少存取时间,降低上溢出发生的概率
B.节省存储空间,降低上溢出发生的概率
C.减少存取时间,降低下溢出发生的概率
D.节省存储空间,降低下溢出发生的概率
0 1 … n-1 … STACKSIZE-1
data a a … a … b … b b
1 2 n m 2 1
top1 top2
栈1 栈2考点二: 栈的顺序结构
2.两个栈共享一个数组空间的好处是()。
A.减少存取时间,降低上溢出发生的概率
B.节省存储空间,降低上溢出发生的概率
C.减少存取时间,降低下溢出发生的概率
D.节省存储空间,降低下溢出发生的概率
B【解析】 共享栈的特点。共享栈可以节省存储空间,降低上溢出发生的概率,
不一定均分就是最好的方式。THANKSCON T EN T S
目录
考点一 栈的概念 ★★★★
考点二 栈的顺序结构 ★★
考点三 栈的链式结构
考点四 栈的应用 ★★★★★考纲框架
链式栈的定义
链式栈的操作【链栈的定义】考点三: 栈的链式结构
链栈:栈的链接存储结构 单链表是如何存储线性表的?
head
a a a a
∧
1 2 i n
top
P:用链表的哪一端作为栈顶?
A:为方便操作,用链头作为栈顶
a
n
为操作一致性,链栈带头结点
a
n-1
a
∧
1考点三: 栈的链式结构
top
typedef int ElemType;
typedef struct StackNode {
a
n
ElemType data; // 数据域
struct StackNode* next; // 指针域
a
n-1
} StackNode;
typedef struct {
StackNode* top; // 栈顶指针
} LinkStack;
a
∧
1考点三: 栈的链式结构
top
栈顶 栈底
a a … a ∧
n n-1 1
链栈的4要素:
⚫ 栈空条件:top->next=NULL
⚫ 栈满条件:一般不考虑
⚫ 进栈e操作:将存放e的结点插入到头结点之后
⚫ 退栈操作:取出头结点之后结点的元素并删除之【链栈的操作】考点三: 栈的链式结构
链栈的实现方式
(1)带头结点的实现(默认方式)
①栈空的条件:top->next == NULL。
s.top
∧考点三: 栈的链式结构
链栈的实现方式
(1)带头结点的实现(默认方式)
②栈满的条件:由于只有内存溢出时才出现栈满,通常不考虑这样的情况,所以在
链栈中可以看成不存在栈满考点三: 栈的链式结构
链栈的实现方式 s.top
p
(1)带头结点的实现(默认方式)
e
③元素e的进栈操作:新建一个结点存放元素e(由
a
n
p指向它),将结点p插入到头结点之后,其实现的
核心代码是p->next = top->next; top->next
a
n-1
= p;
a
∧
1考点三: 栈的链式结构
链栈的实现方式
s.top
(1)带头结点的实现(默认方式)
④出栈操作:取出首结点的data值并将其删
p
a
n
除,其实现的核心代码是p = top->next;
top->next = p ->next; free(p);
a
n-1
a
∧
1考点三: 栈的链式结构
链栈的实现方式
(2)不带头结点的实现
①栈空的条件top == NULL。考点三: 栈的链式结构
链栈的实现方式
(2)不带头结点的实现
②栈满的条件:由于只有内存溢出时才出现栈满,通常不考虑这样的情况,所以在
链栈中可以看成不存在栈满。考点三: 栈的链式结构
p
链栈的实现方式
s.top
s.top
a e
(2)不带头结点的实现 n
③元素e的进栈操作:新建一个结点存放元素
a
a
e(由p指向它),将结点p插入到头结点之后,其 n-1
n
实现的核心代码是p->next = top; top = p;
a
n-1
a
∧
1
a
∧
1考点三: 栈的链式结构
链栈的实现方式
s.top a a
(2)不带头结点的实现 n n
④出栈操作:取出首结点的data值并将其删除,
s.top
a a
其实现的核心代码是p = top-; top = p - n-1 n-1
>next; free(p);
a a
1 ∧ 1 ∧考点三: 栈的链式结构
初始化栈的函数
InitStack s.top
输入:无 ∧
功能:栈的初始化
输出:一个空栈
操作接口: InitStack(LinkStack& s)
// 成功,返回true
// 失败,返回false
bool InitStack(LinkStack& s) {
s.top = (StackNode*)malloc(sizeof(StackNode));
if (!s.top) {
return false;
}
s.top->next = NULL; // 栈空时栈顶指针为NULL
return true;
}考点三: 栈的链式结构
入栈的函数(头插)
s.top
p
Push
e
输入:元素值 x
a
n
功能:在栈顶插入一个元素 x
输出:如果插入成功,栈顶增加了一个 a
n-1
元素;否则返回失败信息
操作接口: bool push(LinkStack& s, ElemType e)
a
∧
1考点三: 栈的链式结构
s.top
p
入栈的函数(头插)
e
// 成功,返回true
a
// 失败,返回false
n
bool push(LinkStack& s, ElemType e) {
StackNode* p = (StackNode*)malloc(sizeof(StackNode));
a
n-1
if (!p) {
return false; // 栈节点分配失败
}
p->data = e;
p->next = s.top->next; // ①
s.top->next = p; // ②
a
∧
1
return true;
}
链栈的入栈操作为什么不用判断是否栈满?考点三: 栈的链式结构
s.top
出栈的函数(头删)
Pop
p
a
输入:无 n
功能:删除栈顶元素
输出:如果删除成功,返回被删元素值;否则返回失败信息
a
n-1
操作接口:bool pop(LinkStack& s, ElemType& e)
a
∧
1考点三: 栈的链式结构
// 成功,返回true
s.top
// 失败,返回false
bool pop(LinkStack& s, ElemType& e) {
p
a
if (s.top->next == NULL) {
n
return false; // 栈空
a
} n-1
StackNode* p = s.top->next; // ①
s.top->next = p->next; // 修改栈顶指针
②
e = p->data; // 获取栈顶元素 a
∧
1
free(p); // ③
return true;
}考点三: 栈的链式结构
取栈顶元素
top
GetTop
在栈不为空的条件下,将头结点后继数据结点的数据域赋给e。
a
e
n
操作接口:bool GetTop(LinkStack& s, ElemType& e)
a
{ n-1
if (s.top->next == NULL) {
return false; // 栈空
}
e = s.top->next->data; // 获取栈顶元素
return true;
a
∧
1
}【政哥题型总结】考点三: 栈的链式结构
1.一个栈顶指针为top的链栈指向头结点,则链栈为空的条件是( )。
A.top->next==NULL; B.top==NULL;
C.top->next!=NULL; D.top!=NULL;考点三: 栈的链式结构
1.一个栈顶指针为top的链栈指向头结点,则链栈为空的条件是( )。
A.top->next==NULL; B.top==NULL;
C.top->next!=NULL; D.top!=NULL;
InitStack top
输入:无 ∧
功能:栈的初始化
输出:一个空栈
// 成功,返回true
// 失败,返回false
bool InitStack(LinkStack& s) {
s.top = (StackNode*)malloc(sizeof(StackNode));
if (!s.top) {
return false;
}
s.top->next = NULL; // 栈空时栈顶指针为NULL
return true;
}考点三: 栈的链式结构
1.一个栈顶指针为top的链栈指向头结点,则链栈为空的条件是( )。
A.top->next==NULL; B.top==NULL;
C.top->next!=NULL; D.top!=NULL;
A【解析】 带头结点的单链表,其判空的条件是“top->next==NULL;”。
不带头结点的单链表,其判空的条件是“top==NULL;”。考点三: 栈的链式结构
2.一个栈顶指针为top的链栈指向头结点,在其中插入一个S所指结点,则执
行()。
A.top->next=S;
B.S->next=top->next;top->next=S;
C.S->next=top;top=S;
D.S->next=top;top=top->next;考点三: 栈的链式结构
入栈的函数(头插)
s.top
p
// 成功,返回true
e
// 失败,返回false
bool push(LinkStack& s, ElemType e) { a
n
StackNode* p = (StackNode*)malloc(sizeof(StackNode));
if (!p) {
a
return false; // 栈节点分配失败 n-1
}
p->data = e;
p->next = s.top->next; // ①
s.top->next = p; // ②
return true;
a
∧
1
}考点三: 栈的链式结构
2.一个栈顶指针为top的链栈指向头结点,在其中插入一个S所指结点,则执
行()。
A.top->next=S;
B.S->next=top->next;top->next=S;
C.S->next=top;top=S;
D.S->next=top;top=top->next;
B【解析】 带头结点的单链表,要插入一个结点S的操作是“S->next=top->
next;top->next=S;”。THANKSCON T EN T S
目录
考点一 栈的概念 ★★★★
考点二 栈的顺序结构 ★★
考点三 栈的链式结构
考点四 栈的应用 ★★★★★考纲框架
括号匹配
进制转换
函数调用
栈的应用
函数和递归
递归调用
表达式
前缀表达式
表达式求值 中缀表达式
后缀表达式
栈的作用考纲框架
进制转换
括号匹配
函数与递归调用
表达式求值考点四: 栈的应用
栈的应用中可以直接使用的函数
(1)栈顶(top())与栈底:允许元素插入与删除的一端称为栈顶,另
一端称为栈底。
(2)压栈( push() ):栈的插入操作,叫做进栈,也称压栈、入栈。
(3)弹栈( pop() ):栈的删除操作,也叫做出栈。
(4)初始化(initStack()): 栈的初始化操作【进制转换】考点四: 栈的应用
进制转换
十进制N向其它进制数d(二、八、十六)的转换是计算机实现计算的基
本问题。
转换法则:除留余数法
例如 (1348) = (2504) ,其运算过程如下:
10 8
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2考点四: 栈的应用
设计一个算法,利用栈将一个正十进制整数转换为二进制数并输出。
十进制  二进制:n=10
2 10
低位
2 5 10 % 2 = 0
2 2 5 % 2 = 1
用栈保
2 1 2 % 2 = 0 存
2 0 1 % 2 = 1 高位考点四: 栈的应用
进制转换
1. 初始化空栈
2. 十进制数N非零时,循环以下操作:
(1)N与d求余,余数入栈;
(2)N更新为N与d的商
3. 栈非空时,循环以下操作:
(1)弹出栈顶元素;
(2)输出e。考点四: 栈的应用
// 将十进制数n转换为d(二或八)进制数,并输出
void Convert(int n, int d) {
if (n == 0) { // 0的d进制数为0,特殊处理
printf("0\n"); return;
}
bool flag = false; // flag为true表示n为负数,需要输出负号
if (n < 0) {
flag = true; n = -n;
}
SqStack s;
InitStack(s);
while (n != 0) {
push(s, n % d); // 取余,余数入栈
n /= d; // 商作为新的被除数
}
if (flag) printf("-"); // n为负数,输出负号
while (!Empty(s)) { // 栈不为空,输出栈中元素
ElemType e;
pop(s, e); // 弹出栈顶元素
printf("%d", e); // 输出栈顶元素
}
printf("\n");
}【括号匹配】考点四: 栈的应用
括号匹配
在文字处理软件或编译程序设计时,常常需要检查一个字符串或一
个表达式中的括号是否相匹配?
例如:[ 4 + (2 + 8 ) * [ 5 / ( 9 – 7 ) ] * 3
只看括号: [ ( ) [ ( ) ]
约定:在括号匹配中只允许出现 [ ] ( ) 而没有{ }考点四: 栈的应用
括号匹配
匹配思想:从左至右扫描一个字符串(或表达式),则每个右括号将与最
近遇到的那个左括号相匹配。
[ ( ) [ ( ) ] ]
在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到
一个右括号时,就将它与栈顶的左括号(如果存在)相匹配,同时从栈顶
删除该左括号。考点四: 栈的应用
括号匹配
匹配成功的条件很简单:每一个检测到的括号与已检测到的优先级最高
的括号都匹配。
匹配失败的条件:
(1)检测到与已检测到的优先级最高的括号不匹配的括号;
(2)扫描完整个表达式,还是有已检测到的括号没有完成匹配;考点四: 栈的应用
括号匹配
算法思想:
➢ 设置一个栈,
➢ 当读到左括号时,左括号进栈。
➢ 当读到右括号时,则从栈中弹出一个元素,与读到的左括号进行匹
配,若匹配成功,继续读入;
➢ 否则匹配失败,返回FALSE。考点四: 栈的应用
表达式括号不配对情况的演示
例如:exp=“( ( ) ) )”
① ‘(‘进栈
② ‘(‘进栈
③ 遇到’)’,栈顶为’(‘,退栈
(
④ 遇到’)’,栈顶为’(‘,退栈
(
⑤ 遇到’)’,栈为空,返回false考点四: 栈的应用
表达式括号配对情况的演示
例如:exp=“( ( ) )”
① ‘(‘进栈
② ‘(‘进栈
( ③ 遇到’)’,栈顶为’(‘,退栈
(
④ 遇到’)’,栈顶为’(‘,退栈
栈空且exp扫描完,返回true考点四: 栈的应用
bool MatchBrackets(char* exp) {
if (exp == NULL) { return false; }
SqStack s;
InitStack(s);
for (int i = 0; exp[i] != '\0'; i++) {
if (exp[i] == '(' || exp[i] == '[') {
push(s, exp[i]); // 左括号入栈
} else if (exp[i] == ')') {
ElemType x;
pop(s, x); // 遇到右括号,弹出栈顶元素
if (x != '(') {
return false;
}
} else if (exp[i] == ']') {
ElemType x;
pop(s, x); // 遇到右括号,弹出栈顶元素
if (x != '[') return false;
} else {
; // 忽略其他字符
}
}
return Empty(s); // 栈为空,匹配成功
}【函数与递归调用】考点四: 栈的应用
递归调用
递归调用:一个函数(或过程)直接或间接地调用自己本身,简称递归。
从前有座山,山里有个庙,庙里有个老和尚和一个小和尚。一天,老
和尚在对小和尚讲故事,故事的内容是:从前有座山,山里有个庙,庙里
有个老和尚和一个小和尚。一天,老和尚在对小和尚讲故事,故事的内
容是:从前有座山,山里有个庙,庙里有个老和尚和一个小和尚。一天,
老和尚在对小和尚讲故事,故事的内容是……如此循环往复,这就像数
学的无限循环,永远也讲不完……考点四: 栈的应用
递归调用
递归是程序设计中的一个强有力的工具。因为递归函数结构清晰,程序易
读,正确性很容易得到证明。
例如:求解N!,阶乘的递归公式为
1 , N < 0
𝑓 N = ቐ
N ∗ 𝑓(N − 1), 𝑁 > 0考点四: 栈的应用
递归调用
递归是程序设计中的一个强有力的工具。因为递归函数结构清晰,程序易
读,正确性很容易得到证明。
例如:求解N!
①
int fact(int n) {
①递归初始条件
if (n<=1)② return 1;
递归三要素
②递归终止条件
return n * fact(n-1);
③
③递归转移条件
}
A. O(log n) B. O(n) C. O(nlog n) D. O(n2)
2 2考点四: 栈的应用
递归调用
递归是程序设计中的一个强有力的工具。因为递归函数结构清晰,程序易
读,正确性很容易得到证明。
例如:求解N, 当N等于5时,调用和执行过程:
5 != 5 * 4!
4 != 4 * 3!
3!= 3 * 2!
2!= 2 * 1!
1!= 1 * 0!
0! = 1考点四: 栈的应用
递归调用
栈的另一个重要应用是在程序设计语言中实现递归和函数调用。
遵循的基本准则是:先调用和后执行特征。
栈顶
求解N!,阶乘的递归公式为 𝑓(1)
𝑓(2)
1, N < 0 …
𝑓 N = ቐ
𝑓(N − 3)
N ∗ 𝑓(N − 1), 𝑁 > 0
𝑓(N − 2)
𝑓(N − 1)
栈底
𝑓(N)
栈考点四: 栈的应用
递归调用
void main(){
int a,b,c;
func1(a);
}
栈顶
void func1(int a){
int x;
func2
func1
func2(x);
栈底
main
}
void func2(int x){ 栈
int m,n;
}【栈的应用】考点四: 栈的应用
➢ 问题描述
这里限定的简单表达式求值问题是:用户输入一个包含“+”、“-”、
“*”、“/”、正整数和圆括号的合法算术表达式,计算该表达式的运算结果。考点四: 栈的应用
➢ 数据组织
简单表达式采用字符数组exp表示,其中只含有“+”、“-”、“*”、
“/”、正整数和圆括号。
为了方便,假设是合法的算术表达式,例如,exp=“1+2*(4+12)”;
在设计相关算法中用到栈,这里采用顺序栈存储结构。考点四: 栈的应用
➢ 运算算法设计
• 中缀表达式:1 + 2 * 3
• 后缀表达式:1 2 3 * + 运算数的相对次序相同
• 前缀表达式:+ 1 * 2 3考点四: 栈的应用
➢ 运算算法设计
运算符位于两个操作数中间的表达式称为中缀表达式。例如,"1+2*3"就是
一个中缀表达式。
中缀表达式的运算规则:“先乘除,后加减,从左到右计算,先括号内,
后括号外”。
因此,中缀表达式不仅要依赖运算符优先级,而且还要处理括号。考点四: 栈的应用
➢ 运算算法设计
算术表达式的另一种形式是后缀表达式或逆波兰表达式,就是在算术表达
式中,运算符在操作数的后面。
如"1+2*3"的后缀表达式为"1 2 3 * +"。
后缀表达式特点:
⚫ 没有括号,已考虑了运算符的优先级。
⚫ 只有操作数和运算符,而且越放在前面的运算符来越优先执行。考点四: 栈的应用
➢ 运算算法设计
在算术表达式中,如果运算符在操作数的前面,称为前缀表达式,如
"1+2*3"的前缀表达式为"+ 1 * 2 3"。考点四: 栈的应用
➢ 运算算法设计
语法树: 语法树即将运算符作为根节点,将数字作为左右节点。
以中缀表达式A+B*(C-D)+E/F为例画出一颗语法树,步骤:
(1)从当前的中缀表达式中选择最先执行的四则运算符,作为当前的根节点,
若没有运算符,将数字写在对应的节点处;
(2) 接着再选择剩余中次优先执行的四则运算,作为当前的根节点,重复步骤
(1)(2);考点四: 栈的应用
• 中缀表达式:A+B*(C-D)+E/F (二叉树的中序遍历)
A+B*(C-D)+E/F • 后缀表达式:ABCD-*+EF/+ (二叉树的后序遍历)
• 前缀表达式:++A*B-CD/EF (二叉树的先序遍历)
+
• 计算机内部用哪个?后缀表达式
/
+
E F
A *
B -
C D考点四: 栈的应用
➢ 运算算法功能
中缀表达式的求值过程:
⚫ 将中缀算术表达式转换成后缀表达式。
⚫ 对该后缀表达式求值。
数栈S1
符栈S2考点四: 栈的应用
➢ 中缀表达式的求值:
1)转化前先建立两个栈,命名为s1和s2。用栈s1存储表达式中的运算数,用
栈s2存储符;
2)在转化的过程中需从左到右扫描中缀表达式的每一个运算数和符号,若是运
算数就压入栈s1中;考点四: 栈的应用
➢ 中缀表达式的求值:
3)若扫描到的是符号,设符号是C,则以下情况需要将C压入到s2:
① 若s2为空,则C入栈s2;
② 若C为左括号,则C入栈s2;
③ 若s2的栈顶运算符为左括号,则C入栈s2;
④ 若s2的栈顶运算符的优先级小于C,则C入栈s2; [右括号的优先级最低]
⑤否则,就要将s2的栈顶运算符弹出,从s1中弹出两个(也可能是1个)运算数,
进行运算,并把运算的结果压回s1。 回到3)
4)扫描到表达式结束,若最后栈s2中还有符号,则将其依次出栈,并从s1中弹
出两个(也可能是1个)运算数,进行运算,并把运算的结果压回s1。回到3)。
5)最终完成转化过程。考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
1)初始时,s1和s2为空; 从左往后扫描表
达式;
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
首先扫描到9,是运算数,放入s1中
9
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
遇到”+“,此时C= ”+“,s2为空,符合
①(若s2为空,则C入栈s2;),将”+“压
入s2中,
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
接着扫描到“(”;此时C= ”(“,符合②若C
为左括号,则C入栈s2; ,将”(“压入s2中;
(
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
接着扫描到“(”;此时C= ”(“,符合②若C
为左括号,则C入栈s2; ,将”(“压入s2中;
(
(
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
接着扫描到3,是运算数,放入s1中;
(
3 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
遇到”*“,此时C= ”*“,栈顶是左括号,
符合③若s2的栈顶运算符为左括号,则C入
栈s2;
*
, 将”*“压入s2中;
(
3 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
接着扫描到2,是运算数,放入s1中;
*
2 (
3 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
遇到“)”,此时C= “)”,符合⑤要将
s2的栈顶运算符弹出,从s1中弹出两个(也
可能是1个)运算数,进行运算,并把运算的
*
结果压回s1 ,则将“*”从s2中弹出,2和3
2 (
从s1中弹出。进行运算,并将2*3的值6放入
36 (
9 + s1中,左括号和右括号配对离开。
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
扫描到“+”,此时C= ”+“,栈顶是左括
号,符合③若s2的栈顶运算符为左括号,则
C入栈s2;
, 将”+“压入s2中;
+
6 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
扫描到“(”;此时C= ”(“,符合②若C为
左括号,则C入栈s2;
将”(“压入s2中
(
+
6 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
接着扫描到3,是运算数,放入s1中;
(
3 +
6 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
扫描到“-”,此时C= ”-“,栈顶是左括号,
符合③若s2的栈顶运算符为左括号,则C入
栈s2;
-
(
, 将”-“压入s2中;
3 +
6 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
接着扫描到1,是运算数,放入s1中;
-
1 (
3 +
6 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
遇到“)”,此时C= “)”,符合⑤要将
s2的栈顶运算符弹出,从s1中弹出两个(也
可能是1个)运算数,进行运算,并把运算
-
1 (
的结果压回s1 ,则将“-”从s2中弹出,1和
23 +
3从s1中弹出。进行运算,并将3-1的值2放
6 (
9 + 入s1中,左括号和右括号配对离开。
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
遇到“)”,此时C= “)”,符合⑤要将
s2的栈顶运算符弹出,从s1中弹出两个(也
可能是1个)运算数,进行运算,并把运算的
结果压回s1 ,则将“-”从s2中弹出,2和6
2 +
从s1中弹出。进行运算,并将6+2的值8放入
68 (
9 + s1中,左括号和右括号配对离开。
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
遇到“/”,此时C= “/”,符合④若s2的栈
顶运算符的优先级小于C,则C入栈s2; [右括
号的优先级最低]
,则将“/” 压入s2中;
8 /
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
接着扫描到2,是运算数,放入s1中;
2
8 /
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
表 达 式 扫描结 束 , s1 和 s2 不空 , 从 s2弹
出”/”,从s1中弹出2和8,运算8/2=4,并把
结果放回到s1中.
2
48 /
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
再从从s2弹出”+”,从s1中弹出9和4,运算
结果是13
4
193 +
数栈S1 符栈S2考点四: 栈的应用
➢ 中缀表达式转后缀表达式:
规则与表达式求值相同,不同点是:
1、从S2中弹出的运算符,压到S1中,请注意S1不弹栈
2、从S2中弹出的左括号,不压到S1中,考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
1)初始时,s1和s2为空; 从左往后扫描表
达式;
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
首先扫描到9,是运算数,放入s1中
9
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
遇到”+“,此时C= ”+“,s2为空,符合
①(若s2为空,则C入栈s2;),将”+“压
入s2中,
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
接着扫描到“(”;此时C= ”(“,符合②若C为
左括号,则C入栈s2; ,将”(“压入s2中;
(
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
接着扫描到“(”;此时C= ”(“,符合②若C为
左括号,则C入栈s2; ,将”(“压入s2中;
(
(
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
接着扫描到3,是运算数,放入s1中;
(
3 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
遇到”*“,此时C= ”*“,栈顶是左括号,
符合③若s2的栈顶运算符为左括号,则C入栈
s2;
*
, 将”*“压入s2中;
(
3 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
接着扫描到2,是运算数,放入s1中;
*
2 (
3 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
遇到“)”,此时C= “)”,符合⑤要将
s2的栈顶运算符弹出,压到S1中,则将“*”
从s2中弹出压到S1中,左括号和右括号配对
* *
离开。
2 (
3 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
扫描到“+”,此时C= ”+“,栈顶是左括号,
符合③若s2的栈顶运算符为左括号,则C入栈s2;
, 将”+“压入s2中;
*
+
2
3 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
扫描到“(”;此时C= ”(“,符合②若C为左括
号,则C入栈s2;
将”(“压入s2中
* (
+
2
3 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
接着扫描到3,是运算数,放入s1中;
3
* (
+
2
3 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
扫描到“-”,此时C= ”-“,栈顶是左括号,
符合③若s2的栈顶运算符为左括号,则C入栈s2;
, 将”-“压入s2中;
3 -
* (
+
2
3 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
接着扫描到1,是运算数,放入s1中;
1
3 -
* (
+
2
3 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
遇到“)”,此时C= “)”,符合⑤要将
-
s2的栈顶运算符弹出,压到S1中,则将“-”
1
从s2中弹出压到S1中,左括号和右括号配对
3 -
* ( 离开。
+
2
3 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
+
遇到“)”,此时C= “)”,符合⑤要将
-
s2的栈顶运算符弹出,压到S1中,则将“+”
1
从s2中弹出压到S1中,左括号和右括号配对
3
* 离开。
+
2
3 (
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
+
遇到“/”,此时C= “/”,符合④若s2的
-
栈顶运算符的优先级小于C,则C入栈s2; [右
1
括号的优先级最低]
3
* ,则将“/” 压入s2中;
2
3 /
9 +
数栈S1 符栈S2考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
2
接着扫描到2,是运算数,放入s1中;
+
-
1
3
*
/
2
+
3
9
符栈S2
数栈S1考点四: 栈的应用
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
+
/ 表达式扫描结束,s2不空,从s2弹出“/”和
2
“+”放入到S1中。
+
当S2为空时,S1中就是后缀表达式。
-
1 后缀表达式:9 32* 31- + 2/ +
3
/
*
+
2
符栈S2
3
9
数栈S1考点四: 栈的应用
➢ 中缀表达式的求值:【规则再探】
若扫描到的是符号,设符号是C,则以下情况需要将C压入到s2:
① 若s2为空,则C入栈s2;
② 若C为左括号,则C入栈s2;
③ 若s2的栈顶运算符为左括号,则C入栈s2;
④ 若s2的栈顶运算符的优先级小于C,则C入栈s2; [右括号的优先级最低]
⑤否则,就要将s2的栈顶运算符弹出,从s1中弹出两个(也可能是1个)运算数,
进行运算,并把运算的结果压回s1。 回到3)
4)扫描到表达式结束,若最后栈s2中还有符号,则将其依次出栈,并从s1中弹
出两个(也可能是1个)运算数,进行运算,并把运算的结果压回s1。回到3)。
5)最终完成转化过程。考点四: 栈的应用
➢ 中缀表达式的求值:【规则再探】
假如有一个表达式:9 +((3 * 2)+(3 - 1))/ 2
① 若s2为空,则C入栈s2;
② 若C为左括号,则C入栈s2;
③ 若s2的栈顶运算符为左括号,则C入栈s2;
④ 若s2的栈顶运算符的优先级小于C,则C入栈s2; [右括号的优先级最低]
( ( (【政哥题型总结】考点四: 栈的应用
1、表达式a*(b+c)-d的后缀表达式是( )。
A.abcd*+- B. abc+*d-
C. abc*+d- D. -+*abcd考点四: 栈的应用
1、表达式a*(b+c)-d的后缀表达式是( )。
A.abcd*+- B. abc+*d-
C. abc*+d- D. -+*abcd
根据运算顺序构建二叉树:
-
d
*
后序遍历: abc+*d-
a +
b c考点四: 栈的应用
1、表达式a*(b+c)-d的后缀表达式是( )。
A.abcd*+- B. abc+*d-
C. abc*+d- D. -+*abcd
B【解析】后缀表达式是运算符在对应的操作数的后面。所以首先是bc+,然后
是a bc+ *,最后是a bc+ * d-; 大家在写的过程,需要注意,运算符的顺序是
不变的。考点四: 栈的应用
2、假设栈初始为空,将中缀表达式a/b-(c * d+e * f)/g转化为等价后缀表达式
过程中,当扫描到f时,栈中的元素依次为( )
A. /-+* B.-(+* C.-(*+ D./-(*+*考点四: 栈的应用
B【解析】方法一:
将中缀表达式转换后缀表达式的过程如下,如图:
从左向右开始扫描中缀表达式;遇到数字时,加入后缀表达式;遇到运算符时:
a.若为‘(’,入栈;
b.若为‘)’,则一次把栈中的运算符加入后缀表达式中,直到出现‘(’,
从栈中删除‘(’;
c.若为除括号外的其他运算符,当其优先级高于除‘(’意外的栈顶运算符时,
直接入栈。否则从栈顶开始,一次弹出比当前处理的运算符优先级高和优先级
相等的运算符,直到一个比它优先级低的或者遇到了一个左括号位置。
(4)当扫描的中缀表达式结束时,栈中的所有运算符一次出栈加入后缀表达式。考点四: 栈的应用
本题操作过程如图所示
1.-入栈,并把/挤出栈,栈中剩下-
2.(直接入栈。栈里从底到顶为-(
3.*级别高于(,*入栈,栈里从底到顶为-(*
4.+入栈,因为+低于*,所以-把*挤出栈,栈里从底到顶为-(+
5.*优先级高于+,*入栈。栈里从底到顶为-(+*
设 s1为操作数栈,s2为运算符栈,表中 R1 代表 a/b,R2代表c * d。考点四: 栈的应用
方法二:请大家回顾一下,运算符号的入栈规则,若扫描到的是符号,设符号
是C,则以下情况需要将C压入到s2:
① 若s2为空,则C入栈s2;
② 若C为左括号,则C入栈s2;
③ 若s2的栈顶运算符为左括号,则C入栈s2;
④ 若s2的栈顶运算符的优先级小于C,则C入栈s2; [右括号的优先级最低]
从上述四条规则中,我们可以发现,规则①②③都是特殊情况,要么与空栈
有关,要么与左括号有关。在排除左括号和运算符栈为空的情况下,只有规则
④,要想将当前运算符入栈,必须是当前符号的运算优先级高于当前栈顶运算
符的优先级。所以运算符栈中运算符以左括号为界,左括号左右两边的运算符
的运算优先级都是升高的,结合这个结论,可以可到只有B选项符合这个规则。考点四: 栈的应用
3、假设栈初始为空,将中缀表达式a/b-(c * d+e * f)/g转化为等价后缀表达式
过程中,用栈来存放暂时还不能确定运算次序的操作符,若栈初始时为空,则
转换过程中同时保存在栈中的操作符的最大个数是()。
A. 2 B. 3 C. 4 D. 5考点四: 栈的应用
3、假设栈初始为空,将中缀表达式a/b-(c * d+e * f)/g转化为等价后缀表达式
过程中,用栈来存放暂时还不能确定运算次序的操作符,若栈初始时为空,则
转换过程中同时保存在栈中的操作符的最大个数是()。
A. 2 B. 3 C. 4 D. 5
C【解析】方法一,参考第2题的解题过程,运算符栈的最大值是4。考点四: 栈的应用
方法二:计算机的运算规则是程序员设计的,则表达式转换的也符合程序员的
四则运算规则。在转换过程中,我们可以用四则运算进行表示,运算过程如图
所考点四: 栈的应用
(1)从左往右,扫描到‘/’,直接入栈,此时栈中只有‘/’
(2)扫描到‘+’,则‘/’需要弹出运算,此时栈中只有‘+’
(3)扫描到‘(’,则‘(’需要压入栈中,此时栈中只有‘+(’
(4)扫描到‘*’,则‘*’需要压入栈中,此时栈中只有‘+( *’
(5)扫描到‘-’,则‘/’需要弹出运算,然后‘-’需要压入栈中,此时栈
中只有‘+( -’
(6)扫描到‘*’,则‘*’需要压入栈中,此时栈中只有‘+( - *’
(7)扫描到‘)’,则‘*’、‘-’需要弹出运算,此时栈中只有‘+’
(8)扫描到‘/’,则‘/’需要压入栈中,此时栈中只有‘+ /’
综上,可以看到栈的最大容量是4,此时栈中的运算符是‘+( - *’。考点四: 栈的应用
4、求表达式的值用到栈,设立运算数栈 OPEN。若 OPEN 只有两个存储单元,
则下面表达式中,不会发生溢出的是()。
A、 A-B∗(C-D) B、 (A-B)∗C-D
C、 (A-B∗C)-D D、 (A-B)∗(C-D)考点四: 栈的应用
B【解析】方法一:大家可以用栈的结构进行求解。用栈存储运算数,就是在
表达式转换的过程中,用栈存储数值和中间结果。
A选项,首先遇到A,需要将A放入到栈中,然后遇到-,再次遇到B,需要将B
放入到栈中,然后遇到*,因为*优先级高于-,所有此时不能运算。继续扫描,
遇到C,此时需要3个空间存储数值,会发生溢出。
B选项,首先遇到A,需要将A放入到栈中,然后遇到-,再次遇到B,需要将B
放入到栈中,这里有括号,会将(A-B)运算。然后遇到*,继续扫描,遇到C;
继续扫描,遇到-; 此时*优先级高于-,需要先进行运算(A-B)*C,继续扫
描D,运算 (A-B)∗C-D。只需要2个空间存储数据。
相同的方法,可以分析C和D选项。考点四: 栈的应用
B【解析】方法二:我们可以借鉴第3题中方法和结论,伴随着运算符栈的增加,
运算数栈的大小也会增加,同样的,伴随着运算符栈的减小,运算数栈的大小
也会减小。
A选项,A-B∗(C-D),运算符号的入栈顺序是-*(,则栈中运算符号超过了2个,
则运算数栈中的运算数肯定会超过2个。
C选项,(A-B∗C)-D,运算符号的入栈顺序是-*,则栈中运算符号超过了2个,
则运算数栈中的运算数肯定会超过2个。
D选项,(A-B)∗(C-D),首先运算A-B,后续运算符号的入栈顺序是*(-,则栈
中运算符号超过了2个,则运算数栈中的运算数肯定会超过2个。
B选项,(A-B)∗C-D,首先运算A-B,接着运算 (A-B)∗C,最后运算(A-B)∗C-D,
在此过程中运算栈中的运算符不会超过1个,因此运算数栈中的运算数不会超
过2个。THANKS