第三章栈和队列 《数据结构》 第三章栈和队列 第1页
第三章 栈和队列 第1页 《数据结构》 第三章 栈和队列
第三章栈和队列 第三章栈和队列 要求: 对栈和队列的存储方式及基本操作 一有较深刻的理解。理解栈和队列的概念 存储表示,进栈、退栈和进队、出队 操作的算法,初步了解栈的基本应用如 表达式的求值、递归的设计实现等 重点: 栈和队列的基本操作,栈在实现递 归中的应用。 第2页
第三章 栈和队列 第2页 要求： 对栈和队列的存储方式及基本操作 有较深刻的理解。理解栈和队列的概念 ，存储表示，进栈、退栈和进队、出队 操作的算法，初步了解栈的基本应用如 表达式的求值、递归的设计实现等。 重点： 栈和队列的基本操作，栈在实现递 归中的应用。 第三章 栈和队列
第三章栈和队列 主要内容 1、栈 ●抽象数据类型栈的定义 栈的表示与实现 2、栈的典型应用一一表达式求值 ●表达式的传统标记法—中缀标记法 ●简单算术表达式求值算法—一算符优先算法 3、栈与递归过程 递归求解问题 递归过程的实现 ●递归过程转换成非递归过程 第3页
第三章 栈和队列 第3页 主要内容 1、栈 ⚫ 抽象数据类型栈的定义 ⚫ 栈的表示与实现 2、栈的典型应用——表达式求值 ⚫ 表达式的传统标记法——中缀标记法 ⚫ 简单算术表达式求值算法——算符优先算法 3、栈与递归过程 ⚫ 递归求解问题 ⚫ 递归过程的实现 ⚫ 递归过程转换成非递归过程
第三章栈和队列 主要内容 4、队列 ●队列的逻辑结构 队列的抽象数据类型 ●链队列——队列的链式存储结构 ●循环队列——队列的顺序存储结构 ●双端队列 ●队列的应用举例 ●离散事件模拟 第4页
第三章 栈和队列 第4页 4、队列 ⚫ 队列的逻辑结构 ⚫ 队列的抽象数据类型 ⚫ 链队列——队列的链式存储结构 ⚫ 循环队列——队列的顺序存储结构 ⚫ 双端队列 ⚫ 队列的应用举例 ⚫ 离散事件模拟 主要内容
第三章栈和队列 第三章栈和队列 两种重要的受限线性结构:线(Smck)和列ueue) 从数据结构角度看,栈和队列也是线性表,其特殊 性在于栈和队列的基本操作是线件表操作的子集。它们 是燥作受限的线性表,即可称为限定性的数据结构。但 从数据类型角度看,它们又是和线性表大不相同的两类 重要的抽象数据类型。 第5页
第三章 栈和队列 第5页 第三章 栈和队列 两种重要的受限线性结构：栈(Stack)和队列(Queue)。 从数据结构角度看，栈和队列也是线性表，其特殊 性在于栈和队列的基本操作是线性表操作的子集。它们 是操作受限的线性表，即可称为限定性的数据结构。但 从数据类型角度看，它们又是和线性表大不相同的两类 重要的抽象数据类型
第三章栈和队列 第三章栈和队列 三者的操作规则比较: 线性表:可以在表的任何位置上插入、删除元素 一栈:对栈仅限定在表的一端(表尾)进行插入 或删除操作。 队列:限定在表的一端进行插入,而在另一端删 除元素。 因此,从ADT的角度看,栈、队列和线 性表是不相同的。 第6页
第三章 栈和队列 第6页 第三章 栈和队列 三者的操作规则比较： 线性表：可以在表的任何位置上插入、删除元素。 栈：对栈仅限定在表的一端（表尾）进行插入 或删除操作。 队列：限定在表的一端进行插入，而在另一端删 除元素。 因此，从ADT的角度看，栈、队列和线 性表是不相同的
第三章栈和队列 1、栈三 栈的定义 定义:栈( Stack)是限定伩在表的一端进行插入或删除操作 的线性表 在栈中能进行插入和删除的一端称为栈顶(top),相应地另 固定端称为栈底( bottom)。将一个元素放入栈中的操作叫做进栈 或压,从栈顶取出一个元素的操作叫做機或殚。不含元素的 空表称为空栈 栈的存取操作符合进先班( Last in first out,LIFO)或先进后 出( First In last out,FIO)故栈又称为后进先出线性表,简称 JFQ结构 出栈 进栈 栈顶 栈底 第7页
第三章 栈和队列 第7页 ⚫ 栈的定义 定义 ： 栈（Stack）是限定仅在表的一端进行插入或删除操作 的线性表。 在栈中能进行插入和删除的一端称为栈顶（top），相应地另一 固定端称为栈底（bottom）。将一个元素放入栈中的操作叫做进栈 或压栈，从栈顶取出一个元素的操作叫做出栈或弹出。不含元素的 空表称为空栈。 栈的存取操作符合后进先出（Last In First Out, LIFO）或先进后 出（First In Last Out, FILO）故栈又称为后进先出线性表，简称 LIFO结构。 1、栈 an . . . a2 a1 栈底 栈顶 出栈 进栈
第三章栈和队列 1、栈三 栈的基本性质 1)集合性:该结构由若干个有限的同类型元素集合而成 2)线性性:除线底外,栈中任一元素均有唯一的前驱,除线顶外, 栈中任一元素均有唯一的后继; 3受限制的运算:仅允许在栈顶压入、弹出 4)数学性质:当n个编号元素依某种顺序压入,且可任意弹出时, 所能获得的编号元素排列的数目为 n+ (2H)! n+1r!! 其中n为输入序列长度即编号元素个数,c为可能的排列数目。 由公式(*)产生的数列称为卡塔南数列。 第8页
第三章 栈和队列 第8页 栈的基本性质 1) 集合性：该结构由若干个有限的同类型元素集合而成； 2) 线性性：除线底外，栈中任一元素均有唯一的前驱，除线顶外， 栈中任一元素均有唯一的后继； 3) 受限制的运算：仅允许在栈顶压入、弹出； 4) 数学性质：当n个编号元素依某种顺序压入，且可任意弹出时， 所能获得的编号元素排列的数目为。 ( ) ! ! (2 )! 1 1 1 1 2 • + = + = n n n n C n C n n n 其中n为输入序列长度即编号元素个数，cn为可能的排列数目。 由公式（*）产生的数列称为卡塔南数列。 1、栈
第三章栈和队列 示例用铁路调度站表示栈ˉ 出栈 进栈 一设有A,B,C三列车厢,则出栈时可能的编号元素排列为ABC 一ACB,BAC,BCA,CBA共五种。(无CAB) 2×3 6·5·4 3+133!43 若A,B,C,D四列车厢,则应有14种排列: 2×4)!_18·7·6·5 14 4+1445 4! 第9页
第三章 栈和队列 第9页 示例 用铁路调度站表示栈 出栈 进栈 设有A，B，C三列车厢，则出栈时可能的编号元素排列为ABC ，ACB，BAC，BCA，CBA共五种。(无CAB) 5. 3! 6 5 4 4 1 3!3! (2 3)! 3 1 1 3 = • • = • • + C = 14. 4! 8 7 6 5 5 1 4!4! (2 4)! 4 1 1 4 = • • • = • • + C = 若A，B，C，D四列车厢，则应有14种排列：
第三章栈和队列 1、栈三 栈的抽象数据类型定义 栈是一种强限制的数据类型。在栈上仅能在特定的一个位置上 定义有限几种操作 Specification ADT Stack Elements:所涉及对象的数据类型明显地取决于应用,故数据元素 可以是各种类型的,只要同属一个数据对象即可 Structure:数据元素之间呈线性关系。假设栈中有n个数据元素 (a1,a2…an),则对每一个元素a(i=1,2,…n-1),都存在关 系 ,并且a1无前驱,an无后继。但是,栈是一种受 限的线性结构,该结构使后进栈的元素先出栈 Operation:栈通常包含下面的基本操作,这些操作中除 了 Initstack之外,都要求栈S已存在。 第10页
第三章 栈和队列 第10页 ⚫ 栈的抽象数据类型定义 栈是一种强限制的数据类型。在栈上仅能在特定的一个位置上 定义有限几种操作。 Specification ADT Stack Elements：所涉及对象的数据类型明显地取决于应用，故数据元素 可以是各种类型的，只要同属一个数据对象即可。 Structure：数据元素之间呈线性关系。假设栈中有n个数据元素 (a1 ,a2 ,···,an )，则对每一个元素ai (i=1,2,···,n-1)，都存在关 系 ，并且a1无前驱，an无后继。但是，栈是一种受 限的线性结构，该结构使后进栈的元素先出栈。 Operation：栈通常包含下面的基本操作，这些操作中除 了InitStack之外，都要求栈S已存在。 1、栈