Description

在PushPop城中有一个著名的火车站，车站铁路如图所示。

每辆火车都从A方向驶入车站，再从B方向驶出车站，同时它的车厢可以进行某种形式的重新组合。假设从A方向驶来的火车有N节车厢（N≤1000），分别按顺序编号为1，2，…，N。负责车厢调度的工作人员需要知道能否使它以A1，A2，…，An的顺序从B方向驶出。

请你编写程序，用来判断能否得到指定的车厢顺序。假定在进入车站之前每节车厢之间都是不连着的，并且它们可以自行移动，直到处在B方向的铁轨上。另外假定车站可以停放任意多的车厢。但是一旦车厢进入车站，它就不能再回到A方向的铁轨上了，并且一旦它驶入B方向的铁轨后，它就不能再回到车站。

Input

第1行输入N，接下来的一行是任意多个的出站重组顺序（A1，A2，…，），以0为结束标志，用空格分隔。

Output

输出Yes表示可以把火车（1，2，…，N）火车编排成所需要的顺序（A1，A2，…，），否则用No表示。

Sample Input 

5

1 2 3 4 5 0

Sample Output

Yes

 

 

正好是栈的简单应用，a，b代替两个站进出火车的编号，target[]保存出站顺序

1 //栈的特点是先进后出 2 /*1-n进站，能否按给定顺序出站 3 */ 4 #include
     
       5 #include
      
        6 #include
       
         7 using namespace std; 8 const int MAX=1000+10; 9 int n;10 int target[MAX];11 int main()12 {13     while(scanf("%d",&n)==1)14     {15         stack
        
         s;16         int a=1;17         int b=1;18         for(int i=1;i<=n;i++) cin>>target[i];19         int ok=1;20         while(b<=n)21         {22             if(a==target[b]){a++;b++;}23             else if(!s.empty()&&s.top()==target[b]){s.pop();b++;}24             else if(a<=n) s.push(a++);25             else{ok=0;break;}26         }27         printf("%s\n",ok?"Yes":"No");28     }29     return 0;30 }