序列元素IT面试题——判断合法出栈序列

本文纯属个人见解，是对前面学习的总结，如有描述不正确的地方还请高手指正~

    在技巧笔试口试上，我们常常会碰到这样一类题型，如给你一个入栈序列，然后再让你判断几个序列是否有可能为它的出栈序列，如：

    入栈序列为 1 2 3 4 5，则 1 2 3 4 5可能为它的出栈序列，而 5 4 1 2 3弗成能为它的出栈序列。

    对于n比较小的情况，我们往往可以通过手动模拟的方法来判断，对于n比较大的时候，这种方法就显得效率不佳了。

    下面分析一种通用的方法判断正当出栈序列，时间复杂度为O(n)。为了叙说便利，我们不妨设入栈序列为 1 2 3.......n，并且每一个元素各不相等。

    事实上，一个出栈序列固定的话，那么没个数的出栈顺序和时间都是固定的，则我们可以模拟栈的入栈出栈过程，来判断是否一个正当的出栈序列。

    我们首先设po为目前为止入栈的元素中最大的数，初始化为0，若下一个出栈元素要大于po的话（设为x），说明我必须将[po+1,x]中的全部书都入栈，再将x弹出便可（这时还应把po赋值为x）。否则说明下一个出栈的元素已经在栈中，并且肯定是栈顶元素，若栈顶元素与下一个出栈元素不相等的话，我们可以判断这不是一个正当出栈序列，否则，若全部的出栈元素都不引起冲突，则说明这是一个正当序列。这里再说一下时间复杂度，因为我们只有在下一个出栈元素大于po时，才将元素压入栈中，并且我们每一次判断一个出栈元素是否发生冲突时，都会将栈顶元素弹出，所以每一个元素都入栈一次，出栈一次，所以时间复杂度为O(n)。

    每日一道理
灯，带有一种明亮的光，每当深夜来临，是它陪伴着你，如此默默无闻。它是平凡的，外表华丽与否，那都是一样的，珍珠点缀，水晶加饰的灯它只能用以装饰，来满足人们的虚荣心，比起这，普普通通的日光灯是幸运的，因为它照明的本性没有改变，如同生活中的一部分人平平凡凡却实实在在。

    算法的具体实现请看代码。

    

    代码如下：

#include <stdio.h>
#define maxn 1005
int stack[maxn],top;
int out[maxn];
int check(int n)
{
    int po=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=po+1;j<=out[i];j++)
        {
            po=j;
            stack[top++]=j;
        }
        if(stack[--top]!=out[i])
        return 0;
    }
    return 1;
}
int main()
{
    int n;
    scanf("%d",&n);//假设入栈序列为1 2。。。。n
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&out[i]);
    }
    if(check(n))
    printf("Yes\n");
    else
    printf("No\n");
    return 0;
}

    

文章结束给大家分享下程序员的一些笑话语录： 3G普不普及现在已经不是看终端了，而是看应用，有好的，便宜实用的应用，花1000多买个能用的智能手机应该不是什么难事。反过来说，你200元拿一个智能手机，没有好的应用，看个电影要几十元，也是没人用3G。