《数据结构与算法分析》课程教学课件（PPT讲稿）第三章 栈和队列

第三章栈和队列 找 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={|a-1,a∈D,i=2,.,n} a和a之间存在一个有序关系，二者 基本操作： 不能互换。 ADT STACK

二 ． 栈 的 抽 象 数 据 类 型 定 义 ADT STACK{ 数据对象： D＝{ai | ai∈ElemSet, i=1,2,.,n, n≥0} 数据关系： R＝{ | ai-1 , ai ∈D, i=2,.,n} 基本操作： } ADT STACK 栈的n个数据元素的集合。数据元素可以 是整型、字符型、结构类型。 栈a i-1和ai之间存在一个有序关系，二者 不能互换

关于基本操作的几点说明： 1、基本操作是定义于逻辑结构上的基本操作，向外界 提供一个与其通讯的接口。还没有用具体的某种程序 语言写出具体的算法，而算法的实现只有在存储结构 确立之后。对应于不同的存储结构，栈的基本操作的 实现也不相同。 2、基本操作的种类可随实际需要的不同而不同。但是， 栈是操作受限的线性表，不能任意的定义基本操作。 如在栈的第个位置插入数据元素。 3、针对不同的需要，基本操作的参数和返回值可以有 所变化

关于基本操作的几点说明： 1、基本操作是定义于逻辑结构上的基本操作，向外界 提供一个与其通讯的接口。还没有用具体的某种程序 语言写出具体的算法，而算法的实现只有在存储结构 确立之后。对应于不同的存储结构，栈的基本操作的 实现也不相同。 2、基本操作的种类可随实际需要的不同而不同。但是， 栈是操作受限的线性表，不能任意的定义基本操作。 如在栈的第i个位置插入数据元素。 3、针对不同的需要，基本操作的参数和返回值可以有 所变化

1)、求栈的长度：Count(0 初始条件：栈存在； 操作结果：返回栈中数据元素的个数。 2)、判断栈是否为空：IsEmpty0 初始条件：栈存在； 操作结果：如果栈为空返回true,否则返回 false。 3)、清空操作：Clear(0 初始条件：栈存在； 操作结果：使栈为空

1)、求栈的长度：Count () 初始条件：栈存在； 操作结果：返回栈中数据元素的个数。 2)、判断栈是否为空：IsEmpty() 初始条件：栈存在； 操作结果：如果栈为空返回true，否则返回 false。 3)、清空操作：Clear() 初始条件：栈存在； 操作结果：使栈为空

4)、入栈操作：Push(T item) 初始条件：栈存在； 操作结果：将值为item的新的数据元素添加到栈 顶，栈发生变化。 5)、出栈操作：Pop0 初始条件：栈存在且不为空； 操作结果：将栈顶元素从栈中取出，栈发生变化。 6)、取栈顶元素：GetTop() 初始条件：栈表存在且不为空； 操作结果：返回栈顶元素的值，栈不发生变化

4)、入栈操作：Push(T item) 初始条件：栈存在； 操作结果：将值为item的新的数据元素添加到栈 顶，栈发生变化。 5)、出栈操作：Pop() 初始条件：栈存在且不为空； 操作结果：将栈顶元素从栈中取出，栈发生变化。 6)、取栈顶元素：GetTop() 初始条件：栈表存在且不为空； 操作结果：返回栈顶元素的值，栈不发生变化

3.1.2栈的顺序存储 一.栈的顺序存储：利用一组地址连续的存储单元 依次存放自栈底至栈顶的元素。 假设每个元素占用个存储单元，栈中第一个元素（即栈底元素)的 存储地址是LOC(a1)=b,那麽栈中最后一个元素（即栈顶元素）的存储 地址是多少？ b+(n-1)川 an b+(n-2)川 an1 b+l a2 a1 b

3.1.2 栈的顺序存储 一．栈的顺序存储：利用一组地址连续的存储单元 依次存放自栈底至栈顶的元素。 假设每个元素占用l个存储单元，栈中第一个元素（即栈底元素）的 存储地址是LOC(a1)=b，那麽栈中最后一个元素（即栈顶元素）的存储 地址是多少？ a1 a2 a n-1 a n . b b+(n-2)l b+l b+(n-1)l

因为在c#语言的层面上讨论问题，栈的顺序存储是把栈 的数据元素自栈底至栈顶放在一维数组中。同时附设一个 top指示器指向栈顶元素。 top an an1 a2 a

因为在c#语言的层面上讨论问题，栈的顺序存储是把栈 的数据元素自栈底至栈顶放在一维数组中。同时附设一个 top指示器指向栈顶元素。 a1 a2 a n-1 a n . top