【数据结构】出栈序列的合法性【面试】-创新互联-成都创新互联网站建设

关于创新互联

多方位宣传企业产品与服务 突出企业形象

公司简介 公司的服务 荣誉资质 新闻动态 联系我们

【数据结构】出栈序列的合法性【面试】-创新互联

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

成都创新互联主要从事网站设计、成都网站制作、网页设计、企业做网站、公司建网站等业务。立足成都服务天山,十多年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18980820575

有一组元素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;
}

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

创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。


本文题目:【数据结构】出栈序列的合法性【面试】-创新互联
标题URL:http://kswsj.cn/article/jhsec.html

其他资讯