火车编号为：1~9，且不重复。
如：编号分别为“1”、“2”、“3”、“4”、“5”的5个火车顺序进站，那么进站序列为“12345”，全部进站后再顺序出站，则出站序列为“54321”，如果先进1,2，然后2出站，然后1出站，然后再3进站、出站，4进站、出站，5进站、出站，那么出站序列就为21345.
问题分析：
栈具有先进后出、后进先出的特点，因此，任何一个调度结果应该是1 ，2 ，3 ，4全排列中的一个元素。由于进栈的顺序是由小到大的，所以出栈序列应该满足以下条件：对于序列中任何一个数其后面所有比它小的数应该是倒序的.例如4321是一个有效的出栈序列，1423不是一个有效的出栈结果（4 后面比它小的两个数 2 ，3 不是倒序）。
主要有两种算法：
第一种计算出全排列，然后筛选出不符合条件的，例如, 这种算法简单粗暴，如果要求按照全排列顺序输出，有可能还需要重新排序，效率太低。第二种采用递归的方式，状态转移方程比较简单，难点主要在于如何去存储状态。
我们只考虑还在原始火车序列和火车站中的序列，该序列要么直接把尾部火车出站，此时车站中火车减1，原始序列不变；要么再来一列之前没有的火车，此时原始火车序列当前出的火车序号加1。也就是：
dispatch(fPos,tPos) = dispatch(fPos+1,tPos) + dispatch(fPos,tPos-1)
终止条件就是：fPos达到最后一个并且火车站中火车全部出站。
注意的是我们的递归函数尽量不要去涉及状态，状态由外部保存的话就不用每次传递状态，这样会浪费内存。
那么难点就在如何存储于回溯状态！
我们采用list来存储出站的火车序列，如果直接用数组记录的话会很浪费空间，例如;如果采用栈来存储的话，每次得到一个序列后都需要弹栈来输出序列，压栈来恢复状态，效率也很低，例如。
好了，话不多少，上代码。
#include <stack>#include <list>using namespace std;int total=0; //记录出站的可能数目int SIZE; //输入几列火车list<int> output; //采用list来存储结果序列，如果采用copy方式保存，那么每次都复制会浪费内存；//如果用栈的话每次结束需要弹栈再压栈，也不划算，上面已经讲过stack<int> to; //存储当前火车站的序列void dispatch(int *from,int fPos,int tPos){//fPos火车出到第几列,tPos火车站的火车还有几列if(fPos == SIZE && tPos ==0){ //终止total++;list<int>::iterator it;for(it=output.begin();it!=output.end();it++){cout<<*it;}cout<<endl;return;}if(!to.empty()){ //我们先让当前列直接出，这样最终的顺序是从小到大的排列int popped = to.top();to.pop();output.push_back(popped);dispatch(from,fPos,tPos-1); //从火车站开出去一列output.pop_back();//保证回溯的结果序列回到之前状态to.push(popped);}if(fPos<SIZE){int tmp = from[fPos];to.push(tmp);dispatch(from,fPos+1,tPos+1);//火车站进来一辆火车to.pop();}}int main(){cout<<"please input total size of the train"<<endl;while(SIZE<=0){cout<<"请输入大于0的整数"<<endl;cin>>SIZE;}int arr[SIZE]; //初始的火车序列for(int i=0;i<SIZE;i++){arr[i] = i+1;}dispatch(arr,0,0);printf("共有%d种出站顺序\n",total );return 0;};复制代码
