对于栈来讲，理论上线性表的操作特性它都具备，可由于它的特殊性，所以针对它在操作上会有些变化。特别是插入和删除操作，我们改名为push和pop，英文直译的话是压和弹，更容易理解。你就把它当成是弹夹的子弹压入和弹出就好记忆了，我们一般叫进栈和出栈。

ADT 栈(stack)
Data
    同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
    InitStack(*S):    初始化操作，建立一个空栈S。
    DestroyStack(*S): 若栈存在，则销毁它。
    ClearStack(*S):   将栈清空。
    StackEmpty(S):    若栈为空，返回true，否则返回false。
    GetTop(S, *e):    若栈存在且非空，用e返回S的栈顶元素。
    Push(*S, e):      若栈S存在，插入新元素e到栈S中并成为栈顶元素。
    Pop(*S, *e):      删除栈S中栈顶元素，并用e返回其值。
    StackLength(S):   返回栈S的元素个数。
endADT

由于栈本身就是一个线性表，那么线性表的顺序存储和链式存储，对于栈来说，也是同样适用的。

栈的顺序存储结构

既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。线性表是用数组来实现的，想想看，对于栈这种只能一头插入删除的线性表来说，用数组哪一端来作为栈顶和栈底比较好？

对，没错，下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小，所以让它作栈底。

我们定义一个top变量来指示栈顶元素在数组中的位置，这top就如同中学物理学过的游标卡尺的游标，如图，它可以来回移动，意味着栈顶的top可以变大变小，但无论如何游标不能超出尺的长度。同理，若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判定条件定为top等于-1。

image-20200414090025436

栈的结构定义

#define OK 1
#define ERROR 0

#define MAXSIZE 5

typedef int Status;
// SElemType类型根据实际情况而定，这里假设为int
typedef int SElemType;

typedef struct {
    SElemType data[MAXSIZE];
    int top; // 用于栈顶的指针
}SqStack;

若现在有一个栈，StackSize是5，则栈普通情况、空栈和栈满的情况、空栈和栈满的情况示意图如图所示。

空栈-满栈

进栈操作

对于栈的插入，即进栈操作，其实就是做了如图所示的处理。

进栈

代码实现：

// 插入元素e为新的栈顶元素
Status Push(SqStack *S, SElemType e) {
    if ((*S).top == MAXSIZE-1) {
        // 满栈
        return ERROR;
    }
    // 栈顶元素加1
    (*S).top++;
    // 将新的元素放置在栈顶
    (*S).data[(*S).top] = e;
    return OK;
}

出栈操作

操作出栈操作pop，代码如下：

// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
Status Pop(SqStack *S, SElemType *e) {
    // 先判断是否是空栈
    if (S->top == -1) {
        return ERROR;
    }
    // 记录要删除的元素
    *e = S->data[S->top];
    // 栈顶指针减1
    S->top--;
    return OK;
}

两者没有涉及到任何循环语句，因此时间复杂度均是O(1)。

两栈共享空间

其实栈的顺序存储还是很方便的，因为它只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题。不过它有一个很大的缺陷，就是必须事先确定数组存储空间大小，万一不够用了，就需要编程手段来扩展数组的容量，非常麻烦。对于一个栈，我们也只能尽量考虑周全，设计出合适大小的数组来处理，但对于两个相同类型的栈，我们却可以做到最大限度地利用其事先开辟的存储空间来进行操作。

如果我们有两个相同类型的栈，我们为它们各自开辟了数组空间，极有可能是第一个栈已经满了，再进栈就溢出了，而另一个栈还有很多存储空间空闲。这又何必呢？我们完全可以用一个数组来存储两个栈，只不过需要点小技巧。

我们的做法如图，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为数组的末端，即下标为数组长度n-1处。这样，两个栈如果增加元素，就是两端点向中间延伸。

两栈共享空间

其实关键思路是：它们是在数组的两端，向中间靠拢。top1和top2是栈1和栈2的栈顶指针，可以想象，只要它们俩不见面，两个栈就可以一直使用。

从这里也就可以分析出来，栈1为空时，就是top1等于-1时；而当top2等于n时，即是栈2为空时。

