北京邮电大学自动化学院：《数据结构》第三章 栈和队列

第三章栈和队列 31栈 32栈的应用举例 ●33队列 北京邮电大学自动化学院

北京邮电大学自动化学院 1 第三章 栈和队列 ⚫3.1 栈 ⚫3.2 栈的应用举例 ⚫3.3 队列

31.1抽象数据类型栈的定义 ●1栈的定义 出栈 进栈 栈( Stack是限制在表的 端进行插入和删除运top 算的线性表。 a ●通常称插入、删除的这 端为栈顶(Top),另 端为栈底(Base) base 2 ●当表中没有元素时称为 a 空栈。 北京邮电大学自动化学院

北京邮电大学自动化学院 2 ⚫ 1 栈的定义 ⚫栈(Stack)是限制在表的 一端进行插入和删除运 算的线性表。 a1 a2 a n-1 a n …… top base 出栈 进栈 ⚫通常称插入、删除的这 一端为栈顶(Top)，另一 端为栈底(Base)。 ⚫当表中没有元素时称为 空栈。 3.1.1抽象数据类型栈的定义

1、栈的定义 假设栈S=(a1,a2 出栈 进栈 a3,∴an),则a1称为栈底 元素,an为栈顶元素。栈中 元素按a1a2a3,…a,的top a 次序进栈,退栈的第一个元 素应为栈顶元素。 ●栈的特点:栈的修改是按 后进先出的原则进行的。base 2 因此,栈称为后进先出表 a (LIFO)。 图3.1栈的示意图 北京邮电大学自动化学院

北京邮电大学自动化学院 3 图3.1栈的示意图 1、 栈的定义 a1 a2 a n-1 a n …… top base ⚫假设栈S=(a1，a2， 出栈 进栈 a3，…an )，则a1称为栈底 元素，an为栈顶元素。栈中 元素按a1，a2，a3，…an的 次序进栈，退栈的第一个元 素应为栈顶元素。 ⚫栈的特点：栈的修改是按 后进先出的原则进行的。 因此，栈称为后进先出表 （LIFO）

2、栈的基本操作 (1)初始化 (2)进栈 (3)退栈 (4)取栈顶元素 (5)判栈是否非空 (6)置栈空 北京邮电大学自动化学院 4

北京邮电大学自动化学院 4 ⚫ （1）初始化 2、栈的基本操作 ⚫ （2）进栈 ⚫ （3）退栈 ⚫ （4）取栈顶元素 ⚫ （5）判栈是否非空 ⚫ （6）置栈空

3、栈的抽象数据类型的定义 o ADT stacki 数据对象:D={aa∈ Elem Set. i=1,2,…,n,n>=0)} 数据关系:R1={a11aP|a1a∈D}约定an为栈顶,a1端为栈 底 ● Destroystack(&s) ●基本操作: ●初始条件:栈已经存在 操作结果:栈s被销毁 Initstack(&s) Clearstack &s) ●操作结果:构造一个 空栈s ●初始条件:栈已经存在 操作结果:将s清空为零 北京邮电大学自动化学院

北京邮电大学自动化学院 5 ⚫ ADT stack{ ⚫ 数据对象：D={ai |aiElemSet,i=1,2,…,n,n>=0)} ⚫ 数据关系：R1={|ai-1 ,aiD} 约定an为栈顶，a1端为栈 底 3、栈的抽象数据类型的定义 ⚫ 基本操作： ⚫ Initstack(&s) ⚫ 操作结果：构造一个 空栈s ⚫ Destroystack(&s) ⚫ 初始条件：栈已经存在 ⚫ 操作结果：栈s被销毁 ⚫ Clearstack(&S) ⚫ 初始条件：栈已经存在 ⚫ 操作结果：将s清空为零

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, ⚫ 因此，非空栈中的栈顶指针始 终在栈顶元素的下一位置上。 左图展示了顺序栈中数据元素 和栈顶指针之间的对应关系