铁轨（Rails，UVa 514)

题目描述：
某城市有一个火车站，铁轨铺设如下图所示。有n节车厢从A方向驶入车站，按进站顺序编号为1~n。你的任务是判断是否能让他们按照某种特定的顺序进入B方向的铁轨并驶出车站。例如，出站顺序（5 4 1 2 3）是不可能的，但（5 4 3 2 1）是可能的。为了重组车厢，你可以借助中转站C。这是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入C的车厢必须按照相反的顺序驶出C。对于每个车厢，一旦从A移出就不能再返回到A了；一旦从C移入B，就不能再回到C了。换句话说，在任意时刻，只有两种选择：A->C和C->B.

样例输入:
5
5 4 1 2 3
5
5 4 3 2 1
样例输出:
NO
YES

分析：
先进的列车后出，可以借助栈来解决，先用一个target数组来存储将要验证的进入B的顺序，从A出来的列车顺序是固定的即1~n，从A出来的要么先存在C中，要么直接进入B，我们可以假想B有一个守卫拿着一份顺序单只让按照先后顺序的列车进去。此题是数据结构栈当中的一道经典题目。
代码如下：

//铁轨 UVa 514
#include <iostream>
#include <cstdio>
#include <stack>


#define MAXN 1010


using namespace std;


int n;
int target[MAXN];//存储将要验证的顺序

int main()
{
    while(scanf("%d",&n)==1){
        stack<int>s ;
        for(int i=1;i<n;i++)
            scanf("%d",&target[i]);
        int A=1,B=1;//A是指当前从A方向驶入C的列车的序号，B是指需验证的顺序中第B个列车的序号
        int ok=1; //标记是否该顺序可以实现
        while(B<=n){
            if(A==target[B]){   //A号列车从A进入C后直接进入B
                A++;
                B++;
            }
            else if(!s.empty()&&s.top()==target[B]){ //C当中的最上面的列车是需验证的顺序中的第B个列车
                s.pop(); //C中列车进入B
                B++; //判断下一个进入B的列车
            }
            else if(A<=n){ //A中出去的列车数少于等于n，并且当前从A进入C的列车先在C中待着
                s.push(A++); //该列车先压到C中
            }
            else{        //A中的列车全部出去了还是不能够让下一个应当进入B的列车进入B
                ok=0;
                break;
            }


        }
        printf("%s\n",ok?"YES":"NO");
        return 0;
    }
}