📖【数据结构与算法】第八章：栈与队列相关应用
📝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; //匹配失败 }
