栈（Stack）

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

1.顺序栈

1.1 设计一个顺序栈

栈作为一个特殊的定制化的线性存储结构，有着固定的读写方式（入栈、出栈）。所以我们设计一个顺序栈的时候，需要一个顺序的存储单元和一个存放栈顶指针的变量。

代码实现：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

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

/* 顺序栈结构 */
typedef struct {
    SElemType data[MAXSIZE];
    int top; /* 用于栈顶指针 */
}SqStack;

1.2 初始化一个顺序栈

当栈顶指针为-1时即是一个栈的初始状态
代码实现：

// 初始化一个空栈
Status InitStack(SqStack *S) {
    S->top = -1;// 大部分栈的实现都是初始化的时候将栈顶指针置为-1
    return OK;
}

1.3 清空一个顺序栈/判断栈是否为空

当栈顶指针为-1时即是一个空栈
代码实现：

// 将栈置空
Status ClearStack(SqStack *S){
    //不需要将栈内元素全部清空，只需要修改栈顶指针即可
    S->top = -1;
    return OK;
}

// 判断顺序栈是否为空;
Status StackEmpty(SqStack S){
    if (S.top == -1)
        return TRUE;
    else
        return FALSE;
}

1.4 返回栈的长度

由于我们设置栈顶指针为-1时为空，所以当栈有值时只需将栈顶指针的值加1就是栈的长度。
代码实现：

// 返回栈的长度
int StackLength(SqStack S){
    return S.top + 1;
}

1.5 获取栈顶元素（不出栈）

获取栈顶指针当前的元素
代码实现：

// 获取栈顶元素（不出栈）
Status GetStackTop(SqStack S, SElemType *e) {
    // 空栈报错
    if (S.top == -1) { return ERROR; }
    // 取值
    *e = S.data[S.top];
    return OK;
}

1.6 压栈（入栈）

由于栈的特殊性读写特性，压栈只是在栈顶加入新的元素。
代码实现：

// 压栈
Status PushStack(SqStack *S, SElemType e) {
    // 判断栈是否满了
    if (S->top == MAXSIZE-1) { return ERROR; }
    // 移动栈顶指针
    S->top++;
    // 压栈
    S->data[S->top] = e;
    
    return OK;
}

1.7 出栈

由于栈的特殊性读写特性，出压栈只是将栈顶的元素移出栈内。
代码实现：

// 出栈
Status PopStack(SqStack *S, SElemType *e) {
    // 栈空报错
    if (S->top == -1) { return ERROR; }
    // 取值
    *e = S->data[S->top];
    // 移动栈顶指针
    S->top--;
    
    return OK;
}

1.8 遍历栈的所有元素

输出栈的所有元素。
代码实现：

/// 遍历栈内所有元素
/// @param S 栈
Status StackTraverse(SqStack S) {
    if (S.top == -1) {
        printf("栈为空");
        return OK;
    }
    int i = 0;
    printf("此栈中所有元素");
    while (i<=S.top) {
        printf("%d ",S.data[i++]);
    }
    printf("\n");
    
    return OK;
}

2.链式栈

链式栈的好处在于不用再初始化的时候开辟内存，而且理论上只要有内存就可以继续入栈。但也有其麻烦的地方，在出栈的时候需要销毁出栈节点的内存。

2.1 设计一个链式栈

栈作为一个特殊的定制化的线性存储结构，有着固定的读写方式（入栈、出栈），所以我们在设计一个链式栈的时候需要一个具有存储数据和指向下一个栈元素指针的节点作为该栈的栈顶指针top。如果我们需要统计栈内元素的总个数，最好添加一个count变量，在使用起来会更加方便。

代码实现：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

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

// 链式栈节点
typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
}StackNode;

// 链式栈
typedef struct {
    StackNode *top;
    int count;
}LinkStack;

2.2 初始化一个链式栈

初始化一个链式栈只需将栈顶指针置空，计数count置为0就可以le。
代码实现：

// 初始化一个栈
Status InitLinkStack(LinkStack *S){
    /// 置空栈顶指针
    S->top = NULL;
    /// 长度置为0
    S->count = 0;
    return OK;
}

2.3 置空链式栈/判断链式栈是否为空

置空链式栈需要将栈内的所有节点全部清空，并且释放节点内存，最后将top置空，count置为0。
代码实现：

