一、栈的概念和特征
栈是一种元素先进后出(LIFO)的数据结构，它限定仅仅在表尾进行插入和删除操作，是一种线性表。其中，允许插入、删除的一端称为栈顶，另一端称为栈底，不含任何元素的栈称为空栈。对于栈的操作包括入栈push和出栈pop
二、栈的存储结构
1. 顺序存储
顺序存储中，栈保存在线性表中，重点在于标记合理的栈顶元素指针，在入栈之后累计，出栈之后释放，同时注意满栈，空栈等边界条件的处理。
顺序存储有种特殊情况，即两栈共享空间，提高了空间的利用率，但是逻辑相对复杂，同时要注意两个栈的数据必须是同类型。这种结构在两个栈的数据处理逻辑相反，即此消彼长的时候，相对的更有意义。
2.链式存储
链式存储的栈也称之为链栈，实际的存储结构是单链表，将链表的头部作为栈顶。当是空栈时，实际链表头部指向为空，即top->NULL。进栈即将新节点插入头部，替换头部指针；出栈即为删除头部节点，更新头部指针。也要关注各种栈为空和即将为空的边界条件（出栈操作后）。
三、栈的应用
1.递归函数
递归中前序结果依赖后序处理结果，如经典的斐波拉契数列问题的递归解法，以下递归函数，可以通过递归代码实现，从复杂高度逐渐递归到简单逻辑，再反推，最终得到结果。值得注意的是，程序中栈的大小有限，太大的栈深度可能无法得到结果（如超时）或者会抛出异常（栈溢出）。
递归函数：直接调用自身或者通过其他语句间接调用自身的函数
斐波拉契的递归代码
int fb (int i){
if (i < 2)
return i == 0 ?0: 1;
return fb(i - 1) + fb(i - 2);
}
int main(){
int i ;
for(i = 1; i < 40; i++){
printf("%d ", fb(i));
}
}
2.四则运算与逆波兰式
1）概念
逆波兰式（wiki ）是一种数学表达方式，所有的操作符位于计算数的后面，无需用括号表示算术优先级，也称之为后缀表达式。这种方式可以使程序方便地实现四则运算。通过后缀表达式，由于运算符都在运算数字之后出现，再结合栈的特性，即可以完成相关计算。举例说明：
后缀表达式为9 3 1 - 3 * + 10 2 / + ，计算规则是
依次从左遍历表达式，遇到数字，进栈，遇到符号将在栈顶的两数字元素出栈，并执行运算，结果入栈，直到获得最终结果
2）过程演示
遇到数字9 3 1 ，依次入栈，遇到符号 - ， 1，3 出栈，执行3 - 1 = 2入栈，栈中9 2 ；
3入栈，栈中9 2 3 ， 符号*，执行2 * 3 = 6 入栈，栈中 9 6 ；
符号 + ，执行9+6，15入栈，栈中 15；
10 2 入栈，栈中15 10 2 ；
符号 / ， 执行 10 / 2 = 5 入栈，栈中15 5 ；
符号+ ，执行15+5 = 20 进栈，即为最终结果。
3）后缀表达式转换
标准的四则运算表达式也称为中缀表达式，中缀表达式转后缀表达式的过程如下：
从左往右遍历中缀表达式，遇到数字进行输出；空栈时运算符直接入栈；左括号入栈；遇到右括号，执行出栈并输出元素，直到遇到左括号，括号不输出；遇到运算符，弹出所有优先级等于或者大于当前符号的运算符，并将当前符号入栈；最终所有元素依次出栈，获得表达式。
4）中缀转后缀过程
以9+(3-1)*3+10/2为例
遍历，9输出，+ 栈中为空，入栈，左括号入栈；
3输出，- 不高于 + ，入栈，1 输出，当前输出9 3 1，栈中+ ( -；
右括号，- ，（出栈，遇到左括号，输出为9 3 1 -， 栈中+；
符号* 优先级大于+ ，入栈，3输出，当前输出为9 3 1 - 3，栈中+ *；
遇到+，优先级小于，等于+，出栈，+出栈，+入栈，栈中+，输出为9 3 1 - 3 * +；
10输出，/ 优先级大于+，/ 入栈，当前输出为9 3 1 - 3 * + 10 ，栈中+ /；
2 输出，栈中输出，得到最终结果。 9 3 1 - 3 * + 10 2 /；
另一种方法为根据优先级，忽略括号，构建树形结构，分别对应树的中序遍历和后序遍历。本文内容较多，在下一篇会做简单介绍。
以上读书笔记。
