【数据结构】出栈序列的合法性【面试】

之前我们对栈已经有所了解，先进后出，后进先出这是栈的两大特性，那么，我们经常会碰到这种题，例：

双湖网站制作公司哪家好，找成都创新互联公司！从网页设计、网站建设、微信开发、APP开发、自适应网站建设等网站项目制作，到程序开发，运营维护。成都创新互联公司从2013年成立到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选成都创新互联公司。

有一组元素abcdef，按先后顺序进栈，那么出栈时哪些情况是非法的？

A.   fedcba

B.   abdcef

C.   acbdef

D.   abcdef

选哪个呢？？？

很明显，根据栈的两大特性：先进后出，后进先出，即可判断，答案：C

剖析： 先看C选项acb这样的出栈序列，那么进栈肯定是abc，那么显然出栈时c肯定不会在b之前，就这么简单。用代码实现这个合法性的判断，当然也是比较容易的，只要思路逻辑清楚，就没有问题。

代码如下：

#include 
#include 
#include 
using namespace std;

bool isLegalSequence(const char* Push_seq,const char* Pop_seq)
{
    assert(Push_seq);
    assert(Pop_seq);

    //判断出入栈序列长度是否相等
    if ( strlen(Push_seq) != strlen(Pop_seq) ) 
        return false;

    stack stk;
    while ( *Push_seq)
    {
        // 先判断栈是否为空，然后判断栈顶元素是否和出栈序列的元素相同
        if (0 == stk.size() || stk.top() != *Pop_seq)
        {
            stk.push(*Push_seq++); // 不相同就压栈，继续向后找
        }
        else
        {
            stk.pop(); //找到相同的，出栈
            ++Pop_seq; //跳到出栈序列的下一个元素验证
        }
    }

    while (stk.size()) // 将剩余的出栈序列元素判断
    {
        if (stk.top() != *Pop_seq)
        {
            return false;
        }
        stk.pop();
    }

    return true;
}

int main()
{
    char* str1 = "abcdef";
    char* str2 = "baedcf";
    cout << ( isLegalSequence(str1, str2) ? "yes" : "no" ) << endl;

    system("pause");
    return 0;
}

由于系统的栈是现成的，我们可以直接拿来使用，这样问题大大简化，具体的实现步骤过程，代码中也有注释，简单易懂。