POJ 1363 Rails

题意：就是1...N的数按顺序入栈，看给定的输入是否是合法的出栈顺序，只要模拟就可以了。

思路：按照给出的出栈顺序,一个一个和和当前栈顶的元素比较,不相等就向当前栈压入一个元素,因为是按照顺序压栈的,所以总会找到一个当前给出的顺序所在位置值一样的栈顶元素,然后出栈。同时给出的元素顺序也后移一位直到给出的顺序遍历完或者出错。
输入：

5 //5个数入栈
1 2 3 4 5 //出栈顺序
5 4 1 2 3 //出栈顺序
0 //5个数的结束
6 //6个数的入栈
6 5 4 3 2 1
0 //6个数的结束
0 //输入结束

题目链接http://poj.org/problem?id=1363

View Code

 1 #include <stdio.h>
 2 int max=1010;
 3 int n,t[1010];
 4 int main()
 5 {
 6 
 7     while(scanf("%d",&n)&&n!=0)
 8     {
 9 
10         while(scanf("%d",&t[1])&&t[1]!=0)
11         {
12             int stack[max],top=0;
13             int a=1,b=1,i;
14             for(i=2;i<=n;i++)
15             scanf("%d",&t[i]);
16             int ok=1;
17         while(b<n)
18         {
19             if(a==t[b])
20             {
21                 a++;b++;
22             }
23             else if(top&&stack[top]==t[b])
24             {
25                 top--;
26                 b++;
27             }
28             else if(a<=n)
29             {
30                 stack[++top]=a++;
31             }
32             else
33             {
34                 ok=0;break;
35             }
36         }
37         printf("%s\n",ok?"Yes":"No");
38         }
39         printf("\n");
40 
41     }
42     return 0;
43 }