题目描述：
给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。
要求输出所有火车出站的方案，以字典序排序输出。
输入描述：
有多组测试用例，每一组第一行输入一个正整数N
输出描述：
输出以字典序从小到大排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见sample。
示例：
输入：
3
1 2 3
输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
说明：
第一种方案：1进、1出、2进、2出、3进、3出
第二种方案：1进、1出、2进、3进、3出、2出
第三种方案：1进、2进、2出、1出、3进、3出
第四种方案：1进、2进、2出、3进、3出、1出
第五种方案：1进、2进、3进、3出、2出、1出
请注意，[3,1,2]这个序列是不可能实现的。
解题思路：
本题是入栈出栈问题。用队列in存放火车入站的顺序，用out存放出站的顺序，用stack栈模仿入站出站操作；solve函数是递归求解函数，当bool为true时表示入站，为false表示出站；入站则将in弹出一个数据，stack存放一个数据，出站则stack弹出，out存放，出站先判断栈内有无数据，无数据直接返回；递归操作，进行一次出站再进行一次入站；当in队列空了则说明火车全部进站完毕，此时若还进站则直接返回，若栈内还有数据则依次弹出；用write_result函数记录out的结果，格式如1 2 3；递归全部完成则表示所有可能的情况都遍历过了；因为题目要求结果按字典排序，用sort排序后输出即可。
测试代码：
#include <iostream> #include <vector> #include <queue> #include <stack> #include <algorithm> using namespace std; vector<string> result; // 写入结果 void write_result(queue<int> q) { string str; while(!q.empty()) { str+=to_string(q.front()); str+=' '; q.pop(); } result.push_back(str); } // 递归求解 void solve(queue<int> in,stack<int> t,queue<int> out,bool flag) { if(in.empty()) // in队列空了就说明都进完了 { if(flag) // in队列空了不能再进了 return; while(!t.empty()) // 栈里若还有数据直接弹出到out队列里 { out.push(t.top()); t.pop(); } write_result(out); // 记录本次结果 return; } else{ if(flag) // 入栈 { t.push(in.front()); in.pop(); } else{ // 出栈 if(t.empty()) // 没得出直接返回 return; out.push(t.top()); t.pop(); } // 递归 solve(in,t,out,false); solve(in,t,out,true); } } int main() { int num; while(cin>>num) { int sequence; queue<int> in,out; stack<int> t; for(int i=0;i<num;++i) { cin>>sequence; in.push(sequence); } solve(in,t,out,true); // 按字典顺序排序结果 sort(result.begin(),result.end()); for(auto it=result.begin();it!=result.end();++it) { cout<<*it<<endl; } result.clear(); } return 0; }
