栈在括号匹配中的应用
- 最后出现的左括号最先被匹配**(LIFO)**
- 每出现一个右括号，就出栈一个左括号
- 若没有匹配的左括号，报错
boolbracketCheck(charstr[],intlength){SqStack S;InitStack(S);for(inti=0;i<length;i++){if(str[i]=='('||str[i]=='['||str[i]=='{'){Push(S,str[i]);//扫描到左括号，入栈}else{if{StackEmpty(S))//扫描到右括号，且当前栈空returnfalse;//匹配失败chartopElem;pop(S,topElem);//栈顶元素出栈if(str[i]==')'&&topElem!='(')returnfalse；if(str[i]=='}'&&topElem!='{')returnfalse；if(str[i]==']'&&topElem!='[')returnfalse；}}returnStackEmpty(S);//检索完全部括号后，栈空说明匹配成功}栈在表达式求值中的应用
- 操作数：123456
- 运算符：加减乘除
- 界限符：括号
- 逆波兰表达式 = 后缀表达式
- 运算符在两个操作数后面
- 波兰表达式 = 前缀表达式
- 运算符在两个操作数前面
- 逆波兰表达式 = 后缀表达式
中缀表达式
- 运算符在两个操作数中间
#中缀表达式求值
用栈实现中缀表达式的计算：
初始化两个栈，操作数栈和运算符栈
若扫描到操作数，压入操作数栈
若扫描到运算符或界限符，则按照 “中缀转后缀” 相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）
&后缀表达式&
- 后缀表达式适用于基于栈的编程语言（stack-oriented programming language），如：Forth、PostScript
#中缀表达式转后缀表达式
- 由于运算顺序不唯一，因此对应的后缀表达式也不唯一，为了算法的“确定性”，这里引入“左优先”原则
初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
从左到右处理各个元素，直到末尾。可能遇到三种情况：
① 遇到操作数。直接加入后缀表达式。
② 遇到界限符。遇到 ( 直接入栈；遇到 ) 则依次弹出栈内运算符并加入后缀表达式，直到弹出 ( 为止。注意：( 不加入后缀表达式。
③ 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 ( 或栈空则停止。之后再把当前运算符入栈。
- 由于运算顺序不唯一，因此对应的后缀表达式也不唯一，为了算法的“确定性”，这里引入“左优先”原则
#后缀表达式求值
①从左往右扫描下一个元素，直到处理完所有元素
②若扫描到操作数则压入栈，并回到①；否则执行③
③若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈
- 栈顶为右操作数，栈底为左操作数
前缀表达式
#中缀表达式转前缀表达式
- “右优先原则”
#前缀表达式求值
- 从右往左扫描表达式每一个元素，直到全部遍历完毕
- 读到操作数：直接压入栈，返回步骤 1 继续扫描
- 读到运算符：连续弹出栈顶 2 个元素，执行对应运算，运算结果压回栈顶，返回步骤 1
- 遍历结束后，栈中仅剩唯一元素，即为表达式最终结果
- 栈顶为左操作数，栈底为右操作数
函数调用栈
- 可以把原始问题转化为属性相同，但规模更小的问题
函数调用时，需要用一个栈存储
- 调用返回地址
- 局部变量
- 实参
缺点：递归层数太多可能导致栈溢出
- 递归层数越多，空间复杂度越高
- 可能包含重复运算
队列的应用
- 树的层次遍历
- 图的广度优先遍历
- 在操作系统中的应用：FCFS(Frist Come First Service,先来先服务）
