栈的顺序存储（顺序栈的实现、基本运算以及共享栈）和链式存储

1. 栈的顺序存储结构

1) 顺序栈的实现

栈的顺序存储称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据 元素，同时附设一个指针(top)指示当前栈顶的位置。

栈的顺序存储类型可描述为：

#define MaxSize 50  //定义栈中元素的最大个数
typedef struct{
    Elemtype data[MaxSize];  //存放找中元素
    int top;  // 栈顶指针
}SqStack;

栈顶指针：S.top，初始时设置S.top=-1；栈顶元素：S.data[S.top]。

进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。

出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1。

栈空条件：S.top=-1；栈满条件：S.top==MaxSize-1；栈长：S.top+1。

由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能 发生栈上溢，此时应及时向用户报告消息，以便及时处理，避免出错。

图3-2  栈顶指针和栈中元素之间的关系

2) 顺序栈的基本运算

栈操作的示意图如图3-2所示，图3-2 (a)是空栈，图3-2 (c)是A、B、C、D、E共5 个元素依次入栈后的结果，图3-2 (d)是在图3-2 (c)之后E、D、C相继出栈，此时栈中还 有2个元素，或许最近出栈的元素C、D、E仍在原先的单元存储着，但top指针已经指向了 新的栈顶，则元素C、D、E已不在栈中了，读者应通过该示意图深刻理解栈顶指针的作用。 下面是顺序上常用的基本运算的实现。

1) 初始化

void InitStack(&S){
    s.top=-1;  //初始化栈顶指针
}

2) 判栈空

bool StackEmpty(S){
if(s.top==-1)  //栈空
    return true;
else  //不空
    return false;
}

3) 进栈

bool Push(SqStack &S, ElemType x) {
    if(S.top==MaxSize-1)  //栈满，报错
        return false;
    S.data[++S.top] = x;  //指针先加 1，再入栈
        return true;
}

4) 出栈

bool Pop(SqStack &S, ElemType &x){
    if(S.top==-1)  // 栈空，报错
        return false;
    x=S.data [S.top--];  //先出栈，指针再减1
    return true;
}

5) 读栈顶元素

bool GetTop(SqStack S,ElemType &x){
    if (S.top==-1)  //找空，报错
        return false;
    x=S.data[S.top];  //x记录栈顶元素
    return true;
}

注意：这里栈顶指针指向的就是栈顶元素，所以进栈时的操作是S.data[++S.top]=x，出 栈时的操作是x=S.data[S.top--]。如果栈顶指针初始化为S.top=0，即栈顶指针指向栈顶元素 的下一个位置，则入栈操作变为S.data[S.top++]=x，出栈操作变为x=S.data[--S.top]。相应的 栈空、栈满条件也会发生变化。请读者仔细体会其中的不同之处，做题时也应灵活应变。

3) 共享栈

利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的 栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，如图3-3所示。

图3-3  两个顺序栈共享存储空间

两个栈的栈顶指针都指向栈顶元素，top0=-1 时0号为空，top1=MaxSize时1号栈为 空；仅当两个栈顶指针相邻(top1-top0=1) 时，判断为栈满。当0号栈进栈时top0先加1 再赋值，1号栈进栈时top1先减1再赋值；出栈时则刚好相反。

共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被 占满时才发生上溢。其存取数据的时间复杂度均为0(1)，所以对存取效率没有什么影响。

2. 栈的链式存储结构

用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且 不存在栈满上溢的情况。通常用单链表实现，并规定所有操作都是在单链表的表头进行的。 这里规定链栈没有头结点，Lhead指向栈顶元素，如图3-4所示。 

图3-4  栈的链式存储

栈的链式存储类型可描述为

typedef struct Linknode{
    ElemType data;  //数据域
    struct Linknode *next;  //指针域
} *LiStack;  //栈类型定义

用链式存储，便于结点的插入与删除。链栈的操作与链表类似，在此不做详细讨论。 读者需要注意的是，对于带头结点和不带头结点的链栈，在具体的实现方面有所不同。