定义
栈
(stack)是限定仅在表尾进行插入和删除操作的线性表
其实我们在日常的开发中，天天都在和栈打交道，比如说导航栏的实现。我们从主页面进入到一级、二级、三级页面，返回的时候，必然也是二级、一级、主页面的形式。这种后进先出(LIFO)、或者说是先进后出(FILO)的方式就是栈。
通常，我们把允许插入和删除的一端称为栈顶top，相反的一端称为栈底bottom，不含任何数据元素的栈称为空栈。一般简称为Last In First Out(LIFO)结构。
需要注意的是，栈是一个线性表。栈中的元素具有线性关系，也就是前驱和后继。最先进栈的元素就在栈底，最后进入的在栈顶。
栈的插入操作，也叫进栈、压栈、入栈。栈的删除操作，叫做出栈。
栈的抽象数据类型
ADT 栈(stack)
Data
- 和线性表相同。元素都具有相同的类型，相邻的元素具有前驱和后继关系。
Operation操作
-
InitStack(*S)：初始化，创建一个空栈 -
DestoryStack(*S)：销毁栈 -
ClearStack(*S)：清空栈 -
StackIsEmpty(S)：判断是否是空栈 -
StackLenth(*S)：获取栈的长度 -
GetStackTopElement(*S, *e)：获取栈顶元素 -
PushElement(*S, e)：压栈 -
PopElement(*S, *e)：出栈
endADT
由于线性表具有顺序存储和链式存储，所以栈也可以是这两种存储方式。
栈的顺序存储结构
栈的顺序存储结构可以使用数组实现。
顺序栈的状态有3种，空栈、满栈、有元素且未满。空栈对应的top为-1，满栈对应的top为初始化最大长度-1。
栈的结构定义：
typedef int ElementType;
typedef struct {
ElementType data[T_MAX_SIZE];
int top;
}SeqStack;
初始化栈
初始化栈，由于是顺序表，内存已经申请好，我们只需要将top置为-1即可。
TStatus InitSeqStack(SeqStack *S) {
S->top = -1;
return T_OK;
}
清空栈
清空栈，也只需要将top置为-1即可。
TStatus ClearSeqStack(SeqStack *S) {
if (S == NULL) {
return T_ERROR;
}
S->top = -1;
return T_OK;
}
获取栈顶元素
TStatus GetStackTopElement(SeqStack *S, ElementType *e) {
if (S->top == -1) {
return T_ERROR;
}
*e = S->data[S->top];
return T_OK;
}
入栈
入栈其实就是将top加1，然后再把数据放到top的位置上。
TStatus PushElement(SeqStack *S, ElementType e) {
if (S->top == T_MAX_SIZE - 1) {
return T_ERROR;
}
S->top += 1;
S->data[S->top] = e;
return T_OK;
}
出栈
出栈只需要将top减1即可。
TStatus PopElement(SeqStack *S, ElementType *e) {
if (S->top == -1) {
return T_ERROR;
}
e = S->data[S->top];
S->top -= 1;
return T_OK;
}
判断是否是空栈
bool StackIsEmpty(SeqStack S) {
if (S.top == -1) {
return true;
}
return false;
}
可以看出栈的顺序存储结构的操作，就是顺序压栈出栈，操作起来是非常简单的。但是有一个很大的缺陷，就是需要我们提前确定数组的大小，申请内存空间，申请小了，如果不够用还需要扩容；申请大了，浪费空间。
栈的链式存储结构
上面我们提到了顺序栈的缺陷，而链式栈则很好的解决了这个问题，我们只需要入栈的申请一个内存空间存放，出栈就释放即可。那么栈顶是放在链表的头部还是尾部呢？由于单链表存在头指针，而栈顶指针也是必须存在的，所以我们可以将栈顶放在链表的头部，不过这样就失去了头结点的意义。所以一般单链表链栈是不需要头结点的。
初始化栈
链式栈的内存是我们添加结点的时候才会去申请开辟的，所以在初始化之前我们需要先定义结点结构，还需要定义栈的结构。初始化的时候，只需要将top指针置空，栈长度置为0即可。
#define T_ERROR -1
#define T_OK 1
typedef int TStatus;
typedef int ElementType;
typedef struct StackNode{
ElementType data;
struct StackNode *next;
}StackNode, * LinkStackNode;
typedef struct {
LinkStackNode top; // 栈顶
int count; // 栈的长度
} LinkStack ;
TStatus InitLinkStack(LinkStack *S) {
S->top = NULL;
S->count = 0;
return T_OK;
}
清空栈
链式栈清空的时候，我们需要将栈内元素逐一释放，并且将栈长度置为0。
TStatus ClearLinkStack(LinkStack *S) {
if (S == NULL) {
return T_OK;
}
LinkStackNode p = S->top;
LinkStackNode q;
while (p) {
q = p->next;
free(p);
p = q;
}
S->count = 0;
return T_OK;
}
获取栈顶元素
获取栈顶元素，如果栈不为空的话只需要将栈顶结点的数据返回即可。
TStatus GetLinkStackTopElement(LinkStack *S, ElementType *e) {
if (S == NULL || S->count == 0) {
return T_ERROR;
}
*e = S->top->data;
return T_OK;
}
入栈
链式栈入栈需要创建一个新的结点，将该结点的next指针指向原来的栈顶结点，然后再将top指针指向新的结点；再将栈的长度加1即可。
TStatus PushElement(LinkStack *S, ElementType e) {
LinkStackNode p = (LinkStackNode)malloc(sizeof(LinkStackNode));
p->data = e;
p->next = S->top;
S->top = p;
S->count += 1;
return T_OK;
}
出栈
链式栈出栈需要将原来栈顶元素释放，并将top指针指向新的栈顶，并将栈长度减1。
TStatus PopElement(LinkStack *S, ElementType *e) {
if (S == NULL || S->count == 0) {
return T_ERROR;
}
LinkStackNode p = S->top;
*e = p->data;
S->top = p->next;
free(p);
S->count -= 1;
return T_OK;
}
链式栈在内存空间上弥补了顺序栈的缺陷，
递归
栈有一个很重要的应用，即递归。
斐波那契数列
递归有一个很经典的例子，斐波那契数列。也就是兔子繁殖数列，说是兔子在出生的2个月后，就有繁殖能力，一对兔子每个月能生出一对兔子，假设所有的兔子不死，一年以后能有多少对兔子。我们可以穷举一下，1、1、2、3、5、8、13、21、34、55、89、144。归纳一下：
上述例子，我们可以使用数列的方式来计算：
void TestFbi() {
int a[10];
a[0] = 0;
a[1] = 1;
for (int i = 2; i < 10; i++) {
a[i] = a[i-1] + a[i-2];
}
}
我们也可以使用递归的方式来计算：
int Fbi(int i) {
if(i < 2) {
return i == 0 ? 0 : 1;
}
return Fbi(i-1) + Fbi(i-2);
}
void TestFbi() {
for (int i = 0; i < 10; i++) {
printf("==%d==", Fbi(i));
}
}
递归的调用方式如下：
递归的定义
递归函数：直接调用自己或者通过一系列的调用语句间接的调用自己的函数。
使用递归最需要注意的问题就是跳出递归，如果出不去，那么程序就会陷入死循环。所以每个递归定义必须至少有一个条件满足时能够返回退出。
迭代和递归的区别是：迭代使用的是循环结构，递归使用的是选择结构。递归代码虽然比较清晰，但是递归操作会创建函数副本，消耗时间以及空间，这一点是需要注意的。
栈的应用
四则运算表达式求值
我们常用的标准四则运算表达式叫做中缀表达式，这是因为所有的运算符号都在两个数字之间。早在20世纪50年代的时候，波兰逻辑学家提出了一种不需要括号的表达方式，后缀表达式，也叫逆波兰表示。这种后缀表达式就是按照先后顺序将符号放在运算数字后面。比如说9+(3-1)*3+10/2，转化为931-3*+102/+。而后缀表达式的出现，主要是能让计算机高效的处理运算。
后缀表达式的计算是通过栈来处理，其计算逻辑规则：
从左到右遍历表达式的每个数字和符号，遇到数字就入栈，遇到符号就将处于栈顶两个数组出栈，运行运算，运算结果入栈，一直到获得最终结果。
如9+(3-1)*3+10/2的后缀表达式为931-3*+102/+，计算过程如下：首先将931入栈；遇到-号，则执行3-1，将结果2入栈；接着将3入栈；遇到*号，计算2*3，将结果6入栈；遇到+号，执行9+6，将结果15入栈；遇到10和2，入栈；然后遇到/号，执行10/2，将结果5入栈；遇到+号，执行15+5，将结果20入栈，表达式结束，然后再将20出栈。
可以看出对计算机来说，后缀表达式确实是很简单的，省去了很多关于运算顺序的逻辑。那么后缀表达式是如何从中缀表达式转换过来的呢？转换逻辑如下：
- 从左到右进行遍历
- 运算数，直接输出
- 若是左括号，直接压栈，(括号是最高优先级，无需比较)(入栈后优先级降到最低，确保其他符号正常入栈)
- 右括号，(意味着括号已结束)不断弹出栈顶运算符并输出直到遇到左括号(弹出但不输出)
- 其他运算符，将该运算符与栈顶运算符进行比较，如果优先级高于栈顶运算符则压入堆栈(该部分运算还不能进行)，如果优先级低于等于栈顶运算符则将栈顶运算符弹出并输出，然后比较新的栈顶运算符。(低于弹出意味着前面部分可以运算，先输出的一定是高优先级运算符，等于弹出是因为同等优先级，从左到右运算)直到优先级大于栈顶运算符或者栈空,再将该运算符入栈。
- 如果对象处理完毕,则按顺序弹出并输出栈中所有运算符。
如9+(3-1)*3+10/2，转化为931-3*+102/+。首先，遇到9，输出；遇到+号进栈；遇到(，进栈；遇到3，输出；遇到-，高于(，入栈；遇到1，输出；遇到)，则需要输出-和(；遇到*，优先级高于+号，入栈；遇到3，输出；遇到+，优先级低于*，将*出栈，再和栈顶+比较，优先级和+相同，弹出原来的+，此时栈里面已经空了，所以比较就停止了，把当前的+入栈；遇到10，输出；遇到/，比栈顶的+优先级高，入栈；遇到2，输出。此时，输出的为931-3*+102，栈内还有+和/，其中/是栈顶元素，再按顺序输出，结果为931-3*+102/+。
总结
- 顺序栈和链栈在时间复杂度上是一样的，均为
O(1)。 - 在空间上，顺序栈需要先申请空间，链栈添加结点的时候只需要申请结点的空间即可
- 顺序栈不需要指针域
- 如果栈的元素变化不可预料，建议使用链栈，反之则可以使用顺序栈。
- 将中缀表达式转换为后缀表达式，栈用来进出运算符号
- 将后缀表达式进行运算得出结果，栈用来进出运算的数字
参考文献：
《大话数据结构》
