第3章 CHAPTER 3
栈 和 队 列
主要知识点 栈和队列的类型定义。 栈的存储表示及基于存储结构的基本操作实现。 队列的存储表示及基于存储结构的基本操作实现。 栈和队列是两种重要的线性结构,从数据结构的角度看,栈和队列也是线性表,其特殊性在于栈和队列的基本操作是线性表操作的子集,它们是操作受限制的线性表,因此可以称为限定性的数据结构。但从数据类型的角度看,它们是和线性表大不相同的两类抽象数据类型。栈和队列在操作系统、编译原理及大型应用软件系统中得到了广泛的应用。 3.1栈 栈的特点在于其基本操作的特殊性,即它必须按照“后进先出”的规则进行操作。与线性表相比,其插入和删除操作受到更多的约束和限定。 3.1.1栈的类型定义 在日常生活中,有很多“后进先出”的例子。例如,把餐厅里洗净的一摞碗看作一个栈。通常,后洗净的碗总是摞在先洗净的碗上面,*后洗净的碗摞在*上面; 而使用时却是从这摞碗顶端拿取,即后洗净的先取用。栈的操作特点正是上述实际的抽象。 1. 栈的定义 栈(Stack)是限定仅可以在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶(Top),栈顶将随着栈中数据元素的增减而浮动,且通过栈顶指针指明当前数据元素位置; 不允许插入和删除的一端称为栈底(Bottom),栈底指针并不随着栈中数据元素的增减而移动,它是固定的。不含任何数据元素的栈称为空栈(Empty Stack)。
图31栈的示意图
如图31所示,栈中有3个数据元素,插入元素(也称入栈)顺序是a1、a2、a3,当需要删除元素(也称出栈)时,其顺序只能为a3、a2、a1。换言之,在任何时候出栈的数据元素都只能是栈顶元素,即*后入栈者*先出栈,所以栈中元素除了具有线性关系外,还具有后进先出(Last In First Out,LIFO)的特性。栈也可以简称为LIFO表。
图32所示的铁路调度站A是一个栈。车辆由轨道B进入调度站A,调度站A中的车辆从轨道C离去; 后进入调度站A的车辆将先调出。
图32铁路调度示意图
在程序设计语言中,也有很多栈的应用例子。例如,在对程序设计语言编写的源程序进行编译时,类似于表达式括号匹配问题就是用栈来解决的。又如,计算机系统在处理子程序之间的调用关系时,用栈来保存处理执行过程中的调用层次,等等。