出栈序列问题归纳
最近温习数据结构方面的一些知识，遇到了很多关于出栈序列的问题。
大致就是已知元素的入栈序列，然后求出出栈序列。比如入栈为1,2,3,...n,然后求出可能的出栈序列数目，以及判断是否为正确的出栈序列。
下面就是我遇到的两个问题：
宁宁考虑的是这样一个问题：一个操作数序列，从1，2，一直到n，栈A的深度大于n。
现在可以进行两种操作：
1.将一个数，从操作数序列的头端移动到栈的头端（对应数据结构栈的push操作）
2.将一个数，从栈的头端移动到输出序列的尾端（对应数据结构的pop操作）
使用这2个操作，由一个操作数序列就可以得到一系列的输出序列，下面为由1 2 3 到 2 3 1 的过程：
操作数：1 2 3
栈：
输出端：
操作数：2 3
栈：1（栈底）
输出端：
操作数：3
栈：2 1（栈底）
输出端：
操作数：3
栈：1（栈底）
输出端：2
操作数：
栈：3 1（栈底）
输出端：2
操作数：
栈：1（栈底）
输出端：2 3
操作数：
栈：
输出端：2 3 1
现在对于任意一个N，输入端的数据一定是1，2，3...N
对于任意一个序列，请问是否能根据规则产生这样的序列；
输入第一行包含一个整数 n(n <= 1000)，表示数列长度，第二行包含n个数a1，a2，…，an, 表示期望顺序。(a1，a2，…，an) ∈ Permutation{1, 2, …, n}
输出
如果可以满足，输出 Yes，否则输出No。
样例输入5
1 2 3 5 4样例输出
Yes
这题解题思想就是，位于出栈序列 i 的元素A[i]，i位置之后的元素，若存在小于A[i]的元素必须是降序排列，否则错误。
#include "stdio.h"int sum;void dfs(int top,int head,int n){if(head==n+1){sum++;return;}if(top>0){dfs(top-1,head,n); /*未出过栈 ，则出栈*/}if(head<n+1){dfs(top+1,head+1,n); /*未入过栈，则入栈*/}}int main(){int testCase;int n;scanf("%d",&testCase);while(testCase--){scanf("%d",&n);sum=0;dfs(0,1,n);printf("%d\n",sum);}return 0;}