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