3.1 栈
3.1.1 栈的基本概念
栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为
后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性
表。 栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指
针(top)来指示栈顶元素。 栈底(Bottom)：是固定端，又称为表头。 空
栈：当表中没有元素时称为空栈。
设栈S=(a1，a2，…an)，则a1称为栈底元素，an为栈顶元素，如图所
示。
typedef struct Dulnode
{ ElemType data ;
struct Dulnode *prior , *next ;
}DulNode ;栈中元素按a1，a2，…an的次序进栈，退栈的第一个元素应为栈顶元
素。即栈的修改是按后进先出的原则进行的。
3.1.2 栈的抽象数据类型定义
ADT Stack{ 数据对象：D ={ ai|ai∈ElemSet, i=1,2,…,n，n≥0 } 数据关
系：R ={<ai-1, ai>|ai-1，ai∈D, i=2,3,…,n } 基本操作：初始化、进栈、出
栈、取栈顶元素等 } ADT Stack
栈的基本运算包括： （1）置空栈SETNULL（S） （2）判栈空
EMPTY（S）:布尔函数 （3）入栈PUSH(S，x)
（4）出栈POP（S） （5）取栈顶TOP（S）