第三章栈和队列 《数据结构》 第三章栈和队列 第1页
第三章 栈和队列 第1页 《数据结构》 第三章 栈和队列
第三章栈和队列 第三章栈和队列 要求: 对栈和队列的存储方式及基本操作 一有较深刻的理解。理解栈和队列的概念 存储表示,进栈、退栈和进队、出队 操作的算法,初步了解栈的基本应用如 表达式的求值、递归的设计实现等 重点: 栈和队列的基本操作,栈在实现递 归中的应用。 第2页
第三章 栈和队列 第2页 要求： 对栈和队列的存储方式及基本操作 有较深刻的理解。理解栈和队列的概念 ，存储表示，进栈、退栈和进队、出队 操作的算法，初步了解栈的基本应用如 表达式的求值、递归的设计实现等。 重点： 栈和队列的基本操作，栈在实现递 归中的应用。 第三章 栈和队列
第三章栈和队列 主要内容 1、栈 ●抽象数据类型栈的定义 栈的表示与实现 2、栈的典型应用一一表达式求值 ●表达式的传统标记法—中缀标记法 ●简单算术表达式求值算法—一算符优先算法 3、栈与递归过程 递归求解问题 递归过程的实现 ●递归过程转换成非递归过程 第3页
第三章 栈和队列 第3页 主要内容 1、栈 ⚫ 抽象数据类型栈的定义 ⚫ 栈的表示与实现 2、栈的典型应用——表达式求值 ⚫ 表达式的传统标记法——中缀标记法 ⚫ 简单算术表达式求值算法——算符优先算法 3、栈与递归过程 ⚫ 递归求解问题 ⚫ 递归过程的实现 ⚫ 递归过程转换成非递归过程
第三章栈和队列 主要内容 4、队列 ●队列的逻辑结构 队列的抽象数据类型 ●链队列——队列的链式存储结构 ●循环队列——队列的顺序存储结构 ●双端队列 ●队列的应用举例 ●离散事件模拟 第4页
第三章 栈和队列 第4页 4、队列 ⚫ 队列的逻辑结构 ⚫ 队列的抽象数据类型 ⚫ 链队列——队列的链式存储结构 ⚫ 循环队列——队列的顺序存储结构 ⚫ 双端队列 ⚫ 队列的应用举例 ⚫ 离散事件模拟 主要内容
第三章栈和队列 第三章栈和队列 两种重要的受限线性结构:线(Smck)和列ueue) 从数据结构角度看,栈和队列也是线性表,其特殊 性在于栈和队列的基本操作是线件表操作的子集。它们 是燥作受限的线性表,即可称为限定性的数据结构。但 从数据类型角度看,它们又是和线性表大不相同的两类 重要的抽象数据类型。 第5页
第三章 栈和队列 第5页 第三章 栈和队列 两种重要的受限线性结构：栈(Stack)和队列(Queue)。 从数据结构角度看，栈和队列也是线性表，其特殊 性在于栈和队列的基本操作是线性表操作的子集。它们 是操作受限的线性表，即可称为限定性的数据结构。但 从数据类型角度看，它们又是和线性表大不相同的两类 重要的抽象数据类型