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