和出栈的类似问题很多，
关于出栈可能顺序种类的讨论(参考了大佬的算法嘻嘻),
输入一个数n，输出n个数出栈的可能顺序种类：
这个问题可以用递归公式。
首先我们考虑n=4时，a,b,c,d： //f(4)
a第一个出栈，只能是a先进去然后立即出来，剩下b,c,d即f(1)f(3)种。
a第二个出栈，只能是b先出，然后a出，剩下c,d即f(2)种。
a第三个出栈，b,c比a先出，有f(2)种。
a第四个出栈，b,c,d即f(3)种。
则f(4)=f(3)+f(1)f(2)+f(2)f(1)+f(3)。
f(n)=f(n-1)+f(1)f(n-2)+f(2)f(n-3)…f(n-3)f(2)+f(n-2)f(1)+f(n-1)。
上面的公式两角加上f(0)， i=0
便可以总结为f(n)= ∑ f(i)f(n-i-1)。
n-1

注意f(0)等于1，这样不改变任何值。
代码实现©：
#include<stdio.h>
int Stacksqcount(int n){
if(n==0) return 1;
int ans=0;
for(int i=0;i<n;i++){
ans+=Stacksqcount(i)*Stacksqcount(n-1-i);
}
return ans;
}
int main(){
while(1){
int ch;
scanf("%d",&ch);
printf("%d\n",Stacksqcount(ch));
}
return 0;
}

  • n个数据依次进入栈中，出栈的种类有