大家好，今天我要介绍一下数据结构中的一个经典结构——栈。
一：栈的介绍
与顺序表和单链表不同的是：
顺序表和单链表都可以在头部和尾部插入和删除数据，但是栈的结构就锁死了（栈的底部是堵死的）栈只能从栈顶插入（数据入栈）和删除（数据出栈）数据————last in first out（后进先出）（最后入栈的数据要第一个出栈）。
如果进栈过程中不允许出栈：入栈 1 2 3 4————出栈4 3 2 1
二：栈的概念和结构
栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（last in first out）的原则。
压栈：栈的插入数据操作叫做进栈或压栈或入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
来看一道经典的练习题：
这道题目看到进栈顺序是1 2 3 4，很多人会直接想到出栈顺序为 4 3 2 1.
但是答案中却没有4 3 2 1
我们仔细读题：
题目要找不可能的出栈顺序，说明四个选项中有三个选项都是可能的出栈顺序。
在进栈过程中允许出栈的前提下，一种进栈顺序是可以对应出多种出栈顺序的。
这种题目的解法就是模拟实现上面的情境，以D选项为例：
3 4 2 1的出栈顺序
可以先入1 2 3，再出3，再入4，再出4，最后出2 1.
三：栈的模拟实现
栈的结构只能从栈顶插入和删除数据（我们在实现的过程中以数组或者链表的尾部当栈顶）。（头部当栈顶的话数组就麻烦了）。
栈的模拟实现使用数组或者单链表都是可以的，相对而言数组的结构实现更优一些。因为在数组尾部插入数据的代价比较小。
链表的话在尾部插入数据如果定义一个尾指针的话还是容易做到的，但是如果链表删除尾部数据的话还是要从头指针进行遍历的（单链表不可逆）（尾指针不容易找到其前一个结点）（使用双向链表就有点麻烦了）。（要是真的愿意使用链表的方式实现也是可以的，自己下去可以尝试）。
综上：
我们今天使用数组来实现栈这一数据结构，数组的尾部作为栈顶。
0.栈的结构的定义
这里我们还是使用动态内存栈。
1.栈的初始化
栈的模拟实现实际上跟顺序表很相似，甚至比顺序表还要简单。
这里值得说明的就是：
1.在初始化的过程中先给上数组4个存储空间，后面不够的话在添加。
2.程序的第17行top的含义是指向栈顶元素的下一个位置（初始情况下栈中没有数据top的下表就先为0）.(这样的话方便后续数据入栈)。
当然这里也可以让top指向栈顶元素（初始时栈中没有元素就先指向-1，栈中插入数据之后，top就是栈顶元素的下表）
两种方式都可以，看自己平时的习惯即可（你用哪种方式实现后续操作要保持一致）。
2.插入数据（数据入栈）
插入数据首先要判断空间是否够用，不够的话扩容（二倍扩容法）。
3.删除栈顶数据（数据出栈）
删除数据之前要断言是否有数据可删（否则会有越界的风险）
4.统计栈中的数据个数
5.判断栈是否为空
6.获取栈顶数据
这里66行尽量不要写成assert（ps->top），因为你写出来的栈将来在可能是给别人用的，你自己清楚top是指向栈顶元素的下一个位置，但是别人是不知道的，如果别人一位top是栈顶元素位置，使用你的栈发现了错误，就不太好，因此不如直接提供接口，利用函数去判空，程序的可读性就会提高。（下面还有例子）
7,栈的销毁
8.栈的遍历访问
这里面也是，判断条件写成函数接口的形式代码可读性更高。
这里注意，遍历访问栈中元素时，不能直接像遍历访问数组一样，栈的特性就说明了栈一定是栈顶元素拿出去以后猜能访问下面的元素，否则就不叫栈了。
四：栈相关的经典题目
有效的括号。
这道题的整体思路就是：
从左到右依次遍历字符串，遍历过程中遇到左括号就进栈，如果遇到的是右括号就出栈顶元素看是否能够跟其成功匹配。
如果匹配失败，则返回false
如果遍历完毕后栈中还有左括号，返回false
如果遍历完毕，且栈为空，返回true
自己可以下去尝试，这里不再提供代码。
完。