//把链栈S置为空栈
Status ClearLinkStack(LinkStack *S){
    // 辅助变量
    StackNode *p;
    StackNode *q;
    // 栈顶元素
    p = S->top;
    // 循环清空
    while (p) {
        q = p;
        p = p->next;
        free(q);// 释放内存
    }
    // 长度置为0
    S->count = 0;
    // 栈顶置空
    S->top = NULL;
    return OK;
}

// 判断栈是否为空
Status LinkStackIsEmpty(LinkStack S){
    if (S.count == 0) return TRUE;
    return FALSE;
}

//把链栈S置为空栈
Status ClearLinkStack2(LinkStack *S){
    // 辅助变量
    StackNode *q;
    // 循环清空
    while (S->top) {
        q = S->top;
        S->top = S->top->next;
        free(q);// 释放内存
    }
    // 长度置为0
    S->count = 0;
    return OK;
}

//把链栈S置为空栈
Status ClearLinkStack3(LinkStack *S){
    // 辅助变量
    StackNode *p;
    StackNode *q;
    // 栈顶元素
    p = S->top;
    // 循环清空
    while (p->next) {
        q = p;
        p = p->next;
        free(q);// 释放内存
    }
    // 长度置为0
    S->count = 0;
    return OK;
}

2.4 获取栈的长度/栈顶元素（非出栈）

长度直接返回我们设计的栈的count即可，栈顶元素直接取top节点的值就行。
代码实现：

// 获取栈的长度
int GetLinkStackLength(LinkStack S){
    return S.count;
}

// 获取栈顶元素（不出栈）
Status GetLinkStackTop(LinkStack S, SElemType *e) {
    // 栈空报错
    if (S.top == NULL) { return ERROR; }
    // 赋值
    *e = S.top->data;
    return OK;
}

2.5 压栈（入栈）

根据栈的特性，链式栈的压栈就是在栈顶处添加一个新的节点，并且更新该节点为新的栈顶，计数count加一即可。
代码实现：

// 压栈
Status PushLinkStack(LinkStack *S, SElemType e) {
    // 初始化一个新节点
    StackNode *temp = (StackNode*)malloc(sizeof(StackNode));
    // 赋值
    temp->data = e;
    // 新节点的next指向原栈顶
    temp->next = S->top;
    // 更新栈顶
    S->top = temp;
    // 增加长度
    S->count++;
    return OK;
}

2.6 出栈

出栈就是将栈顶元素移出栈，更新栈顶为原栈顶的下一个节点，计数count减一。前提是栈不能为空，所以一开始要判断是否是一个空栈。
代码实现：

// 出栈
Status PopLinkStack(LinkStack *S, SElemType *e) {
    // 空栈判断
    if (S->top == NULL) { return ERROR; }
    
    // 辅助变量
    StackNode *p = S->top;
    // 取得出栈元素
    *e = S->top->data;
    // 更新栈顶元素
    S->top = S->top->next;
    // 释放内存
    free(p);
    // 长度减1
    S->count--;
    
    return OK;
}

2.7 遍历查看链式栈

如果栈为空则打印'栈为空'，不为空则从栈顶元素开始打印。
代码实现：

void LinkStackTraverse(LinkStack S) {
    if (S.top == NULL) {
        printf("栈为空");
    } else {
        StackNode *p = S.top;
        printf("此栈中所有元素");
        while (p) {
            printf(" %d ",p->data);
            p = p->next;
        }
        printf("\n");
    }
}

2.8 验证代码

在main函数中验证上述操作
代码实现：

int main(int argc, const char * argv[]) {
    // insert code here...
//    printf("Hello, World!\n");
    
    LinkStack S;
    SElemType e;
    if (InitLinkStack(&S) == OK) {
        for (int i = 1; i<=3; i++) {
            PushLinkStack(&S, i);
        }
    }
    
    LinkStackTraverse(S);
    
    GetLinkStackTop(S, &e);
    printf("获取到的栈顶元素是：%d\n",e);
    
    printf("栈是否为空：%d\n",LinkStackIsEmpty(S));
    printf("栈是de长度是：%d\n",GetLinkStackLength(S));
    
    if (PopLinkStack(&S, &e) == OK) {
        printf("出栈的元素是：%d\n", e);
        LinkStackTraverse(S);
    } else {
        printf("出栈报错");
    }
    
    printf("清空栈的结果是：%d\n",ClearLinkStack2(&S));
    LinkStackTraverse(S);
    
    return 0;
}