# 栈在括号匹配中的应用
最后出现的左括号最先被匹配，每出现一个右括号，就 "消耗" 一个左括号，遇到左括号就入栈，遇到右括号，就 "消耗" 一个左括号
处理完所有括号后，栈非空 —— 左括号单身
算法实现：
#define MaxSize 10
typedef struct {
char data[MaxSize];
int top;
}SqStack;
void InitStack(SqStack &S) //初始化栈
bool StackEmpty(SqStack S) //判断栈空
bool Push(SqStack &S,char x) //新元素入栈
bool Pop(SqStack &S,char &x) //栈顶元素出栈，用x返回
bool bracketCheck(char str[],int length){
SqStack S;
InitStack(S);
for(int i=0;i<length;i++){
if(str[i]=='(' || str[i]=='{' || str[i]=='[')
Push(S,str[i]);
else{
if(StackEmpty(S))
return false;
char topElem;
Pop(S,topElem);
if(str[i]=='}' && topElem!='{')
return false;
if(str[i]==']' && topElem!='[')
return false;
if(str[i]==')' && topElem!='(')
return false;
}
}
return StackEmpty(S);
}
# 栈在表达式求值的应用
逆波兰表达式 = 后缀表达式
波兰表达式 = 前缀表达式
中缀转后缀的手算方法：
- 确定中缀表达式中各个运算符的运算顺序
- 确定下一个运算符，按照 [左操作数 右操作数 运算符] 的方式组合成一个新的操作数
- 如果还有运算符没被处理，就继续第二步
左优先原则：只要左边的运算符能先计算，就优先算左边的
从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数
注意：两个操作数的左右顺序
用栈实现后缀表达式的计算：
- 从左往右扫描下一个元素，直到处理完所有元素
- 若扫描到操作数则压入栈，并回到第一步；否则执行下一步
- 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到第一步
若表达式合法，最后栈中留下的一个元素就是最终结果
中缀转前缀的手算方法：
- 确定中缀表达式中各个运算符的运算顺序
- 选择下一个运算符，按照 [运算符 左操作数 右操作数] 的方式组合成一个新的操作数
- 如果还有运算符没被处理，就继续第二步
右优先原则：只要右边的运算符能先计算，就优先计算右边的
用栈实现前缀表达式的计算：
- 从右往左扫描下一个元素，直到处理完所有元素
- 若扫描到操作数则压入栈，并回到第一步；否则执行下一步
- 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到第一步
中缀表达式转后缀表达式（机算）
初始化一个栈，用于保存暂时还不能确定运算顺序的运算符
从左到右处理各个元素，直到末尾。可能遇到三种情况
遇到操作数，直接加入后缀表达式
遇到界限符。遇到 '(' 直接入栈，遇到 ')' 则依次弹出栈内运算符并加入后缀表达式，直到弹出 '(' 为止。注意：'(' 不加入后缀表达式
遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到了 '(' 或栈空则停止。之后再把当前运算符入栈
按照上述方法处理完毕所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式
中缀表达式的计算（用栈实现）
- 初始化两个栈，操作数栈和运算符栈
- 若扫描到操作数，压入操作数栈
- 若扫描到运算符或界限符，则按照 "中缀转后缀" 相同的逻辑压入运算符栈（期间也会弹出运算符，每弹出一个运算符时，就要弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）
# 栈在递归中的应用
函数调用的特点：最后被调用的函数最先执行结果
函数调用时，需要用一个栈存储：
- 调用返回地址
- 实参
- 局部变量
适用递归算法解决：可以把原始问题转化为属性相同，但规模更小的问题
递归调用时，函数调用栈可称为 "递归工作栈"
每进入一层递归，就将递归调用所需的信息压入栈顶
每退出一层递归，就将栈顶弹出相应信息
缺点：
- 太多层递归可能会导致栈溢出
- 可能包含很多重复计算
# 队列应用
树的层次遍历
图的广度有限遍历
多个进程争抢使用有限的系统资源时，FCFS（先来先服务）是一种常用策略
# 矩阵的压缩存储
一维数组存储结构：各个元素大小相同，且物理上连续存放
二维数组的存储结构：行优先存储 | 列有限存储
不同矩阵的存储：用二维数组存储
对称矩阵的存储：
- 普通存储：二维数组
- 压缩存储策略：只存储主对角线和下三角区
上三角矩阵与下三角矩阵：
按照行优先 \ 列优先的原则存入一维数组中，并在最后一个位置存储常量 c
三对角矩阵的压缩存储
- 按行优先原则存储到一维数组中
稀疏矩阵的压缩存储策略
顺序存储 —— 三元组（行、列、值）
链式存储 —— 十字链表法
