🙊🙊作者主页：🔗求不脱发的博客
📔📔 精选专栏：🔗数据结构与算法
📋📋 精彩摘要：前面几章纤细介绍了栈与队列的基本内容及相关操作，本章将通过三个案例对栈与队列作进一步的分析，然后分别利用栈和队列的基本操作给出案例中相关算法的具体实现。
💞💞觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞
📚目录
📖【数据结构与算法】第八章：栈与队列相关应用
📝1️⃣数制的转换。
【案例描述】
十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：
N = (N div d) × d + N mod d（其中，div为整除运算，mod为求余运算）
假设现要编制一个满足下列要求的程序：
- 对于输入的任意一个非负十进制整数，输出与其等值的八进制数。
上述计算过程是从低位到高位顺序产生八进制数的各个数位；而输出过程应从高位到低位进行，恰好和计算过程相反，因而我们可以使用栈来解决这个问题。在计算过程中依次将得到的余数压入栈中，计算完毕后，再依次弹出栈中的余数就是数制转换的结果。
【案例分析】以十进制转化为八进制为例
当将一个十进制整数N转换为八进制数时，在计算过程中，把N与8求余得到的八进制数的各位依次进栈，计算完毕后将栈中 的八进制数依次出栈输出，输出结果就是待求得的八进制数。
【算法步骤】
① 初始化一个空栈S。
② 当十进制数N非零时，循环执行以下操作：
- 把N与8求余得到的八进制数压入栈S；
- N更新为N与8的商。
③ 当栈S非空时，循环执行以下操作：
- 弹出栈顶元素e；
- 输出e。
【算法描述】
void conversion(int N) { //对于任意一个非负十进制数，打印输出与其等值的八进制数 InitStack(S); //初始化空栈S while(N) //当N非零时,循环 { Push(S,N%8); //把N与8求余得到的八进制数压入栈S N=N/8; //N更新为N与8的商 } while(!StackEmpty(S)) //当栈S非空时，循环 { Pop(S,e); //弹出栈顶元素e cout<<e; //输出e } }
📝2️⃣括号匹配的检验。
【案例描述】
假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（［］（））或［(［］［］)］等为正确的格式，［（］或（［（））或（（）］）均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。
当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，显然第二个括号的期待急迫性高于第一个括号，此时第一个括号“［”只能暂时靠边，而迫切等待与第二个括号相匹配的、第七个括号“）”的出现。类似地，因等来的是第三个括号“［”，其期待匹配的程度较第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号。在接受了第四个括号之后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配就成为当前最急迫的任务了，……，依次类推。可见，这个处理过程恰与栈的特点相吻合。每读入一个括号，若是右括号，则或者使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。
【案例分析】
检验算法借助一个栈，每当读入一个左括号，则直接入栈，等待相匹配的同类右括号；每当读入一个右括号，若与当前栈顶的左括号类型相同，则二者匹配，将栈顶的左括号出栈，直到表达式扫描完毕。
在处理过程中，还要考虑括号不匹配出错的情况。例如，当出现(( )[ ]))这种情况时，由于前面入栈的左括号均已和后面出现的右括号相匹配，栈已空，因此最后扫描的右括号不能得到匹配；出现[([ ])这种错误，当表达式扫描结束时，栈中还有一个左括号没有匹配；出现(( )]这种错误显然是栈顶的左括号和最后的右括号不匹配。
【算法步骤】
① 初始化一个空栈S。
② 设置一标记性变量flag，用来标记匹配结果以控制循环及返回结果，1表示正确匹配，0表示错误匹配，flag初值为1。
③ 扫描表达式，依次读入字符ch，如果表达式没有扫描完毕或flag非零，则循环执行以下操作：
- 若ch是左括号“[”或“(”，则将其压入栈；
- 若ch是右括号“)”，则根据当前栈顶元素的值分情况考虑：若栈非空且栈顶元素是“(”，则正确匹配，否则错误匹配，flag置为0；
- 若ch是右括号“]”，则根据当前栈顶元素的值分情况考虑：若栈非空且栈顶元素是“[”，则正确匹配，否则错误匹配，flag置为0。
④ 退出循环后，如果栈空且flag值为1，则匹配成功，返回true，否则返回false。
【算法描述】
Status Matching() { //检验表达式中所含括号是否正确匹配，如果匹配，则返回true，否则返回false //表达式以“# 结束 InitStack(S); //初始化空栈 flag=1; //标记匹配结果以控制循环及返回结果 cin>>ch; //读入第一个字符 while(ch!='#'&&flag) //假设表达式以“#”结尾 { switch(ch) { case '['||'(': //若是左括号，则将其压入栈 Push(S,ch); break; case ')': //若是“)”，则根据当前栈顶元素的值分情况考虑 if(!StackEmpty(S)&&GetTop(S)=='(') Pop(S,x); //若栈非空且栈顶元素是“(”，则正确匹配 else flag=0; //若栈空或栈顶元素不是“(”，则错误失败 break; case ']': //若是“]”，则根据当前栈顶元素的值分情况考虑 if(!StackEmpty(S)&&GetTop(S)=='[') Pop(S,x); //若栈非空且栈顶元素是“[”，则正确匹配 else flag=0; //若栈空或栈顶元素不是“[”，则错误匹配 break; } //switch cin>>ch; //继续读入下一个字符 } //while if(StackEmpty(S)&&flag) return true; //匹配成功 else return false; //匹配失败 }
📝3️⃣表达式求值
【案例描述】
表达式求值是程序设计语言编译中的一个最基本问题，其实现是栈应用的又一个典型例子。“算符优先法”，是一种简单直观、广为使用的表达式求值算法。
要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。算符优先法就是根据算术四则运算规则确定的运算优先关系，实现对表达式的编译或解释执行的。
在表达式计算中先出现的运算符不一定先运算，具体运算顺序是需要通过运算符优先关系的比较，确定合适的运算时机，而运算时机的确定是可以借助栈来完成的。将扫描到的不能进行运算的运算数和运算符先分别压入运算数栈和运算符栈中，在条件满足时再分别从栈中弹出进行运算。
【案例分析】
编辑
任何一个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的，统称它们为单词。对于运算符以下给出运算符的优先级顺序。
| f1 \ f2 | + | - | * | / | ( | ) | # |
| + | > | > | < | < | < | > | > |
| - | > | > | < | < | < | > | > |
| * | > | > | > | > | < | > | > |
| / | > | > | > | > | < | > | > |
| ( | < | < | < | < | < | = | x |
| ) | > | > | > | > | x | > | > |
表中的“(”=“)”表示当左右括号相遇时，括号内的运算已经完成。为了便于实现，假设每个表达式均以“#”开始，以“#”结束。所以“#”=“#”表示整个表达式求值完毕。“)”与“(”、“#”与“)”以及“(”与“#”之间无优先关系，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出现了语法错误。在下面的讨论中，我们暂假定所输入的表达式不会出现语法错误。
【算法步骤】
① 初始化OPTR栈和OPND栈，将表达式起始符“#”压入OPTR栈。
② 扫描表达式，读入第一个字符ch，如果表达式没有扫描完毕至“#”或OPTR的栈顶元素不为“#”时，则循环执行以下操作：
- 若ch不是运算符，则压入OPND栈，读入下一字符ch；
- 若ch是运算符，则根据OPTR的栈顶元素和ch的优先级比较结果，做不同的处理：
- 若是小于，则ch压入OPTR栈，读入下一字符ch；
- 若是大于，则弹出OPTR栈顶的运算符，从OPND栈弹出两个数，进行相应运算，结果压入OPND栈；
- 若是等于，则OPTR的栈顶元素是“(”且ch是“)”，这时弹出OPTR栈顶的“(”，相当于括号匹配成功，然后读入下一字符ch。
③ OPND栈顶元素即为表达式求值结果，返回此元素。
【算法描述】
char EvaluateExpression() { //算术表达式求值的算符优先算法，设OPTR和OPND分别为运算符栈和操作数栈 InitStack(OPND); //初始化OPND栈 InitStack(OPTR); //初始化OPTR栈 Push(OPTR，'#'); //将表达式起始符“#”压入OPTR栈 cin>>ch; while(ch!='#'||GetTop(OPTR)!='#') //表达式没有扫描完毕或OPTR的栈顶元素不为“#” { if(!In(ch)) { Push(OPND,ch); cin>>ch; } //ch不是运算符则进OPND栈 else switch(Precede(GetTop(OPTR),ch)) //比较OPTR的栈顶元素和ch的优先级 { case '<': Push(OPTR,ch);cin>>ch; //当前字符ch压入OPTR栈，读入下一字符ch break; case '>': Pop(OPTR,theta); //弹出OPTR栈顶的运算符 Pop(OPND,b);Pop(OPND,a); //弹出OPND栈顶的两个运算数 Push(OPND,Operate(a,theta,b)); //将运算结果压入OPND栈 break; case '=': //OPTR的栈顶元素是“(”且ch是“)” Pop(OPTR,x);cin>>ch; //弹出OPTR栈顶的“(”，读入下一字符ch break; } //switch } //while return GetTop(OPND); //OPND栈顶元素即为表达式求值结果 }
📝4️⃣小 结
到这里栈和队列的基本内容就全部介绍完了，主要内容如下。
（1）栈是限定仅在表尾进行插入或删除的线性表，又称为后进先出的线性表。栈有两种存储表示，顺序表示（顺序栈）和链式表示（链栈）。栈的主要操作是进栈和出栈，对于顺序栈的进栈和出栈操作要注意判断栈满或栈空。
（2）队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。队列也有两种存储表示，顺序表示（循环队列）和链式表示（链队）。队列的主要操作是进队和出队，对于顺序的循环队列的进队和出队操作要注意判断队满或队空。凡是涉及队头或队尾指针的修改都要将其对MAXQSIZE求模。
（3）栈和队列是在程序设计中被广泛使用的两种数据结构，其具体的应用场景都是与其表示方法和运算规则相互联系的。表3.3分别从逻辑结构、存储结构和运算规则3方面对二者进行了比较。（4）栈有一个重要应用是在程序设计语言中实现递归。递归是程序设计中最为重要的方法之一，递归程序结构清晰，形式简洁。但递归程序在执行时需要系统提供隐式的工作栈来保存调用过程中的参数、局部变量和返回地址，因此递归程序占用内存空间较多，运行效率较低。
