学步园

题意:

 n辆火车按顺序依次进站 判断给定的出站顺序是否可能

Sample Input

5

1 2 3 4 5

5 4 1 2 3

0

6

6 5 4 3 2 1

0

0

Sample Output

Yes

No

Yes

STL stack的操作：
empty() 堆栈为空则返回真
pop() 移除栈顶元素
push() 在栈顶增加元素
size() 返回栈中元素数目
top() 返回栈顶元素

#include <cstdio>
#include <stack>
using namespace std;
const int MAXN =1000 + 10;
int n, target[MAXN];
/*
target : 出站序列
s      ：站内车厢序列
A      ：要入站d的车厢号 A=A[i]
B      ：出站车厢号 target[B]
*/
int main()
{
    while(scanf("%d",&n) == 1&&n > 0) {
        stack<int> s;
        while(scanf("%d", &target[1]) == 1 && target[1] != 0) {
            int A = 1, B = 1;
            for(int i = 2; i <= n; i++)
                scanf("%d", &target[i]);
            int ok = 1;
            while(B <= n) {
                if(A == target[B]) {A++; B++;}
                else  if(! s.empty() && s.top() == target[B]) {s.pop();B++;}
                else if(A <= n) s.push(A++);
                else {ok = 0; break;}
/*
三种情况：1)当前要入站的车厢即为当前要出站的车厢
          2)如果站内还有车厢且栈顶元素恰好为当前要出站的车厢
          3)当前要入站的车厢进站
          4)则无法达到要求
*/
            }
            printf("%s\n", ok ? "Yes": "No");
        }
        printf("\n");
    }
    return 0;
}