【精品】PPT课件 3.1 栈3.2 栈的应用举例 3.3 队列.ppt

文档介绍：栈
栈的应用举例
队列
第3章栈和队列
重点: (1)栈、队列的定义、特点、性质和应用;(2)ADT栈、ADT队列的设计和实现以及基本操作及相关算法。
难点: (1)循环队列中对边界条件的处理;(2)分析栈和队列在表达式求值、括号匹配、数制转换、迷宫求解中的应用实例,提高利用栈和队列解决实际问题的应用水平。
本章重点难点
栈
抽象数据类型栈的定义
栈的表示和实现
抽象数据类型栈的定义
栈的定义
栈(Stack)是一种特殊的线性表,其插入和删除操作均在表的一端进行,是一种运算受限的线性表。
栈顶(top)是栈中允许插入和删除的一端。
栈底(bottom)是栈顶的另一端。
栈的术语
栈的特点
栈的示意图
后进先出(Last In First Out,简称LIFO)。又称栈为后进先出表(简称LIFO结构)。
an
…
…
a2
a1
栈底
栈顶
入栈
出栈
抽象数据类型栈的定义
ADT Stack {
数据对象:
数据关系:
抽象数据类型栈
基本操作:
} ADT Stack
R1={ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }
约定an 端为栈顶,a1 端为栈底。
D={ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
见下页
抽象数据类型栈的定义
InitStack(&S) //初始化栈
DestroyStack(&S) //销毁栈
ClearStack(&S) //清空栈
StackEmpty(S) //判栈空
StackLength(S) //求栈长度
GetTop(S, &e) //取栈顶元素
Push(&S, e) //入栈
Pop(&S, &e) //出栈
StackTravers(S, visit()) //遍历栈
栈的基本操作
抽象数据类型栈的定义
栈的表示和实现
//----- 栈的顺序存储表示-----
#define STACK_INIT_SIZE 100; //存储空间初始分配量
#define STACKINCREMENT 10; //存储空间分配增量
typedef struct {
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //当前可使用最大容量
} SqStack;
SqStack S;
顺序栈的C语言实现