若栈2是空栈，栈1的top1等于n-1时，就是栈1满了。反之，当栈1为空栈时，top2等于0时，为栈2满。但更多的情况，其实就是我刚才说的，两个栈见面之时，也就是两个指针之间相差1时，即top1+1==top2为栈满。

两栈共享空间的结构的代码如下：

typedef struct {
    SElemType data[MAXSIZE];
    int top1;// 栈1栈顶指针
    int top2;// 栈2栈顶指针
}SqDoubleStack;

插入

对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈1还是栈2的栈号参数stackNumber。插入元素的代码如下：

// 插入元素e为新的栈顶元素
Status Push(SqDoubleStack *S, SElemType e, int stackNumber) {
    // 先判断是否满栈
    if (S->top1 + 1 == S->top2) {
        return ERROR;
    }
    // 判断是向1栈插入还是2栈插入
    if (stackNumber == 1) {
        S->top1++;
        S->data[S->top1] = e;
    } else {
        S->top2--;
        S->data[S->top2] = e;
    }
    return OK;
}

因为在开始已经判断了是否有栈满的情况，所以后面的top1+1或top2-1是不担心溢出问题的。

删除

对于两栈共享空间的pop方法，参数就只是判断栈1栈2的参数stackNumber，代码如下：

// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
Status Pop(SqDoubleStack *S, SElemType *e, int stackNumber) {
    if (stackNumber == 1) {
        if (S->top1 == -1) {
            // 说明栈1已经是空栈，溢出
            return ERROR;
        }
        *e = S->data[S->top1];
        S->top1--;
    } else {
        if (S->top2 == MAXSIZE) {
            // 说明栈2已经是空栈，溢出
            return ERROR;
        }
        *e = S->data[S->top2];
        S->top2++;
    }
    return OK;
}

总结

事实上，使用这样的数据结构，通常都是当两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况。就像买卖股票一样，你买入时，一定是有一个你不知道的人在做卖出操作。有人赚钱，就一定是有人赔钱。这样使用两栈共享空间存储方法才有比较大的意义。否则两个栈都在不停地增长，那很快就会因栈满而溢出了。

当然，这只是针对两个具有相同数据类型的栈的一个设计上的技巧，如果是不相同数据类型的栈，这种办法不但不能更好地处理问题，反而会使问题变得更复杂，大家要注意这个前提。

栈的链式存储结构

栈的链式存储结构，简称为链栈。

栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？由于单链表有头指针，而栈顶指针也是必须的，那干吗不让它俩合二为一呢，所以比较好的办法是把栈顶放在单链表的头部。另外，都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。

链栈

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题。

但对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候。

链栈的结构定义

#define OK 1
#define ERROR 0

#define MAXSIZE 5

typedef int Status;

// SElemType类型根据实际情况而定，这里假设为int
typedef int SElemType;

typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct LinkStack {
    LinkStackPtr top;// 栈顶指针
    int count; // 栈的长度
}LinkStack;

链栈的操作绝大部分都和单链表类似，只是在插入和删除上，特殊一些。

进栈操作

对于链栈的进栈push操作，假设元素值为e的新结点是s，top为栈顶指针，示意图如图所示。

进栈

代码实现：

// 插入元素e为新的栈顶元素
Status Push(LinkStack *S, SElemType e) {
    // 创建新的结点
    LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
    s->data = e;
    
    // 将新节点指向栈顶
    s->next = S->top;
    // 将新结点赋值给栈顶指针
    S->top = s;
    S->count++;
    return OK;
}

出栈操作

至于链栈的出栈pop操作，也是很简单的三句操作。假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可，如图所示。

出栈

代码实现：

// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
Status Pop(LinkStack *S, SElemType *e) {
    if (S->top->next == NULL) {
        // 空栈
        return ERROR;
    }
    LinkStackPtr p;
    *e = S->top->data;
    p = S->top;
    S->top = S->top->next;
    free(p);
    S->count--;
    return OK;
}

链栈的进栈push和出栈pop操作都很简单，没有任何循环操作，时间复杂度均为O(1)。

顺序栈与链栈

• 对比一下顺序栈与链栈，它们在时间复杂度上是一样的，均为O(1)。
• 顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便。
• 链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。
• 所以它们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。