题解 | 火车进站

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

void dfs(queue<int> a, stack<int> s, vector<int> order, vector<vector<int>>& res){
    //终止条件,a和s都空
    if(a.empty() && s.empty()){
        res.push_back(order);
        return;
    }
    //栈s空，从a中弹出元素入栈s，继续dfs
    else if(s.empty()){
        int t = a.front();
        a.pop();
        s.push(t);
        dfs(a, s, order, res);
    }
    //a空，出栈，继续dfs
    else if(a.empty()){
        int t = s.top();
        order.push_back(t);
        s.pop();
        dfs(a, s, order, res);
    }
    //a和s都不空，开辟两条路径，出栈或入栈，继续dfs
    else{
        //入栈
        queue<int> aa = a;
        stack<int> ss = s;
        int t = aa.front();
        aa.pop();
        ss.push(t);
        dfs(aa, ss, order, res);
        //出栈
        t = s.top();
        order.push_back(t);
        s.pop();
        dfs(a, s, order, res);
    }
}

int main() {
    //输入数据
    int n; 
    cin >> n;
    queue<int> a;
    for(int i = 1; i <= n; i++){
        int tmp;
        cin >> tmp;
        a.push(tmp);
    }
    //使用到的栈
    stack<int> s;
    //结果序列
    vector<vector<int>> res;
    vector<int> order;//存储一种顺序的中间容器
    //深度优先搜索函数
    dfs(a, s, order, res);
    //按字典序排序
    sort(res.begin(), res.end());
    
    //输出结果
    for(const auto& v : res){
        for(const auto& i : v){
            cout << i << " ";
        }
        cout << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")