第二 栈和队列 操作受限的线性表 3.1栈 3.1.1抽象数据类型栈的定义 3.1.2栈的表示与实现 3.2栈的应用举例 3.2.1数制转换 3.2.4迷宫求解 3.2.5表达式求值 *3.3栈和递归的实现 3.4队列 3.4.1抽象数据类型队列的定义 3.4.2链队列—队列的链式表示与实现 3.4.3循环队列—队列的顺序表示与实现
3.1 栈 3.1.1抽象数据类型栈的定义 3.1.2栈的表示与实现 3.2 栈的应用举例 3.2.1 数制转换 3.2.4 迷宫求解 3.2.5 表达式求值 *3.3 栈和递归的实现 3.4 队列 3.4.1抽象数据类型队列的定义 3.4.2 链队列 -- 队列的链式表示与实现 3.4.3 循环队列 -- 队列的顺序表示与实现 第三章 栈和队列 ----- 操作受限的线性表
3.1栈 3.1.1抽象数据类型栈的定义 栈( stack):先进后出(FLO)的线性表。 或后进先出(LIFO)的线性表。 或仅在表尾进行插入和删除操作的线性表 栈顶(top):线性表的表尾端,即可操作端。 栈底( bottom):线性表的表头 栈底 栈顶 出栈(pop) a1 a, a 3 an-lan 入栈(push)
栈（stack）: 先进后出( FILO）的线性表。 • 或后进先出（ LIFO）的线性表。 • 或仅在表尾进行插入和删除操作的线性表。 栈顶（top）: 线性表的表尾端，即可操作端。 栈底（bottom）: 线性表的表头。 3.1 栈 3.1.1 抽象数据类型栈的定义 栈底 栈顶 a ...... 1 a2 a3 an-1 an 入栈(push) 出栈(pop)
栈的抽象数据类型 ADT Stack i 数据对象:D={a1|a1属于 Elemnet, 1,2,,n,n≥0) 数据关系:项a为栈 a1a1,>la1a1属于 D,(-23,,n)} 基本操作: InitStack(&s) DestroyStack(&s) ClearStack(&s); StackEmpty(s); StackLength(S); GetTop(s, &e); Push(&s,e); Pop(&s, &e); StackTraverse(S, visit O) ADT Stack
栈的抽象数据类型 ADT Stack { 数 据 对 象 ： D = {ai | ai 属 于 Elemset, (i=1,2,…,n, n≥0)} 数据关系 ： R1 = { ＜ ai-1 ,ai ＞ |ai-1 ,ai 属 于 D,(i=2,3,…,n)} 约定an为栈顶, a1为栈底。 基本操作： • InitStack(&S); DestroyStack(&S); • ClearStack(&S); StackEmpty(S); • StackLength(S) ; GetTop(S,&e); • Push(&S,e); Pop(&S,&e); • StackTraverse(S,visit ()) }ADT Stack
栈的基本操作(之一) InitStack(&s) 操作结果:构造一个空的栈S。 DestroyStack(&s) 初始条件:栈S已经存在。 操作结果:销毁栈S。 ClearStack(&s) 初始条件:栈S已经存在。 操作结果:将栈S重置为空栈
栈的基本操作(之一) InitStack(&S) • 操作结果:构造一个空的栈S。 DestroyStack(&S) • 初始条件: 栈S已经存在。 • 操作结果: 销毁栈S。 ClearStack(&S) • 初始条件: 栈S已经存在。 • 操作结果: 将栈S重置为空栈
栈的基本操作(之二) StackEmpty(s) 初始条件:栈S已经存在 操作结果:若栈S为空栈,则返回TURE:否则 返回 FALSE。 StackLength(S 初始条件:栈S已经存在。 操作结果:返回栈S中的数据元素个数。 GetTop(s, &e) 初始条件:栈S已经存在且非空。 操作结果:用e返回栈S中栈顶元素的值
栈的基本操作(之二) StackEmpty(S) • 初始条件: 栈S已经存在。 • 操作结果: 若栈S为空栈，则返回TURE;否则 返回FALSE。 StackLength(S) • 初始条件: 栈S已经存在。 • 操作结果: 返回栈S中的数据元素个数。 GetTop(S,&e) • 初始条件: 栈S已经存在且非空。 • 操作结果: 用e返回栈S中栈顶元素的值