程序猿必修课之数据结构（六）栈1

原文：http://www.jianshu.com/p/66da0b8935ac

上一章：程序猿必修课之数据结构（五）线性表3

栈的定义

栈（Stack）是限定仅在表尾进行插入和删除操作的线性表。

我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称 LIFO 结构。

从上面这两段话，可以确定：首先栈是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系，只不过它是一种特殊的线性表。定义中说在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。

栈的插入操作，叫做进栈，也叫压栈、入栈。

栈的删除操作，叫做出栈。

进栈出栈变化多端

最先进栈的元素，不一定是最后出栈的。

栈对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制。意思就是说，当并非所有的元素都进栈的情况下，先进去的元素也可以出栈，只要保证栈顶元素出栈就可以了。

比如，现在有 3 个元素 1、2、3，可能的出栈顺序有下面几种：

• 第一种：1、2、3 依次进栈，再 3、2、1依次出栈，显然出栈顺序为321。
• 第二种：1 进栈，1 出栈，2 进栈，2 出栈，3 进栈，3 出栈。出栈顺序为 123。
• 第三种：1 进栈，2 进栈，2 出栈，1 出栈，3 进栈，3 出栈。出栈顺序为 213。
• 第四种：1 进栈，1 出栈，2 进栈，3 进栈，3 出栈，2 出栈。出栈顺序为 132。
• 第五种：1 进栈，2 进栈，2 出栈，3 进栈，3 出栈，1 出栈。出栈顺序为 231。

栈的抽象数据类型

我们知道，栈是一个特殊的线性表，由于它的特殊性，所以与线性表的操作会略有不同。特别是插入和删除操作，我们分别叫它 push 和 pop。

栈的抽象数据类型

ADT 栈（stack）
Data
    同线性表，元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
    initStack(*S)：初始化操作，建立一个空栈 S。
    destroyStack(*S)：若栈存在，则销毁它。
    clearStack(*S)：清空栈。
    isEmpty(S)：若栈为空返回 true，否则返回 false。
    getTop(S, *e)：若栈存在且非空，用 e 返回 S 的栈顶元素。
    push(*S, e)：若栈 S 存在，插入新元素 e 到栈 S 中并成为栈顶元素。
    pop(*S, *e)：删除栈顶元素，并且 e 返回其值。
    length(S)：返回栈 S 的元素个数。
endADT

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

栈的顺序存储结构及实现

因为栈是线性表的特例，栈的顺序存储其实是线性表顺序存储的简化，简称为顺序栈。

线性表是用数组实现的，对于栈这种只能一端插入删除的线性表来说，下标为 0 的一端作为栈底比较好，因为首元素都存在栈底，变化最小。

我们定义一个变量 top 来指示栈顶元素在数组中的位置，若栈的长度为 stackSize，则栈顶位置 top 必须小于 stackSize。当栈中存在一个元素时，top 等于 0，因此把空栈的判定条件定为 top = -1。

栈的结构定义

define MAXSIZE = 10

typedef struct {
    int data[MAXSIZE];
    int top;
} SqStack;

进栈操作

