【数据结构与算法】第八章：栈与队列相关应用

 📖【数据结构与算法】第八章：栈与队列相关应用

📝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; //匹配失败
}