3.2　栈的实现

与线性表类似,栈的实现既可以采用顺序存储结构也可以采用链式存储结构。采用顺序存储结构实现的栈称为顺序栈,采用链式存储结构实现的栈称为链栈。

3.2.1　顺序栈

与线性表类似,顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时设置两个指针top和base分别指向栈顶和栈底的位置。由于在顺序存储结构中,需要一次性为栈分配一片连续的内存空间,因此需要定义一个常量STACK＿INIT＿SIZE来表示为栈分配的初始容量。同时为了不让栈的存储空间受到限制,当栈的存储空间用完之后需要扩展栈的存储空间,则需要定义另外一个常量STACKINCREMENT表示存储空间分配的增量。用动态数组描述的顺序栈的存储类型如下。

栈的初始化操作是指按指定的大小为栈动态分配一片连续的存储区,并将该存储区的首地址同时送给栈顶指针top和栈底指针base,表示栈里没有任何元素,此时的栈为空栈。若base的值为NULL时则表明栈不存在。当插入一个新元素时栈顶指针加1,当删除一个元素时栈顶指针减1。栈顶指针top始终比顶元超前一个位置,因此栈满的条件是topbase＝stacksize。图3－3所示为栈顶指针和栈中元素的关系。

图3－3　栈顶指针和栈中元素的关系

值得注意的是,栈在运算过程中可能会发生“溢出”。溢出有两种情况,一种称为“上溢”（overflow）,另一种称为“下溢”（underflow）。若系统作为栈用的存储区已满,还有元素要求进栈,则称发生上溢；反之,若系统作为栈用的存储区已空,这时还要退栈,则称发生下溢。上溢是一种错误现象,一旦发生上溢,就要给栈分配一个更大的存储空间,以避免有用信息的丢失。而下溢则常用来作为控制转移的条件或程序结束的标志。

下面给出顺序栈的几种基本操作的算法函数。

1.stackinit函数

【算法思想】　构造一个空栈,即按设定的初始空间容量进行第一次存储分配。设base为栈底指针,在顺序栈中它始终指向栈底的位置；top为栈顶指针,其初值指向栈底的位置,top＝base为空栈标志。

具体算法如下。

2.stackclear函数

【算法思想】　将一个已存在的栈s清空。

具体算法如下。

3.stackempty函数

【算法思想】　判断栈是否为空,若栈空则返回1,反之返回0。

具体算法如下。

4.gettop函数

【算法思想】　若栈s不空,则用e返回s的顶元,并返回1,否则返回0。栈顶指针比顶元超前一个位置。

具体算法如下。

5.push函数

【算法思想】　将新元素e插入到栈s中。栈顶指针比顶元超前一个位置。

具体算法如下。

6.pop函数

【算法思想】　若栈不空,则删除栈s的顶元,用e保存其值,并返回成功标志1,否则返回失败标志0。

具体算法如下。

图3－4　不带头结点的链式栈示意图

3.2.2　链栈

栈也可以采用链式存储结构实现,栈的链式存储结构简称为链栈。链栈实质上是一个规定只能在表头进行插入与删除操作的单链表。链栈具有链式存储结构的优点,例如,可以提高结点的插入和删除的效率,可以根据实际需要为每个栈分配相应的单元等。图3－4所示为一个链式栈的结构。

表示栈的单链表可以带表头结点,也可不设置表头结点。以下是链栈结点的定义。

下面给出链栈的几种基本操作的算法。

1.Stackinit函数

【算法思想】　构造一个带有头节点的空的链栈,操作成功则返回1,反之返回0。

具体算法如下。

2.stackempty函数

【算法思想】　判断栈是否为空,栈空返回1,反之则返回0。

具体算法如下。

3.gettop函数

【算法思想】　若栈h不为空,则用e返回h的顶元并返回1,否则返回0。

具体算法如下。

4.push函数

【算法思想】　将新元素x压入栈h中,若操作成功返回1,反之则返回0。

具体算法如下。

5.pop函数

【算法思想】　弹出栈h的顶元并由y返回,操作成功返回1,反之则返回0。

具体算法如下。