考点猜测
应该重概念，和表达式变化、利用栈计算式子这一块。
只允许在一端插入和删除的线性表
- 具有后进先出（LIFO） 特性
- 栈顶（top）、栈底（bottom）
- ADT中可以进行的操作：
- void CreatStack(Stack s, int maxsize) \ 栈初始化，构造一个空栈。
BOOL IsEmpty(Stack ps) \ 栈判空
BOOL IsFull(Stack* ps) \ 栈判满
BOOL Push(Stack* ps, T_chd* px) \ 入栈
BOOL Pop(Stack* ps, T_chd* px) \ 出栈
- void CreatStack(Stack s, int maxsize) \ 栈初始化，构造一个空栈。
¶ 顺序栈
栈的顺序存储结构简称为顺序栈,是运算受限的顺序表。
- 元素用数组存放，栈底位置是固定不变的，栈顶位置是随着入栈和出栈变化的
- 编程要注意上溢和下溢的处理
- 上溢（Overflow）：过度Push
- 下溢（Underflow）：过度Pop
数据结构类型定义：
typedef struct stack{
int Top;
int MaxStack;
T_chd Elements[MAX_SIZE];
}Stack;
¶ 链栈
栈的链式存储结构称为链栈。是运算受限的链表。
- 链式栈(理论上)无栈满问题，空间可扩充
- 链式栈的栈顶在链头
- 动态分配栈元素，适合于多个栈共享内存，互不干扰
入栈：头插法
出栈：删除首个元素
¶ 应用
¶ 数制转换
¶ 算法步骤
- 初始化空栈：创建一个用于存储余数的栈
- 连续除法求余：
- 将十进制数N不断除以目标进制d
- 将每次的余数压入栈中
- 用商替换N继续上述过程，直到商为0
- 逆序输出结果：将栈中的余数依次弹出，得到转换后的结果
¶ 代码示例
把N转为八进制：
while(N) {
Push(S, N%8);
N = N/8;
}
while(!IsStackEmpty(S)) {
Pop(S, e);
printf("%d", e);
}
¶ 括号匹配的检验
建立左括号栈，出现右括号出栈一次，“抵消完”即括号匹配
¶ 表达式求值
表达式分类：
- 前缀表达式（逆波兰式），不常用
- 中缀表达式：如 12*(20-5)+30
- 符合人类阅读习惯，但计算机处理复杂
- 后缀表达式（波兰式）如： 12 20 5 - * 30 +
- 已隐含了运算优先级，括号不再出现
借助栈实现计算过程，分两步：
- 中缀表达式转后缀表达式
- 算后缀表达式的值
¶ 中缀表达式转后缀表达式
从左到右扫描中缀表达式：
- 遇到操作数：直接输出
- 遇到“(”：入栈“(”
- 遇到“)”：持续出栈并输出,直到出栈1个“(”。(括号不打印输出)
- 遇到符号：判断该符号和栈顶符号优先级，如果栈顶优先级高，则持续出栈直到栈顶符号优先级小于该符号、或栈顶符号为空或“(”，将该符号入栈
- 扫描完中缀表达式后将栈内剩余符号全部出栈输出
¶ 后缀表达式求值
从左到右扫描后缀式，遇到数字立即入栈，遇到符号则连续出栈两个数作为其右操作数和左操作数并将结果入栈，直到扫描结束，结果在栈底出栈即可。
¶ 递归
直接或间接的调用自身的过程叫递归过程（recursion）
一个过程或函数在其中直接或间接地调用自身的方法
两大要素：
- 递归要素
- 问题要能够分解为更小的子问题，并调用自身解决
- 基准要素
- 递归最终要能够结束，防止无限循环。即子问题要能够缩小到最终能得到结果的情形
递归方法进行进制转换：
void Convert(int N) {
if(N) {
Convert(N/8); // 先 递 归 处 理 高 位
printf("%d", N%8); // 后 输 出 当 前 位
}
}