数据结构教案

第三章 栈和队列

数据结构教案 第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={|ai-1,ai∈D, i=2,3,…,n } 基本操作：

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