文档介绍：Page 1 Data Structure 2016-12-24 第三章第三章栈和队列栈和队列 100 865 10 Page 2 Data Structure 2016-12-24 ?学习目标?掌握栈和队列这两种抽象数据类型的特点,并能在相应的应用问题中正确选用它们。?熟练掌握栈类型的两种实现方法。?熟练掌握循环队列和链队列的基本操作实现算法。?理解递归算法执行过程中栈的状态变化过程。?重点和难点?栈和队列是在程序设计中被广泛使用的两种线性数据结构,本章的学习重点是掌握这两种结构的特点,以便能在应用问题中正确使用。?知识点?顺序栈、链栈、循环队列、链队列 Page 3 Data Structure 2016-12-24 ?栈和队列是在程序设计中被广泛使用的两种线性数据结构。?与线性表相比,它们的插入和删除操作受更多的约束和限定,故又称为限定性的线性表结构。?线性表允许在表内任一位置进行插入和删除; ?栈只允许在表尾一端进行插入和删除; ?队列只允许在表尾一端进行插入,在表头一端进行删除。 Page 4 Data Structure 2016-12-24 栈?栈?限定只能在表的一端进行插入和删除操作的线性表。?栈顶(top) :允许插入和删除的一端。?栈底(bottom) :不允许插入和删除的另一端。?空栈:不含元素的空表。(a 1, a 2, ……, a n) 栈顶栈底 Page 5 Data Structure 2016-12-24 a 1a 2a 3 入栈出栈栈底栈顶插入:入栈、进栈、压栈删除:出栈、弹栈栈顶栈顶栈的示意图?特点?先进后出( FILO ) ?后进先出( LIFO ) Page 6 Data Structure 2016-12-24 例:有三个元素按 a、b、c的次序依次进栈,且每个元素只允许进一次栈,则可能的出栈序列有多少种? 栈的逻辑结构栈的逻辑结构栈底栈顶 a b 栈顶 c 栈顶?情况 1: Page 7 Data Structure 2016-12-24 栈底栈顶 a b 栈顶 c 栈顶出栈序列: c出栈序列: c、b出栈序列: c、b、a 例:有三个元素按 a、b、c的次序依次进栈,且每个元素只允许进一次栈,则可能的出栈序列有多少种? ?情况 1: 栈的逻辑结构栈的逻辑结构 Page 8 Data Structure 2016-12-24 栈底栈顶 a b 栈顶出栈序列: b ?情况 2: 例:有三个元素按 a、b、c的次序依次进栈,且每个元素只允许进一次栈,则可能的出栈序列有多少种? 栈的逻辑结构栈的逻辑结构 Page 9 Data Structure 2016-12-24 栈底 a 出栈序列: b出栈序列: b、c出栈序列: b、c、ac 栈顶栈顶注意: 栈只是对表插入和删除操作的位置进行了限制,并没有限定插入和删除操作进行的时间。例:有三个元素按 a、b、c的次序依次进栈,且每个元素只允许进一次栈,则可能的出栈序列有多少种? ?情况 2: 栈的逻辑结构栈的逻辑结构还有其他情况吗? Page 10 Data Structure 2016-12-24 栈的抽象数据类型定义栈的抽象数据类型定义 ADT Stack { 数据对象:D={a i | a i∈ ElemSet , i=1,2,...,n, n ≥ 0 } 数据关系: R1 = { <a i-1 ,a i >| a i-1 ,a i∈ D, i=2,...,n } 基本操作: InitStack(&S )操作结果:构造一个空栈 S。 DestroyStack(&S )初始条件:栈 S 已存在。操作结果:栈 S 被销毁。