文档介绍：2018年5月16日
数据结构
2018年5月16日
栈
栈的应用
栈与递归
队列
队列的应用
教学内容
2018年5月16日
第3章栈和队列
掌握栈和队列的特点,并能在相应的应用问题中正确选用
熟练掌握栈的两种存储结构的基本操作实现算法,特别应注意栈满和栈空的条件
熟练掌握循环队列和链队列的基本操作实现算法,特别注意队满和队空的条件
理解递归算法执行过程中栈的状态变化过程
教学目标
2018年5月16日
栈(Stack)
1. 定义
2. 逻辑结构
3. 存储结构
4. 运算规则
5. 实现方式
队列(Queue)
1. 定义
2. 逻辑结构
3. 存储结构
4. 运算规则
5. 实现方式
2018年5月16日
栈
1. 定义
用顺序栈或链栈存储均可,但以顺序栈更常见
3. 存储结构
与线性表相同,仍为一对一关系
2. 逻辑结构
只能在表的一端(栈顶)进行插入和删除运算的线性表
2018年5月16日
只能在栈顶运算,且访问结点时依照后进先出(LIFO)或先进后出(FILO)的原则
关键是编写入栈和出栈函数,具体实现依顺序栈或链栈的不同而不同
基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等
2018年5月16日
栈是一种特殊的线性表,它只能在表的一端(栈顶)进行插入和删除运算
栈与一般线性表的区别:仅在于运算规则不同
“进”=压入=PUSH()
“出”=弹出=POP( )
一般线性表
逻辑结构:一对一
存储结构:顺序表、链表
运算规则:随机、顺序存取
栈
逻辑结构:一对一
存储结构:顺序栈、链栈
运算规则:后进先出
栈与一般线性表的区别
2018年5月16日
“进”=压入=PUSH()
“出”=弹出=POP( )
2018年5月16日
a1
a2
……
an
顺序栈S
ai
……
表头
表尾
栈底base
栈顶top
低地址
高地址
写入:v[i]= ai
读出: x= v[i]
压入:PUSH (an+1)
弹出: POP (x)
前提:一定要预设栈顶指针top!
低地址
高地址
v[i]
a1
a2
ai
an
……
顺序表V[n]
……
an+1
顺序栈与顺序表
2018年5月16日
顺序栈的表示
空栈
base == top 是栈空标志
stacksize = 4
top
A
base
base
top
A
B
A
B
C
top
base
top
base
A
B
C
D
base
top
3
1
2
0
top 指示真正的栈顶元素之上的下标地址
栈满时的处理方法:
1、报错,返回操作系统。
2、分配更大的空间,作为栈的存储空间,将原栈的内容移入新栈。