出栈的合法顺序

（这是一篇水贴）

在把1到n这n个数依次入栈的情况下，如何判断出栈的顺序是否合法？

如果仅仅要求顺序合法，我们可以在已经得到了一个出栈序列的情况下，以如下的方式判断。

int A=1,B=1;
stack s;
while(A<=n){
      if(a[A]==B){
            A++;B++;
      }
      else if(!s.empty()&&s.top()==a[A]){
            s.pop();
            A++;
      }
      else if(B<=n){
            s.push(B++);
      }
      else {
            break;//不合法
      }
}

我们可以以生成全排列的方法，借用这种判断方式来暴力求出合理的出栈顺序的数量。（当然，可以数论直接求解）

也可以直接高效生成(以下代码来自SE大佬)：

inline void dfs(int s) {
      if(cnt == n) {
      num++;
      /* 
      for (int i = 1;i <= n; ++i) printf("%d", c[i]);  
      printf("\n");  
      */  
      return;  
  }
  if (top > 0) {
      int tp = a[top--];  
      c[++cnt] = tp;  
      dfs(s);  
      a[++top] = tp;
      cnt--;   
  }
  if (s <= n) { 
      a[++top] = s;  
      dfs(s+1);  
      top--;  
   }  
 }  
  int main(){  
      scanf("%d", &n);  
      dfs(1); 
      printf("%d", num);  
      return 0;  
  }