第三章栈和队列 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 |aiElemSet,i=1,2,…,n,n>=0)} ⚫ 数据关系：R1={<ai-1 ,ai>|ai-1 ,aiD} 约定an为栈顶，a1端为栈 底 3、栈的抽象数据类型的定义 ⚫ 基本操作： ⚫ Initstack(&s) ⚫ 操作结果：构造一个 空栈s ⚫ Destroystack(&s) ⚫ 初始条件：栈已经存在 ⚫ 操作结果：栈s被销毁 ⚫ Clearstack(&S) ⚫ 初始条件：栈已经存在 ⚫ 操作结果：将s清空为零