http://poj.org/problem?id=1363
数据结构 栈
用2个栈模拟，复杂度O(n) (每个元素最多进栈(s2)一次，出栈一次)
s1弹出的元素压入s2，s2再弹出来一定要按照顺序n,n-1,n-2...4,3,2,1
想办法让s2按此顺序弹出，如果不能，则输出"No"
1 #include <stdio.h>
2 #include <stack>
3
4 using namespace std;
5
6 stack<int> s1, s2;
7
8 void clear()
9 {
10 while(!s1.empty())
11 {
12 s1.pop();
13 }
14 while(!s2.empty())
15 {
16 s2.pop();
17 }
18 }
19
20 int main()
21 {
22 int n, cases, i, a;
23 for(cases=1; scanf("%d", &n), n; cases++)
24 {
25 if(cases-1)
26 {
27 printf("\n");
28 }
29 while(scanf("%d", &a), a)
30 {
31 clear();
32 s1.push(a);
33 for(i=1; i<n; i++)
34 {
35 scanf("%d", &a);
36 s1.push(a);
37 }
38 for(i=n; i>=1;)
39 {
40 if(!s2.empty() && s2.top()==i)
41 {
42 s2.pop();
43 i --;
44 continue;
45 }
46 if(s1.empty())
47 {
48 i = -1;
49 break;
50 }
51 else
52 {
53 s2.push(s1.top());
54 s1.pop();
55 }
56 }
57 printf(i+1? "Yes\n": "No\n");
58 }
59 }
60 return 0;
61 }