3.1.3 顺序栈
1.栈的顺序存储结构
采用顺序存储结构的栈称为顺序栈。顺序栈利用一组连续的存储单元存放栈中的元素，存放顺序依次从栈底到栈顶。由于栈中元素之间的存放地址的连续性，在C语言中，同样采用数组实现栈的顺序存储。另外，增加一个栈顶指针top，用于指向顺序栈的栈顶元素。
栈的顺序存储结构类型描述如下：
用数组表示的顺序栈如图3.3所示。将元素A、B、C、D、E、F、G、H依次进栈，栈底元素为A，栈顶元素为H。在本书中，约定栈顶指针top指向栈顶元素的下一个位置（而不是栈顶元素）。
图3.3 顺序栈结构
说明：
（1）初始时，栈为空，栈顶指针为0，即S.top=0。
（2）栈空条件为S.top==0，栈满条件为S.top==StackSize-1。
（3）进栈操作时，先将元素压入栈中，即S.stack[S.top]=e，然后使栈顶指针加1，即S.top++。出栈操作时，先使栈顶指针减1，即S.top--，然后元素出栈，即e=S.stack[S.top]。
（4）栈的长度即栈中元素的个数为S.top。
注意：当栈中元素个数为StackSize时，称为栈满。当栈满时进行入栈操作，将产生上溢错误。如果对空栈进行删除操作，将产生下溢错误。因此，在对栈进行进栈或出栈操作前，要判断栈是否已满或已空。
2.顺序栈的基本运算
顺序栈的基本运算如下（以下算法的实现保存在文件“SeqStack.h”中）。
（1）栈的初始化。
（2）判断栈是否为空。
（3）取栈顶元素。
注意：取栈顶元素并不是将元素出栈，这里的操作是S.stack[S.top-1]，并没有修改栈顶指针top的值，即不能写作S.stack[-S.top]或S.stack[S.top-1]。
（4）进栈操作。
（5）出栈操作。
（6）返回栈的长度。
（7）清空栈。
3.共享栈*
栈的应用非常广泛，经常会出现一个程序需要同时使用多个栈的情况。使用顺序栈会因为栈空间的大小难以准确估计，从而造成有的栈溢出，有的栈还有空闲。为了解决这个问题，可以让多个栈共享一个足够大的连续存储空间，利用栈的动态特性使栈空间能够互相补充，存储空间从而得到有效利用，这就是栈的共享，这些栈被称为共享栈。
在栈的共享问题中，最常用的是两个栈的共享。共享栈主要通过栈底固定、栈顶迎面增长的方式实现。让两个栈共享一个一维数组stack[StackSize]，两个栈底设置在数组的两端，当有元素进栈时，栈顶位置从栈的两端向中间迎面增长；当两个栈顶相遇时，栈满。
共享栈（两个栈共享一个连续的存储空间）的数据结构类型描述如下。
其中，top[0]和top[1]分别是两个栈的栈顶指针。
例如，共享栈的存储表示如图3.4所示。
图3.4 共享栈示意图
共享栈的算法操作（以下算法保存在文件“SSeqStack.h”中）如下。
（1）初始化。
（2）进栈操作。
（3）出栈操作。
