第三章栈和队列 找 2找的应用举例 找乌递相的实现 3队列 高散事件模拟
1 栈 2 栈的应用举例 3 队列 第三章 栈和队列 栈与递归的实现 离散事件模拟
3.1栈 3.1.1抽象数据类型栈的定义 一、基本概念： 1、栈(stack)：是只允许在表尾端进行插入和删除的线性表。 (a1,a2,an) 表头 表尾 插入数据元素时，新插入的数据元 (aa2,an,e 素e只能处于线性表的表尾。 (a,a2,.an) 删除数据元素时，只能删除线性表的 表尾元素
3.1栈 3.1.1 抽象数据类型栈的定义 一 、基本概念： 1、栈（stack）：是只允许在表尾端进行插入和删除的线性表。 (a ,a ,.,a ) 1 2 n 表头 表尾 插入数据元素时，新插入的数据元 素e只能处于线性表的表尾。 删除数据元素时，只能删除线性表的 表尾元素
2、栈顶和栈底：表尾端为栈顶(top),表头端为栈底 (bottom)。 3、进栈和出栈：栈的插入操作称为入栈或进栈(push), 而栈的删除操作则称为出栈或退栈(pop)。 4、LFO:最后入栈的数据元素最先出栈；最先入栈的数 据元素最后出栈。因此，栈也被称为“后进先出” (LIFO,last in first out)的线性表。 入栈 出栈 an是最后入栈的数据元素，an最先 栈顶top 出栈。a1是最先入栈的数据元素，a1 an 表尾 最先出栈。 a2 栈底 a1 表头 bottom 栈的示意图
2、栈顶和栈底：表尾端为栈顶（top），表头端为栈底 (bottom)。 3、进栈和出栈：栈的插入操作称为入栈或进栈(push)， 而栈的删除操作则称为出栈或退栈(pop)。 4、LIFO：最后入栈的数据元素最先出栈；最先入栈的数 据 元素 最后出 栈。 因此， 栈也 被称为 “后 进先出 ” （LIFO，last in first out ）的线性表。 栈的示意图 栈底 bottom 入栈 a2 a1 an 出栈 栈顶 top ． ． ． 表尾 表头 an 是最后入栈的数据元素，an最先 出栈。a1是最先入栈的数据元素，a1 最先出栈
·在实际生活中有许多类似于栈的例子。比 如，刷洗盘子，把洗净的盘子一个接一个 地往上放（相当于把元素入栈)；取用盘 子的时候，则从最上面一个接一个地往下 拿（相当于把元素出栈）
◼ 在实际生活中有许多类似于栈的例子。比 如，刷洗盘子，把洗净的盘子一个接一个 地往上放（相当于把元素入栈）；取用盘 子的时候，则从最上面一个接一个地往下 拿（相当于把元素出栈）
二·栈的抽象数据类型定义 ADT STACK! n个数据元素的集合。数据元素可以 是整型、字符型、结构类型。 数据对象 D={a|a∈ElemSet,i=1,2,.,n,n≥0} 数据关系： R={<ai-1,a>|a-1,a∈D,i=2,.,n} a和a之间存在一个有序关系，二者 基本操作： 不能互换。 ADT STACK
二 ． 栈 的 抽 象 数 据 类 型 定 义 ADT STACK{ 数据对象： D＝{ai | ai∈ElemSet, i=1,2,.,n, n≥0} 数据关系： R＝{ <a i-1 ,ai > | ai-1 , ai ∈D, i=2,.,n} 基本操作： } ADT STACK 栈的n个数据元素的集合。数据元素可以 是整型、字符型、结构类型。 栈a i-1和ai之间存在一个有序关系，二者 不能互换