栈的抽象数据类型定义 ADT Stack 数据对象：D={ala:∈ElemSet,.=1,2,,n,n≥0} 数据关系：R={<a-1,a>a1,a:∈D,=2,3,…,n} 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈S已存在。 操作结果：栈S被销毁
ADT Stack{ 数据对象：D ={ ai |ai∈ElemSet, i=1,2,…,n，n≥0 } 数据关系：R ={<ai-1 , ai>|ai-1，ai∈D, i=2,3,…,n } 基本操作： InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。 2 栈的抽象数据类型定义
ClearStack(&S) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackEmpty(S) 初始条件：栈S已存在。 操作结果：若栈S为空栈，则返回TRUE,否则返回 FALSE。 StackLength(S) 初始条件：栈S已存在。 操作结果：返回栈S中元素个数，即栈的长度。 GetTop(S,&e) 初始条件：栈S已存在且非空。 操作结果：用e返回$的栈顶元素
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已存在且非空，visit()为元素的 访问函数。 操作结果：从栈底到栈顶依次对S的每个元素调用函 数visit(),一旦visit()失败，则操作失败。 ADT Stack
Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。 Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。 StackTraverse(S, visit( )) 初始条件：栈 S 已存在且非空，visit( )为元素的 访问函数。 操作结果：从栈底到栈顶依次对S的每个元素调用函 数visit( )，一旦visit( )失败，则操作失败。 } ADT Stack
3.1.2 栈的表示和实现 和线性表类似，栈也有两种存储方法： >栈的顺序存储结构一一顺序栈； >栈的链式存储结构一一链栈
和线性表类似，栈也有两种存储方法： ➢栈的顺序存储结构——顺序栈； ➢栈的链式存储结构——链栈。 3.1.2 栈的表示和实现
3.1.2.1 栈的顺序存储表示 ◆顺序栈，即栈的顺序存储结构，是利用一组地址 连续的存储单元依次存放自栈底到栈顶的数据元素。 ◆设置指针top指向栈顶元素在顺序栈中的位置，通 常习惯做法是以top=O表示空栈。 ◆栈在使用的过程中所需最大空间的大小很难估计， 一般初始化设空栈时不限定栈的最大容量。 ◆一般先分配一个基本容量，然后应用过程中，栈 的空间不够使用时再逐段扩大
◆顺序栈，即栈的顺序存储结构，是利用一组地址 连续的存储单元依次存放自栈底到栈顶的数据元素。 ◆设置指针top指向栈顶元素在顺序栈中的位置，通 常习惯做法是以top=0表示空栈。 ◆栈在使用的过程中所需最大空间的大小很难估计， 一般初始化设空栈时不限定栈的最大容量。 ◆一般先分配一个基本容量，然后应用过程中，栈 的空间不够使用时再逐段扩大。 3.1.2.1 栈的顺序存储表示