一、栈的基本概念

栈是限制在表的一端进行插入和删除的线性表。

表中允许插入和删除的一端,我们称之为栈顶;不允许插入和删除的一端,我们称之为栈底。

我们把插入运算成为进栈、压栈或者入栈,而把删除运算称之为退栈或出栈。

很显然,栈顶是动态变化的,栈底是固定不变的。当表中没有元素时,我们称之为空栈。

下图为栈的进栈和出栈过程示意图,进栈的顺序是 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中返回
}
用户头像
登录后发表评论