Tim的资源站

一、栈的基本概念

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

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

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

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

下图为栈的进栈和出栈过程示意图，进栈的顺序是 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中返回
}