第三章 栈和队列

一、栈的基本概念

1、栈的定义：

栈：只允许在一段进行插入和删除的限定性线性表。

栈顶：线性表允许进行插入和删除的那一端。

栈低：不允许插入和删除的那一端。

空栈：不含任何元素的空表。

根据上述定义，每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素。在下图所示的栈中，元素是以a1，a2，a3，…，an的顺序进栈的，而退栈的次序却是an，…，a3，a2，a1。栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出的线性表，简称为LIFO表。

2、栈的抽象数据类型

栈的抽象数据类型定义

ADT Stack

数据元素：可以是任意类型的数据，但必须属于同一个数据对象。

结构关系：栈中数据元素之间是线性关系。

基本操作：

（1）InitStack(S)

操作前提：S为未初始化的栈。

操作结果：将S初始化为空栈。

（2）ClearStack(S)

操作前提：栈S已经存在。

操作结果：将栈S置成空栈。

（3）IsEmpty(S)

操作前