栈混洗

佚名 7年前 (2019-04-11) 随笔 1911人围观抢沙发百度已收录

栈混洗的概念

A中的元素经S的中转后压入B中，其间，只允许从A弹出压入S或者从S弹出压入B，A中元素全部转移到B中即完成一次栈混洗操作
SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

栈混洗的甄别

对于这个问题主要就是模拟一次栈混洗来解决，即每次S.pop()之前检测S是否已空，或需要弹出的元素在S中却不是顶元素

代码实现

#include "../head.h"
#include <stack>

bool stackPermutation(stack<int> &A, stack<int> &B) {
    stack<int> S, temp;
    while (!B.empty()) {
        temp.push(B.top());
        B.pop();
    }
    while (!A.empty()) {
        S.push(A.top());
        A.pop();
        if (temp.top() == S.top()) {
            temp.pop();
            S.pop();
            while (!S.empty()) {
                if (temp.top() == S.top()) {
                    temp.pop();
                    S.pop();
                }
                else return false;
            }
        }
    }
    return S.empty();
}


int main(int argc, char** argv) {
    stack<int> a, b;
    int ta, tb;
    cout << "the base stack [--->: [";
    while (cin >> ta)
        a.push(ta);
    if (cin.eof())
        cout << "endoffile";
    cin.clear();
    cout << endl;
    cout << "the test stack [--->: [";
    while (cin >> tb)
        b.push(tb);
    if (stackPermutation(a, b)) 
        cout << "true" << endl;
    else cout << "false" << endl;
    return 0;
}

stackPermutation()函数的逻辑是先将待测试栈B一个个弹出到一个临时栈temp中，此时temp的栈顶就是原来B的栈底，这样就可以比较容易的来模拟一次栈混洗（因为标准库的栈容器没有下标运算符，只能出此下策），接下来以A非空为判断标准，一次一个的将元素弹出并压入S中，然后把temp的栈顶元素与刚压入S的元素（刚压入嘛，肯定是栈顶）相比较，如果相同，temp与S同时弹出这个相同的元素，接下来如果S是非空，则说明接下来S的每个元素与temp的元素相同且一一对应，所以接下来以S非空为判断标准，比较一次，弹出一次，一旦有不相等，则说明待测试栈不是给定栈的栈混洗，返回false，还有一种十分特殊的情况，如果B的栈底元素（也就是temp的栈顶元素）在A中根本就没有，即使A全部弹出，也不会触发循环里面的return false，所以，最后要用S是否为空作为判断依据返回