10
65
865
A
B
C
D
E
F
G
第 3 章 栈和队列
学习提要
1.掌握栈和队列这两种抽象数据类型的特点，
并能在相应的应用问题中正确选用它们。
2. 熟练掌握栈类型的两种实现方法，即两种
存储结构表示时的基本操作实现算法，特别应
注意栈满和栈空的条件以及它们的描述方法。
3. 熟练掌握循环队列和链队列的基本操作实现
算法，特别注意队满和队空的描述方法。
第 3 章 栈和队列
栈和队列是两种特殊的线性表，它们是运算时要
受到某些限制的线性表，故也称为限定性的数据
结构。
3.1 栈
3.1.1 栈的定义
栈：限定只能在表的一端进行插入和删除的特殊的线性表
设栈 s= （ a
1
， a
2
， . . . ,a
i
， . . . ， a
n
），
其中 a
1
是栈底元素， a
n
是栈顶元素。
a
1
a
2
….
a
n
进栈 出栈
栈顶
栈底
3.1 栈
3.1.1 栈的定义
栈：限定只能在表的一端进行插入和删除的特殊的线性表
设栈 s= （ a
1
， a
2
， . . . ,a
i
， . . . ， a
n
），
其中 a
1
是栈底元素， a
n
是栈顶元素。
栈顶（ top) ：允许插入和删除的一端；
约定 top 始终指向新数据元素将存放的位置。
栈底（ bottom): 不允许插入和删除的一端。
a
1
a
2
….
a
n
进栈 出栈
栈顶
栈底
