1、堆栈的基本概念

堆栈是一种特殊的线性表，堆栈的数据元素以及数据元素之间的逻辑关系和线性表完全是相同的，其差别在于线性表允许在任意位置插入和删除数据元素操作，而堆栈只允许在固定一端进行插入和删除数据元素操作。堆栈中允许进行插入和删除数据元素操作的一端称为栈顶，另一端称为栈底。栈顶的当前位置是动态的，标识栈顶当前位置的变量称为栈顶指针。堆栈的插入数据元素操作通常称为进栈或入栈，删除数据元素操作称为出栈或退栈。根据堆栈的定义，每次进栈的数据元素都放在当前栈顶数据元素之前而成为新的栈顶元素，每次退栈的数据元素都是当前的栈顶元素，这样最后入栈的数据元素总是最先出栈，因此堆栈也称作后进先出的线性表。

2、堆栈的抽象数据类型

2.1、 数据集合

堆栈的数据集合可以表示为，每个数据元素的数据类型为DateType。

2.2、操作集合

• 初始化StackInitiate(S)：初始化堆栈S。
• 是否是非空堆栈StackNotEmpty(S)：判断堆栈S是否为空。若堆栈为空，函数返回0，否则返回1。
• 入栈StackPush(S,x)：在堆栈S的当前栈顶插入数据元素x。
• 出栈StackPop(S,x)：把堆栈S的当前栈顶数据元素删除并由参数x带回，若出栈成功返回1，否则返回0。
• 取栈顶数据元素StackTop(S，x)：取堆栈S的当前栈顶数据元素并由参数x带回，取到数据元素返回1，否则返回0。

3、堆栈的顺序表示和实现

3.1、顺讯堆栈的存储结构

根据前面的分析我们知道顺序堆栈和顺序表的数据成员是相同的，不同之处在于顺序堆栈的入栈和出栈操作只能对当前栈顶元素进行。顺序堆栈的存储结构如下图所示，其中表示顺序堆栈的数据元素，stack表示顺序堆栈存放数据元素的数组，MaxStackSize表示顺序堆栈数据stack的最大存储单元个数，top表示顺序堆栈数据stack的当前栈顶位置。

用C语言来描述顺序堆栈的结构如下：

typedef struct {
    DataType stack[MaxStackSize];
    int top;
} SeqStack;

3.2、顺序堆栈的操作实现

3.2.1、初始化

顺序堆栈的初始化非常简单，只需要将栈顶位置置为0便可。

void StackInitiate(SeqStack *S) {
    S->top = 0;
}

3.2.2、非空判断

顺序堆栈的栈顶位置为0则表示堆栈是空的。

int StackNotEmpty(SeqStack S) {
    if (S.top <= 0) {
        return 0;
    }
    return 1;
}

3.2.3、入栈

将数据元素x存放在顺序堆栈S的栈顶，成功返回1，失败返回0。

int StackPush(SeqStack *S, DataType x) {
    if (S->top >= MaxStackSize) {
        printf("堆栈已满，无法插入数据");
        return 0;
    } else {
        S->stack[S->top] = x;
        S->top++;
        return 1;
    }
}

3.2.4、出栈

取出顺序堆栈S的栈顶数据元素值由参数x带回，成功返回1，失败返回0。

int StackPop(SeqStack *S, DataType *x) {
    if (S->top <= 0) {
        printf("堆栈无数据元素");
        return 0;
    } else {
        S->top --;
        *x = S->stack[S->top];
        return 1;
    }
}

3.2.5、取栈顶元素

取出顺序堆栈S的栈顶数据元素值由参数x带回，成功返回1，失败返回0。

int StackTop(SeqStack S, DataType *x) {
    if (S.top <= 0) {
        printf("堆栈无数据元素");
        return 0;
    } else {
        *x = S.stack[S.top - 1];
        return 1;
    }
}

3.3、顺序堆栈的时间复杂度

从上面的分析中可以看出，顺序堆栈的操作中都没有循环语句，所以顺序堆栈的所有操作的时间复杂度为O(1)。

4、堆栈的链式表示和实现

4.1、链式堆栈的存储结构

链式堆栈的存储结构和单链表的存储结构完全相同，都是用结点构成链。每个结点除数据域外还有一个或一个以上的指针域。数据域用来存放数据元素，指针域用来构造数据元素之间的关系。堆栈有两端，插入元素和删除元素的一端为栈顶，另一端为栈底。对链式堆栈来说，若把靠近头指针的一端定义为栈顶，则插入元素和删除元素时不需要遍历整个链，时间复杂度为O(1)，否则，若把远离头指针的一端定义为栈顶，则每次插入元素和删除元素时都需要遍历整个链，其时间复杂度为O(n)。因此链式堆栈设计成把靠近头指针的一端定义为栈顶更为合理。下图是带头结点的链式堆栈的示意图。

根据上述分析我们可以用C语言定义链式堆栈如下：

typedef struct SNode {
    DataType data;
    struct SNode *next;
} LSNode;

4.2、链式堆栈操作和实现

4.2.1 初始化

void StackInitiate(LSNode **head) {
    *head = (LSNode *) malloc(sizeof(LSNode));
    (*head)->next = NULL;
}

4.2.2、非空判断

链式堆栈的头结点指针指向NULL则表示栈是空的，返回0，否则返回1。

int StackNotEmpty(LSNode *head) {
    if (head->next == NULL) {
        return 0;
    }
    return 1;
}

4.2.3、入栈

把数据元素x插入到链式堆栈head的栈顶作为新的栈顶。

void StackPush(LSNode *head, DataType x) {
    LSNode *p = (LSNode *) malloc(sizeof(LSNode));
    p->data = x;
    p->next = head->next;
    head->next = p;
}

4.2.4、出栈

取出顺序堆栈的栈顶数据元素值由参数x带回，成功返回1，失败返回0。

int StadkPop(LSNode *head, DataType *x) {
    LSNode *p = head->next;
    if (p == NULL) {
        printf("堆栈已空");
        return 0;
    }
    head->next = p->next;
    *x = p->data;
    free(p);
    return 1;
}

3.2.5、取栈顶元素

取出顺序堆栈的栈顶数据元素值由参数x带回，成功返回1，失败返回0。

int StackTop(LSNode *head, DataType *x) {
    LSNode *p = head->next;
    if (p == NULL) {
        printf("堆栈已空");
        return 0;
    }
    *x = p->data;
    return 1;
}

3.2.6、撤销动态申请空间

和单链表一样，链式堆栈的结点空间是程序动态申请的，而系统只负责自动回收程序中静态分配的内存空间，所以需要增加一个撤销动态申请空间的操作。

void Destory(LSNode *head) {
    LSNode *p, *p1;
    p = head;
    while (p != NULL) {
        p1 = p;
        p = p->next;
        free(p1);
    }
}

4.3、链式堆栈的时间复杂度

从上面的分析中可以看出，链式堆栈的操作中都没有循环语句，所以链式堆栈的所有操作的时间复杂度为O(1)。