3.1.2　栈的顺序存储结构及其基本运算实现

由于栈是运算受限的线性表，因此线性表的存储结构对栈也是适用的，只是操作不同而已。下面我们先来学习一下顺序栈的存储结构及其基本运算。

利用顺序存储方式实现的栈称为顺序栈。类似于顺序表的定义，栈中的数据元素用一个预设的足够长度的一维数组来实现：datatype data［MAXSIZE］，栈底位置可以设置在数组的任一个端点，而栈顶是随着插入和删除而变化的，用一个int top来作为栈顶的指针，指明当前栈顶的位置，同样将data和top封装在一个结构中，顺序栈的类型描述如下：

定义一个指向顺序栈的指针：

通常0下标端设为栈底，这样空栈时栈顶指针top＝－1；入栈时，栈顶指针加1，即s－top＋＋；出栈时，栈顶指针减1，即s－top－－。栈操作的示意图如图3－2所示。图3－2（a）是空栈，图3－2（b）是A元素进栈，图3－2（c）是A、B、C、D、E5个元素依次入栈，图3－2（d）是在图3－2（c）之后E、D、C相继出栈，此时栈中还有两个元素，栈顶指针指向元素B。通过这个示意图要深刻理解栈顶指针的作用。

图3－2 栈顶指针top与栈中数据元素的关系

在上述存储结构上基本操作的实现如下。

1.顺序栈操作的实现

顺序栈基本操作实现如下。

算法3.1 顺序栈基本操作

（1）置空栈

首先建立栈空间，然后初始化栈顶指针。

（2）判空栈

（3）入栈

（4）出栈

（5）取栈顶元素

注意以下几点说明：

第一，对于顺序栈，入栈时，首先判断栈是否满了，栈满的条件为：s－top＝＝MAXSIZE－1，栈满时，不能入栈；否则出现空间溢出，引起错误，这种现象称为上溢。

第二，出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空时常作为一种控制转移的条件。

2.两栈共享空间——双端栈

栈的应用非常广泛，经常会出现在一个程序中需要同时使用多个栈的情况。若使用顺序栈，会因为对栈空间大小难以准确估计，从而产生有的栈溢出、有的栈空间还很空闲的情况。为了解决这个问题，可以让多个栈共享一个足够大的数组空间，通过利用栈的动态特性来使其存储空间互相补充，这就是多栈的共享技术。

在栈的共享技术中最常用的是两个栈的共享技术：它主要利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的一维数组空间S［M］，将两个栈的栈底分别放在一维数组的两端，分别是0、M－1。两个栈顶动态变化，这样可以形成互补，使每个栈可用的最大空间与实际使用的需求有关。由此可见，两栈共享要比两个栈分别申请M／2的空间利用率要高。两栈共享的数据结构定义如下：

两个栈共享空间的示意如图3－3所示。下面给出两个栈共用时的初始化、进栈和出栈操作的算法。

图3－3 两栈共享空间

算法3.2 两个栈共用基本操作

思考：说明读栈顶元素的算法与退栈顶元素的算法的区别，并请写出读栈顶算法。

使用两栈共享，前提是两个栈具有相同的数据类型，并且通常是两个栈的需求有相反的关系，也就是说一个栈增长另一个栈缩短的情况，就像买股票有人赚钱，就会有人赔钱。这样两栈共享存储空间具有较大的意义。