数据结构教案
第三章 栈和队列
数据结构教案 第3章 栈和队列
目 录
3.1 栈的基本概念 ......................................................................................................................... 2
3.1.1 栈的抽象数据类型定义 .............................................................................................. 2 3.1.2 顺序栈 .......................................................................................................................... 2 3.1.3 链栈 .............................................................................................................................. 4 3.2 栈的应用 ................................................................................................................................. 4
3.2.1 数制转换：将十进制数N转换成其他d进制数 ...................................................... 4 3.2.2 括号匹配的检验 .......................................................................................................... 4 3.2.3 行输入处理程序 .......................................................................................................... 4 3.2.4 迷宫求解 ...................................................................................................................... 5 3.2.5 表达式求值 .................................................................................................................. 5 3.3 栈与递归的实现 ..................................................................................................................... 6 3.4 队列的基本概念 ..................................................................................................................... 6
3.4.1 队列的抽象数据类型定义 .......................................................................................... 6 3.4.2 链队列 .......................................................................................................................... 7 3.4.3 循环队列 ...................................................................................................................... 8 3.5 队列与栈的应用 ..................................................................................................................... 8
3.5.1 离散事件模拟 .............................................................................................................. 8
1
数据结构教案 第3章 栈和队列
第3章 栈和队列
3.1 栈的基本概念
3.1.1 栈的抽象数据类型定义 1、栈的逻辑特征
1） 限定在表尾进行插入或删除操作的线性表； 2） 栈顶——表尾端；栈底——表头端 3） 后进先出的线性表
2、抽象数据类型的定义
ADT Stack{
数据对象：D={ai |ai∈ElemSet, i=1,2,…,n, n≥0}
数据关系：R={R1},R1={
InitStack( &S )
操作结果：构造一个空的栈S DestroyStack( &S )
初始条件：栈S已存在 操作结果：销毁栈S ClearStack( &S )
初始条件：栈S已存在
操作结果：将栈S重置为空栈 StackEmpty( S )
初始条件：栈S已存在
操作结果：若S为空栈，则返回TRUE，否则返回FALSE StackLength( S )
初始条件：栈S已存在
操作结果：返回栈S中数据元素的个数 GetTop( S, &e )
初始条件：栈S已存在且非空 操作结果：用e返回S中栈顶元素 Push( &S, e )
初始条件：栈S已存在
操作结果：插入元素e为新的栈顶元素 Pop( &S, &e )
初始条件：栈S已存在且非空
操作结果：删除S的栈顶元素，并用e返回其值 StackTraverse( S, visit( ) )
初始条件：栈S已存在且非空
操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit( )。一
旦visit( )失败，则操作失败
}ADT Stack
思考：栈的取元素、插入、删除操作与线性表的相应操作有何区别，为什么？ 3.1.2 顺序栈
2