栈，线性表的一种特殊的存储结构。与学习过的线性表的不同之处在于栈只能从表的固定一端对数据进行插入和删除操作，另一端是封死的。

栈结构.png

由于栈只有一边开口存取数据，称开口的那一端为“栈顶”，封死的那一端为“栈底”，好比子弹夹只有一个口可以放子弹和取子弹。

“先进后出”原则

使用栈存储数据元素，对数据元素的“存”和“取”有严格的规定：数据按一定的顺序存储到栈中，当需要调取栈中某数据元素时，需要将在该数据元素之后进栈的先出栈，该数据元素才能从栈中提取出来。
如上图，栈中存放了 4 个数据元素，进栈的顺序是 A 先进栈，然后 B 进，然后 C 进，最后 D 进栈；当需要调取 A 时，首先 D 出栈，然后 C 出栈，然后 B 出栈，最后 A 才能出栈被调用。

栈操作数据元素的方法

栈操作数据元素只有两种动作：

1. 数据元素用栈的数据结构存储起来，称为“入栈”，也叫“压栈”。
2. 数据元素由于某种原因需要从栈结构中提取出来，称为“出栈”，也叫“弹栈”。

这里的压栈和弹栈也是根据弹夹的压子弹和弹子弹而来的

栈的两种表示方式

既然栈也是线性表，那么它就同样有线性表的两种表示形式：顺序栈 和 链式栈（简称“链栈”）。

两者的区别在于存储的数据元素在物理结构上是否是相互紧挨着的。顺序栈存储元素预先申请连续的存储单元；链栈需要即申请，数据元素不紧挨着。

栈的“上溢”和“下溢”

栈存储结构调取栈中数据元素时，要避免出现“上溢”和“下溢”的情况：
“上溢”：在栈已经存满数据元素的情况下，如果继续向栈内存入数据，栈存储就会出错。
“下溢”：在栈内为空的状态下，如果对栈继续进行取数据的操作，就会出错。

对于栈的两种表示方式来说，顺序栈两种情况都有可能发生；而链栈由于“随时需要，随时申请空间”的存储结构，不会出现“上溢”的情况。

顺序栈

顺序栈的实现采用的是数组。
在顺序栈中设定一个随时指向栈顶元素的变量（一般命名为 top ），当 top 的值为 -1 时，说明数组中没有数据，即栈中没有数据元素，为“空栈”；只要数据元素进栈，top 就加 1 ；数据元素出栈， top 就减 1 。
例如，使用顺序栈的存储结构将（’a’,’b’,’c’,’d’）四个元素逐个压栈并输出栈顶元素。

#include <stdio.h>
//元素elem进栈
int push(char* a,int top,char elem){
    a[++top]=elem;
    return top;
}
//数据元素出栈
int pop(char * a,int top){
    if (top==-1) {
        printf("空栈");
        return -1;
    }
    printf("弹栈元素：%c\n",a[top]);
    top--;
    return top;
}
int main() {
    char a[10];
    int top=-1;
    top=push(a, top, 'a');
    top=push(a, top, 'b');
    top=push(a, top, 'c');
    top=push(a, top, 'd');
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    return 0;
}

image.png

链栈

链栈，用线性表的链式存储结构实现。
链栈一般不需要创建头结点，头结点会增加程序的复杂性，只需要创建一个头指针就可以了。
用链表表示栈时，用链表头结点的一端作为栈的栈顶端，这样做的好处是当数据元素压栈或者弹栈时，直接使用头指针就可以完成，不需要增设额外的指针。

用链栈实现将（’a’,’b’,’c’,’d’）四个数据元素压栈，再依次弹栈：

#include <stdio.h>
#include <stdlib.h>
typedef struct lineStack{
    char data;
    struct lineStack * next;
}lineStack;
lineStack* push(lineStack * stack,char a){
    lineStack * line=(lineStack*)malloc(sizeof(lineStack));
    line->data=a;
    line->next=stack;
    stack=line;
    return stack;
}
lineStack * pop(lineStack * stack){
    if (stack) {
        lineStack * p=stack;
        stack=stack->next;
        printf("弹栈元素：%c ",p->data);
        if (stack) {
            printf("栈顶元素：%c\n",stack->data);
        }else{
            printf("栈已空\n");
        }
        free(p);
    }else{
        printf("栈内没有元素");
        return stack;
    }
    return stack;
}
int main() {
    lineStack * stack=NULL;
    stack=push(stack, 'a');
    stack=push(stack, 'b');
    stack=push(stack, 'c');
    stack=push(stack, 'd');
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    return 0;
}

image.png

栈的实际应用

括号匹配算法

在编写代码的时候，经常会用到两种括号：圆括号 “()” 和大括号 “{}” 。不管使用哪种括号，程序编译没有问题的其中一个重要因素就是所使用的括号是否能够匹配上.

在编写程序时，括号可以嵌套，即： “({()})” 这种形式，但 “({)” 或者 “({}” 都不符合要求。

括号匹配要求：

给出任意搭配的括号，判断是否匹配。

设计思路

• 如果碰到的是左圆括号或者左大括号，直接压栈；
• 如果碰到的是右圆括号或者右大括号，就直接和栈顶元素配对：如果匹配，栈顶元素弹栈；反之，括号不匹配；

实现代码

#include <stdio.h>
#include <string.h>
int top=-1;//top变量时刻表示栈顶元素所在位置
void push(char * a,int elem){
    a[++top]=elem;
}
void pop(char* a){
    if (top==-1) {
        return ;
    }
    top--;
}
char visit(char * a){
    //调取栈顶元素，不等于弹栈，如果栈为空，为使程序不发生错误，返回空字符
    if (top!=-1) {
        return a[top];
    }else{
        return ' ';
    }
}
int main() {
    char a[30];
    char bracket[100];
    printf("请输入括号序列：");
    scanf("%s",bracket);
    getchar();
    int length=(int)strlen(bracket);
    for (int i=0; i<length; i++) {
        //如果是左括号，直接压栈
        if (bracket[i]=='('||bracket[i]=='{') {
            push(a, bracket[i]);
        }else{
            //如果是右边括号，判断与栈顶元素是否匹配，如果匹配，栈顶元素弹栈，程序继续运行；否则，发现括号不匹配，输出结果直接退出
            if (bracket[i]==')') {
                if (visit(a)=='(') {
                    pop(a);
                }else{
                    printf("括号不匹配");
                    return 0;
                }
            }else{
                if (visit(a)=='{') {
                    pop(a);
                }else{
                    printf("括号不匹配");
                    return 0;
                }
            }
        }
    }
    //如果所有括号匹配完成，栈内为空，说明所有括号全部匹配成功
    if (top!=-1) {
         printf("括号不匹配");
    }else{
       printf("括号匹配");
    }
}

image.png