数据结构栈和队列.ppt

文档介绍：数据结构——栈和队列
1
重点：栈和队列的基本特征，表示与实现
难点：递归、循环队列
第三章 栈和队列
2
第三章 栈和队列
栈
栈的应用举例
栈与递归的实现
队列
3
栈
定义
特殊的线性表：操作受限的线性表
是限定仅在表尾进行插入或删除操作的线性表
允许插入,删除的一端称为栈顶(top),另一端称为栈底(bottom)
逻辑特征
后进先出(LIFO)
ADT Stack
初始化空栈、入栈、出栈
判断栈空、判断栈满
取栈顶
top
bottom
进栈
出栈
an
.
.
.
.
a1
4
栈–顺序栈的表示与实现
顺序栈
约定与类型定义：top的含义
基本操作的实现
base
空栈
a 进栈
b 进栈
a
top
base
top
base
top
a
b
约定：top指向栈顶元素的下一个位置
5
栈–顺序栈的表示与实现
base
e 进栈
f 进栈溢出
e出栈
edcba
top
base
top
base
top
约定：top指向栈顶元素的下一个位置
edcba
顺序栈
dcba
6
栈–链栈的表示与实现
约定：top指向栈顶元素所在的结点
链栈
无栈满问题(除非分配不出内存), 空间可扩充
栈顶----链表的表头
可以不必引入头结点
N
^
top
7
栈的应用举例
数制转换
括号匹配的检验
行编辑程序
迷宫求解
表达式求值
8
队列
定义
特殊的线性表：操作受限的线性表
只允许在一端进行插入，而在另一端删除元素
允许插入的一端为队尾(rear),允许删除的一端为队头(head)
双端队列：限定插入和删除操作在表的两端进行
逻辑特征：先进先出(FIFO)
ADT Queue：初始化空队、入队、出队、判断队空、判断队满、取队头
队头
入队
出队
a1
a2
a3
…
…
an
队尾
9
队列–链队列的表示与实现
链队列
约定与类型定义：
基本操作的实现
无队满问题(除非分配不出内存), 空间可扩充
引入头结点(一定需要吗？)
top
a1
a2
an
^


10