一、栈的基本概念
栈是限制在表的一端进行插入和删除的线性表。
表中允许插入和删除的一端,我们称之为栈顶;不允许插入和删除的一端,我们称之为栈底。
我们把插入运算成为进栈、压栈或者入栈,而把删除运算称之为退栈或出栈。
很显然,栈顶是动态变化的,栈底是固定不变的。当表中没有元素时,我们称之为空栈。
下图为栈的进栈和出栈过程示意图,进栈的顺序是 e1、e2、e3,出栈的顺序为 e3、e2、e1,所以栈又称为后进先出线性表(Last In First Out),简称 LIFO 表,或称先进后出线性表。其特点是先进后出或者后进先出。
栈的进栈和出栈过程示意图:
二、栈的抽象数据类型
对于栈,常用的基本运算有入栈、出栈、取栈顶元素等操作。其抽象数据类型定义如下:
ADT Stack {
Data: 存储栈的元素的数据结构 // 可以用顺序表或者单链表存储
栈顶位置
栈的空间大小
Operation:
Stack() // 构造一个空栈
~Stack() // 销毁一个空栈
Empty_Stack() // 判断栈是否为空
Push_Stack(e) // 将元素e插入栈顶
Pop_Stack(&e) // 从栈顶删除一个元素到e中返回
GetTop_Stack(&e) // 从栈顶取出一个元素到e中返回
}