深度遍历，模拟出栈入栈

深度遍历，模拟出栈入栈
递归时分三种情况：
1.进站不出
2.进站之后马上出站
3.栈里的车出来
当全部火车出站，算一种结果，最后用set去重排序。。。
运行时间45ms，好像要优于全排列的方法

#include <bits/stdc++.h>

using namespace std;
void dfs(set<vector<int>> &st, vector<int> &nums, stack<int> &s, vector<int>& q, int k)
{
    //车全部出站，返回
    if(q.size()==nums.size())
    {
        st.insert(q);
        return;
    }
    for(int i=0; i<3; i++)
    {
        //有三种情况 
        //进站，马上出站
        if(k<nums.size() && i==0)
        {
            q.push_back(nums[k++]);
            dfs(st, nums, s, q, k);
            q.pop_back();
            k--;
        }
        //进站之后不出站
        else if(k<nums.size() && i==1)
        {
            s.push(nums[k++]);//从待入站的车中取出一辆入站
            dfs(st, nums, s, q, k);
            s.pop();
            k--;
        }
        //车从站里出来
        else if(i==2 && !s.empty())
        {
            q.push_back(s.top());
            s.pop();
            dfs(st, nums, s, q, k);
            s.push(q[q.size()-1]);
            q.pop_back();
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    while(cin>>n)
    {
        vector<int> nums(n);//待入栈的车
        for(int i=0; i<n; i++)
            cin>>nums[i];
        stack<int> s;//站内的车
        vector<int> q;//已经出站的车
        set<vector<int>> st;
        dfs(st, nums, s, q, 0);
        for(auto iter=st.begin(); iter!=st.end(); ++iter)
        {
            for(int i=0; i<n; i++)
            {
                cout<<(*iter)[i]<<" ";
            }
            cout<<endl;
        }
    }
}