栈的表示和操作的实现

1 栈的类型定义

栈的基本操作除了入栈和出栈外，还有栈的初始化、栈空的判定，以及取栈顶元素等。下面给出栈的抽象数据类型定义：

和线性表类似，栈也有两种存储表示方法，分别称为顺序栈和链栈。

2 顺序栈的表示和实现

顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。通常习惯的做法是：以top=0表示空栈，鉴于C语言中数组的下标约定从0开始，则当以C语言作描述语言时，如此设定会带来很大不便，因此另设指针base指示栈底元素在顺序栈中的位置。当top和base的值相等时，表示空栈。顺序栈的定义如下：

说明
（1）base为栈底指针，初始化完成后，栈底指针base始终指向栈底的位置，若base的值为NULL，则表明栈结构不存在。top为栈顶指针，其初值指向栈底。每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1。因此，栈空时，top和base的值相等，都指向栈底；栈非空时，top始终指向栈顶元素的上一个位置。
（2）stacksize指示栈可使用的最大容量，后面算法1的初始化操作为顺序栈动态分配MAXSIZE大小的数组空间，将stacksize置为MAXSIZE。
图1所示为顺序栈中数据元素和栈指针之间的对应关系。