题目

数据结构与算法,老师的题目难做啊,
设有编号为1,2,3,4的四辆车,顺序进入一个栈式结构的站台,试写出四辆车开出车站的所有可能的顺序.

提问时间：2021-04-01

答案

4 3 2 1 , 1 2 3 4, 2 3 4 1, 3 4 2 1, 2 1 3 4, 2 1 4 3, 3 2 1 4, 3 2 4 1, 2 4 3 1, 1 4 3 2 , 1 3 2 4, 1 3 4 2 1 2 4 3
#define N 4
int m=0,a=0,b=N;/*m表示种数,a表示栈中元素个数,b表示外面还有需要进栈的个数*/
main()
{
inS(a,b);/*首先入栈*/
printf("%d",m);
getch();
}
int inS(int a,int b)/*入栈*/
{
a++;b--;/*入栈栈中元素+1,栈外元素-1 */
if(b>0)/*若栈外有元素,可以入栈*/
inS(a,b);
if(a>0)/*若栈中有元素,可以出栈*/
outS(a,b);
}
int outS(int a,int b)/*出栈*/
{
a--;/*出栈栈中元素-1*/
if(a==0&&b==0)/*若栈中元素和栈外元素都为0个*/
{
m++;/*则此种情况的序列满足条件,种数+1*/
return;
}
if(b>0)
inS(a,b);
if(a>0)
outS(a,b);
}