#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include "Stack.h"


/*最后一個車廂的號碼*/
long total=0;/*總的組合方案數目*/
int end;

Status Stack_Full(SqStack s)
{
	if(s.top-s.base==end)
		return 1;
	return 0;
}
void Stack_printreverse(SqStack s)
{
     SElemType *po;
     po=s.base;
	 printf("\t[%ld]:   ",total);
	 for(;po!=s.top;) 
		 printf("%d ",*po++);
	 printf("\n");
}

/*---------------核心算法----------------*/
void search(SqStack &inputp,SqStack &tempp,SqStack &outputp)
{  
	if(!StackEmpty(inputp))
	{
		Push(tempp,Pop(inputp));
		search(inputp,tempp,outputp);
		Push(inputp,Pop(tempp));
	}
	if(!StackEmpty(tempp))
	{
		Push(outputp,Pop(tempp));
		search(inputp,tempp,outputp);
		Push(tempp,Pop(outputp));
	}
	if(Stack_Full(outputp))
	{
		total++;
		Stack_printreverse(outputp);
	}
}
/*--------------核心算法結束---------------*/


/*----------------主程序-------------------*/
void main()
{
	SqStack input,temp,output;
	int i;
	printf("車廂調度\n");

	printf("\n 請輸入車廂的長度：\n");
	scanf("%d",&end);
	/*初始化三個棧*/
	InitStack(input);
	input.stacksize=end;
	InitStack(temp);
	temp.stacksize = end;
	InitStack(output);
	output.stacksize = end ;

	/*將車廂號碼進棧*/
	for(i=end;i>=1;i--)
	Push(input,i);
	search(input,temp,output);
	printf("\n\t\t總的組合數目為:%ld\n",total);
	
}