3、栈的抽象数据类型的定义 ● StackEmpty(&s) GetTop(s,&e) ●初始条件:栈已经存在 初始条件:栈已经存在 ●操作结果:若栈S为空,则返回·操作结果:用e返回S的栈 TRUE,否则 FALSE 顶元素 ● StackLength(&s) Push(&s, e) ●初始条件:栈S已经存在°初始条件:栈S已经存在 操作结果:返回栈S的元素个●操作结果:插入元素e为新 数,即栈的长度 的栈顶元素 北京邮电大学自动化学院
北京邮电大学自动化学院 6 ⚫ StackEmpty(&s) ⚫ 初始条件：栈已经存在 ⚫ 操作结果：若栈S为空,则返回 TRUE,否则FALSE. 3、栈的抽象数据类型的定义 ⚫ Push (&s,e) ⚫ 初始条件: 栈S已经存在 ⚫ 操作结果：插入元素e为新 的栈顶元素. ⚫ StackLength(&s) ⚫ 初始条件：栈S已经存在 ⚫ 操作结果：返回栈S的元素个 数,即栈的长度. ⚫ GetTop(S,&e) ⚫ 初始条件：栈已经存在 ⚫ 操作结果：用e返回S的栈 顶元素
3、栈的抽象数据类型的定义 ●Pop(&s&e) 初始条件:栈已经存在且非空 操作结果:删除S的栈顶元素,并用e返回其值 ●} ADT Stack 北京邮电大学自动化学院
北京邮电大学自动化学院 7 3、栈的抽象数据类型的定义 ⚫ Pop(&s,&e) ⚫ 初始条件：栈已经存在且非空 ⚫ 操作结果：删除S的栈顶元素,并用e返回其值. ⚫ }ADT Stack
31.2栈的表示和实现 ●和线性表类似,栈也有两种存储表示方法。顺序栈、链栈。 ●顺序栈,即栈的顺序存储结构是利用一组地址连续的存储单 元依次存放自栈底到栈顶的数据元素。同时附设指针top指 示栈顶元素在顺序表中的位置。 ●通常的习惯做法是以top=0表示空栈,鉴于c语言中数组的下 标约定从0开始,则当以C语言作描述语言时,如此设定会 带来很大不方便; ●另一方面,由于栈在使用过程中所需要最大空间的大小很难估 计,因此,般来说在初始化设计空栈时不应限定栈的最大容量. 个合理的做法是:先为栈分配一个基本容量,然后在应用 过程中,当栈的空间不够使用时再逐段扩大 北京邮电大学自动化学院
北京邮电大学自动化学院 8 和线性表类似，栈也有两种存储表示方法。顺序栈、链栈。 3.1.2 栈的表示和实现 顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单 元依次存放自栈底到栈顶的数据元素。同时附设指针top指 示栈顶元素在顺序表中的位置。 通常的习惯做法是以top=0表示空栈,鉴于C语言中数组的下 标约定从0开始，则当以C语言作描述语言时，如此设定会 带来很大不方便; 一个合理的做法是：先为栈分配一个基本容量，然后在应用 过程中，当栈的空间不够使用时再逐段扩大。 另一方面,由于栈在使用过程中所需要最大空间的大小很难估 计,因此,一般来说,在初始化设计空栈时不应限定栈的最大容量
1、顺序栈 ●为此设定两个常量: STACK_INT_SzE(存储空间初始分配量) 和 STACKINCREMENT(存储空间分配增量),并以下述类型说明 作为顺序栈的定义 ● typedef Struct 0 SElemType“base; ●sE| emType top; o int stacksize; SqStack; ●其中, stacksize指示栈的当前可使用的最大容量 ●栈的初始化操作为:按设定的初始分配量进行第一次存储分配 base称为栈底指针在顺序标中,它始终指向栈底的位置,若base 的值为NULL,则表明栈结构不存在 北京邮电大学自动化学院
北京邮电大学自动化学院 9 为此设定两个常量:STACK_INIT_SIZE(存储空间初始分配量) 和STACKINCREMENT(存储空间分配增量),并以下述类型说明 作为顺序栈的定义. 其中，stacksize指示栈的当前可使用的最大容量。 typedef Struct{ SElemType *base; SElemType *top; int stacksize; }SqStack; 1、 顺序栈 栈的初始化操作为: 按设定的初始分配量进行第一次存储分配， base称为栈底指针,在顺序标中,它始终指向栈底的位置,若 base 的值为NULL,则表明栈结构不存在
1、顺序栈 例、一叠书或一叠盘子。。称top为栈顶指针,其初始值指 向栈底即top=base可作为栈 空的标记, top ●每当插入新的栈顶元素时, a n 指针top增1; ●删除栈顶元素时指针top减1, ●因此,非空栈中的栈顶指针始 终在栈顶元素的下一位置上。 a 左图展示了顺序栈中数据元素 和栈顶指针之间的对应关系。 base a 北京邮电大学自动化学院 10
北京邮电大学自动化学院 10 例、一叠书或一叠盘子。 a n a n-1 a2 a1 …… top base 1、 顺序栈 ⚫ 称top为栈顶指针,其初始值指 向栈底,即top=base可作为栈 空的标记, ⚫ 每当插入新的栈顶元素时, 指针top增1; ⚫ 删除栈顶元素时,指针top减1, ⚫ 因此，非空栈中的栈顶指针始 终在栈顶元素的下一位置上。 左图展示了顺序栈中数据元素 和栈顶指针之间的对应关系