以下3个排列是否能由排列1 2 3 4 5出入站得到，能即为合法，否则为不合法
1 3 2 5 4
1 5 3 2 4
1 3 4 2 5

在这一节，我们要动手解决火车出入站的问题。 首先，我们来对问题进行抽象。抽象是我们在今后解题过程中常用的技能，指的是把一个实际的问题转换成我们学过的的问题。

给定 n 个数的排列 a 和一个栈，n 个值的入栈顺序为 1,2,⋯n，判断出栈顺序是否可以是排列 a。下面代码已经帮我们输入了一个整数 n，并将接下来的 n 个整数，用一个vector来存储。

1. 这里用到了vector，不要忘记了在#include <iostream>下面加上vector对应的头文件：

#include <vector>

我们用一个栈s来记录当前栈的信息，初始的时候栈为空。  

第一个出栈的元素是 a[0]，由于我们规定了进栈顺序，所以我们必须依次把 1 到 a[0] 这些元素压入到栈中，然后让 a[0] 出栈。  
接下来，对于第二个出栈的元素 a[1]，由于我们只能对栈顶进行操作，如果当前栈顶元素不等于 a[1]，我们就必须接着往栈中压入元素，直到找到了 a[1]，然后把 a[1] 这个元素pop掉。如果所有元素都已经被压入栈中，都不能让 a[1] 正确地出栈，说明这组出栈序列是不合法的。  

之后对于 a[2]，采用类似 a[1]的方法进行处理，以此类推。  

你应该已经发现，对每个元素的处理逻辑都是一样。  
根据上面的思路，我们开始实现算法部分的代码。

2. 定义一个栈 s 以及一个用来记录位置的变量 cur，这个 cur 变量用来记录当前还没有压入栈中的元素的起始位置，也就是说 1 到 cur-1 都已经进过栈了。然后定义一个用来记录当前出栈序列是否合法的变量 f。 在main函数里面继续写下：

   stack<int> s; 
   int cur = 1;  // s.push(cur); cur++;
   bool f = 1; 
   

   不要忘记在#include <vector>之后加上头文件：

   #include <stack>

3. 按照我们算法的思路，现在我们需要从第一个需要出栈的元素开始，依次进行模拟。对于枚举的 i 个 a[i]，如果栈顶不等于a[i]，就一直向栈顶push元素。

先在上一步写下的代码后面继续写下

for (int i = 0; i < n; i++) { 
    while (s.top() != a[i]) { 
        s.push(cur); 
        cur++; 
    } 
  
}

4. 仔细分析发现，上面的代码虽然逻辑上是正确的，但是还存很多缺陷。

如果 s 为空，s.top()会出现错误，程序会因此而异常中止。一定要记住，访问栈之前一定要确保栈不为空。对于目前写出的代码，我们可以改成while (s.empty() || s.top() != a[i])，注意s.top() != a[i]一定要在s.empty()后面，因为如果s.empty()为真，那么后面s.top() != a[i]就不会再计算了，所以就不会出现错误。

当 a[i] 很小的时候，cur 一直增加也不可能满足s.top() == a[i]，这个循环会一直跑下去，实际上这时候就是不合法的情况了。所以我们必须限制cur <= n，那么现在，while后面的判断需要改成

while ((s.empty() || s.top() != a[i]) && cur <= n)

注意运算符优先级的问题，一定要在前面的||运算式两边加上括号哦。

改完以后，刚才的代码应该变成下面这样了：

for (int i = 0; i < n; i++) { 
    while ((s.empty() || s.top() != a[i]) && cur <= n) { 
        s.push(cur); 
        cur++; 
    } 
  
}

5. 这时候，如果仍然s.top() != a[i]，那么说明这个顺序是不可能的。在while循环外面继续写

   if (s.empty()||s.top()!=a[i]){
       f=0;
       break;
   }else{
       s.pop();
   }
   

注意，上面的代码在访问栈之前同样还是要判断一下是否空。break是因为一旦出现了不合法的情况，后面的就都不用判断了，我们也就不用进行后面的计算了。

6. 最后，我们输出一下结果，在main函数里面的for循环下面写下：

   if (f) { 
       cout << "legal" << endl; 
   } else { 
       cout << "illegal" << endl; 
   }
   

这一节已经完成，运行以后分别输入下面两组数据试试吧。

5 
1 3 2 5 4  

5 
1 5 3 2 4