boolean push(SqStack *s, int e) {
    if (s->top == MAXSIZE - 1） {
        return false;
    }
    s->top++;
    s->data[s->top] = e;
    return true;
}

出栈操作

若栈不为空，则删除栈顶元素，并把其值赋值给 e。

boolean pop(SqStac *s, int *e) {
    if (s->top == -1)
        return false;
    *e = s->data[s->top];
    s->top--;
    return true;
}

通过进栈和出栈操作的代码可以看出，时间复杂度都为 O(1)。

两栈共享空间

栈的顺序存储有一个很大的缺陷，必须先确定数组存储空间大小，而且万一不够用了，还要扩容。

对于一个栈，我们只能尽量考虑周全，设计出合适大小的数组来处理，但对于两个相同类型的栈，我们可以做到最大限度地利用事先开辟的存储空间来进行操作。

如果我们有两个相同类型的栈，我们为它们各自开辟了数组空间，有可能第一个栈已经满了，而另一个栈还有很多存储空间。我们完全可以用一个数组来存储两个栈。

我们知道，数组有两个端点，两个栈有两个栈底。可以让一个栈的栈底为数组的开始端，即下标为 0 处，另一个栈的栈底为数组的末端，即下标为数组长度 n - 1 处，这样两个栈如果增加元素，就是两端点向中间移动，如图所示。

两栈共享

top1 和 top2 是栈 1 和栈 2 的栈顶指针，只要二者的值不相等，两个栈就可以进行入栈操作。当 top1 等于 -1 时，栈 1 为空；当 top2等于 n 时，栈 2 为空。当 top2 - top1 = 1 时，栈就满了。

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

typedef struct {
    int data[MAXSIZE];
    int top1;
    int top2;
} SqDoubleStack;

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

boolean push(SqDoubleStack *s, int e, int stackNumber) {
    if (s->top2 - s->top1 == 1) {   /* 栈满 */
        return false;
    }
    if (stackNumber == 1) {
        s->data[++s->top1] = e;
    } else if (stackNumber == 2) {
        s->data[--s->top2] = e;
    }
    return true;
}

出栈方法的代码

boolean pop(SqDoubleStack *s, int *e, int stackNumber) {
    if (stackNumber == 1) {
        if (s->top1 == -1)
            return false;
        *e = s->data[s->top1--];
    } else if (stackNumber == 2) {
        if (s->top2 == MAXSIZE)
            return false;
        *e = s->data[s->top2++];
    }
    return true;
}

两栈共享通常用于两个栈的空间需求具有相反关系时，也就是一个栈增长时另一个栈在缩短。就像买卖股票一样，一个人买入时，一定有另一个人在做卖出操作。这样使用两栈共享空间存储方法才有比较大的意义。

两栈共享只针对两个具有相同数据类型的栈。

栈的链式存储结构

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

由于单链表有头指针，而栈顶指针也是必须的，所以把栈顶放在链表的头部。另外，由于已经有了栈顶在头部，所以单链表中的头结点就不需要了。

对于链栈来说，基本不存在栈满的情况，因为只要内存有空间，链表就可以一直添加结点。

链栈的结构代码如下：

/**
 * Node结点
 */
typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode, *pStackNode;

typedef struct LinkStack {
    pStackNode top; /* 栈顶指针 */
    int count;
} LinkStack;

栈的链式存储结构——进栈操作

假设新结点 s 的值为 e，top 为栈顶指针，将 s->next 指向当前栈顶结点，栈元素个数加 1。

boolean push(LinkStack *s, int e) {
    pStackNode pNewNode = (pStackNode)malloc(sizeof(StackNode));
    if (NULL == newNode)
        return false;
    pNewNode->data = e;
    /* 把当前栈顶元素赋值给新结点的直接后继 */
    pNewNode->next = s->top;
    /* 新结点作为栈顶 */
    s->top = pNewNode;
    s->count ++;
    return true;
}

栈的链式存储——出栈操作

出栈的操作步骤：先用一个变量 p 来存储要删除的栈顶结点，将栈顶指针 改为 p->next，释放 p。

boolean pop(LinkStack *s, int *e) {
    if (stackEmpty(*s)) {
        return false;
    }
    pStackNode pNode = s->top;
    *e = pNode->data;
    s->top = pNode->next;
    free(pNode);
    s->count--;
    return true;
}

上面出栈操作中，用到判断栈是否为空，那么链栈是怎样判断是否为空栈的呢？

boolean stackEmpty(LinkStack *s) {
    if (s->top->next == NULL)
        return true;
    else 
        return false;
}

总结

从链栈的进栈和出栈操作，可以看出时间复杂度都为 O(1)。

对比顺序栈和链栈，它们的时间复杂度是一样的，对于空间性能，顺序栈需要先确定一个固定的长度，可能会造成空间浪费，但是它在存取时定位很方便，而链栈则要求每个元素都有指针域，无形中增加了内存开销，但是链栈对长度是没有限制的。

所以它们的区别和线性表的顺序存储以及链式存储的区别是一样的：如果栈中的元素个数变化较大，那么使用链栈再合适不过，反之，如果元素个数变化较小，使用顺序栈会更好一些。

下一章：程序猿必修课之数据结构（七）栈2