大家好，今天我要介绍一下数据结构中的一个经典结构——栈。

一：栈的介绍

与顺序表和单链表不同的是：

顺序表和单链表都可以在头部和尾部插入和删除数据，但是栈的结构就锁死了（栈的底部是堵死的）栈只能从栈顶插入（数据入栈）和删除（数据出栈）数据————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.删除栈顶数据（数据出栈）

删除数据之前要断言是否有数据可删（否则会有越界的风险）

未完待续……