栈

栈的定义

栈是限定仅在表尾进行插入和删除操作的线性表。
允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。
栈的插入操作，叫做进栈，也称压栈、入栈。 栈的删除操作，叫做出栈，也有的叫做弹栈。

栈的抽象数据类型

ADT   栈（stack）
Data
    同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
    InitStack（*S）：初始化操作，建立一个空栈。
    DestoryStack（*S）：若栈存在，则销毁它。
    ClearStack（*S）：将栈清空。
    StackEmpty（*S）：若栈为空，返回true，否则返回false。
    GetTop（S，*e）：若栈存在且非空，用e返回S的栈顶元素。
    Pop（*S，*e）：删除栈S中栈顶元素，并用e返回其值。
    StackLength（S）：返回栈S的元素个数。
endADT

栈的顺序存储结构

顺序栈：用下标为0的一端作为栈底，定义一个top变量来指示栈顶元素在数组中的位置，top必须小于栈的大小。 空栈的判定条件top等于-1。

进栈（push）操作的算法实现思路

1. 判断栈满与否，是则返回错误，否则继续；
2. 将栈顶指针加一；
3. 将新插入元素赋值给栈顶空间；
4. 返回成功。

出栈（pop）操作的算法实现思路

1. 判断栈是否为空栈，是则返回错误，否则继续；
2. 将要删除的元素赋值给e；
3. 栈顶指针减一；
4. 返回成功。

进出栈的时间复杂度

O（1）

链栈

栈顶位于单链表的头部，链栈没有头节点。
链栈的空其实就是top=NULL的时候。

进栈（push）操作的算法实现思路

1. 把当前的栈顶元素赋值给新节点的直接后继；
2. 将新的节点s赋值给栈顶指针；
3. 栈的长度+1；
4. 返回成功。

出栈（pop）操作的算法实现思路

若栈不为空，则删除栈顶元素，用e返回其值，并返回成功；否则返回错误。
1. 判断栈是否为空，是则返回错误，否则继续；
2. 将栈顶元素赋值给e；
3. 将栈顶节点赋值给p；
4. 使栈顶指针下移一位，指向后一节点；
5. 释放节点p；
6. 栈的长度减一；
7. 返回成功。

进出栈的时间复杂度

O（1）

结论

如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好用链栈，反之，如果它的变化在可控范围内，那么使用顺序栈好一些。

应用----递归

递归的定义

把一个调用自己或者一系列的调用语句间接地调用自己的函数，叫做递归函数。
每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。

迭代和递归的区别

迭代使用的是循环结构，递归使用的是选择结构。
递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。
迭代则不需要反复调用函数和占用额外的内存。

为何使用栈？

递归的过程其实是一个逆推的过程，使用栈这种数据结构可以很好的解决在逆推过程中恢复数据的难题。

应用----四则运算求表达式

逆波兰式（后缀表达式）

所有的符号都在运算数字后面出现。

思路

从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶的两个数字出栈，进行运算，运算结果出栈，一直到最终获得结果

中缀表达式转后缀表达式思路

从左到右遍历中缀表达式的每个数字和符号，弱势数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当期符号进栈，一直到最终输出后缀表达式为止。

计算机处理标准（中缀）表达式的两步：

1. 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）；
2. 将后缀表达式进行运算得出结果（栈用来进出运算的数字）。