栈的表示和操作的实现

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所示为顺序栈中数据元素和栈指针之间的对应关系。

图1 栈中元素和栈指针之间的关系
由于顺序栈的插入和删除只在栈顶进行，因此顺序栈的基本操作比顺序表要简单得多，以下给出顺序栈部分操作的实现。
1．初始化
顺序栈的初始化操作就是为顺序栈动态分配一个预定义大小的数组空间。
算法3.1 顺序栈的初始化
【算法步骤】
① 为顺序栈动态分配一个最大容量为MAXSIZE的数组空间，使base指向这段空间的基地址，即栈底。
② 栈顶指针top初始为base，表示栈为空。
③ stacksize置为栈的最大容量MAXSIZE。
2．入栈入栈操作是指在栈顶插入一个新的元素。算法3.2 顺序栈的入栈【算法步骤】① 判断栈是否满，若满则返回ERROR。② 将新元素压入栈顶，栈顶指针加1。【算法描述】

2．入栈
入栈操作是指在栈顶插入一个新的元素。
算法3.2 顺序栈的入栈
【算法步骤】
① 判断栈是否满，若满则返回ERROR。
② 将新元素压入栈顶，栈顶指针加1。
【算法描述】

3．出栈
出栈操作是将栈顶元素删除。
算法3.3 顺序栈的出栈
【算法步骤】
① 判断栈是否空，若空则返回ERROR。
② 栈顶指针减1，栈顶元素出栈。
【算法描述】

由于顺序栈和顺序表一样，受到最大空间容量的限制，虽然可以在“满员”时重新分配空间扩大容量，但工作量较大，应该尽量避免。因此在应用程序无法预先估计栈可能达到的最大容量时，还是应该使用下面介绍的链栈。

3 链栈的表示和实现

图3.4 链栈示意图

图2 链栈示意图

由于栈的主要操作是在栈顶插入和删除，显然以链表的头部作为栈顶是最方便的，而且没必要像单链表那样为了操作方便附加一个头结点。
下面给出链栈部分操作的实现。
1．初始化
链栈的初始化操作就是构造一个空栈，因为没必要设头结点，所以直接将栈顶指针置空即可。
算法3.5 链栈的初始化
【算法描述】

2．入栈和顺序栈的入栈操作不同的是，链栈在入栈前不需要判断栈是否满，只需要为入栈元素动态分配一个结点空间，如图3所示。

图3 链栈的入栈过程
算法3.6 链栈的入栈
【算法步骤】
① 为入栈元素e分配空间，用指针p指向。
② 将新结点数据域置为e。
③ 将新结点插入栈顶。
④ 修改栈顶指针为p。
算法3.7 链栈的出栈【算法步骤】① 判断栈是否为空，若空则返回ERROR。② 将栈顶元素赋给e。③ 临时保存栈顶元素的空间，以备释放。④ 修改栈顶指针，指向新的栈顶元素。⑤ 释放原栈顶元素的空间。【算法描述】

算法3.7 链栈的出栈
【算法步骤】
① 判断栈是否为空，若空则返回ERROR。
② 将栈顶元素赋给e。
③ 临时保存栈顶元素的空间，以备释放。
④ 修改栈顶指针，指向新的栈顶元素。
⑤ 释放原栈顶元素的空间。
【算法描述】

4．取栈顶元素与顺序栈一样，当栈非空时，此操作返回当前栈顶元素的值，栈顶指针S保持不变。
算法3.8 取链栈的栈顶元素
算法描述】