算法竞赛入门经典第六章(例题) B - Rails（涉及到栈的运用）

题目：B - Rails

原题链接：https://cn.vjudge.net/contest...；

题目大意：先输入一个表示火车的节数，火车原本是按从1到n的顺序，但是一起进的还是分开进的是不一定的。之后输入自己的出站顺序，如果这个顺序可以实现，则输出yes，不能实现则输出no；

思路：利用栈的操作，即先将自己输入的第一个往后依次，先判断栈顶是否为空，如果为空，则从没用进入栈的火车头开始找，如果小于这个要找的元素，则进展，如果大于，则结束寻找，找完之后再判断其栈顶和自己找的是否一样（注意进栈的火车节不允许退出去），如果不为空则判断其栈顶是否一样，如果栈顶一样，则再从火车头中找比这个元素小的或者等于的入栈，最后比这个要找的元素小的或者等于全入栈之后，在判断其栈顶是否和要找的这个元素相同；（中间有些地方能直接判断不成立的，则可以直接退出）

代码：

#include<stdio.h>
#include<string.h>

int my_size=0;
int mystack[1010];
int main()
{
    int N;
    int a[1005],tag=0,temp=1,index;
    while(scanf("%d",&N)!=EOF&&N!=0)
    {
    while(1)
    {
        my_size=0;tag=0;temp=1;
        scanf("%d",&a[0]);
        if(a[0]==0)
            break;
        index=1;
        for(int i=1;i<N;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<N;i++)
        {
            if(my_size==0)
            {
                if(index==a[i])
                {
                    index++;
                    continue;
                }
                while(index<a[i])
                {
                    mystack[tag++]=index++;my_size++;
                    }
                if(index>a[i])
                    temp=0;
                index++;
            }
            else
            {
                while(index<=N&&mystack[my_size-1]!=a[i])
                {
                    mystack[tag++]=index++;
                    my_size++;
                }
                if(mystack[my_size-1]!=a[i])
                {
                    temp=0;}
                else
                {my_size--;tag--;}
            }
            if(temp==0)
                break;
        }
        if(temp)
            printf("Yes\n");
        else
            printf("No\n");
    }
    printf("\n");
    }
    return 0;
}