火车进站

OJ_算法

题目描述：

分析：给定一个正整数N代表火车数量，0

样例输入：

3

1 2 3

样例输出：

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1

解答：
  其实核心就是一个栈，对于第K个数，在第K个数进栈之前，前面的 K-1 个数要么全部出去了，要么都在栈里面，要么部分在栈里面部分出去了。那么可以假想，在第K个数入栈之前，依次从栈里面出去 0个、1个、2个……栈.size()个，然后把第K个入栈，再对于 K+1个同样实施这样的方法——这就是个递归了。

　　出去了的保存在一个队列里面，没出站的保存在栈里面，最后一辆车处理完了递归结束并输出。

代码如下：

#include<iostream>  
#include<stack>  
#include<vector>  
#include<algorithm>  
using namespace std;
void train_out_orders(vector<int>& train, stack<int> s, vector<int> out, int cur_train, int n, vector<int*> &all_train_orders)
{
    for (int i = s.size(); i >= 0; i--)
    {
        stack<int>  stack_temp(s);
        vector<int> out_temp(out);
        for (int j = 1; j <= i; j++)//堆栈中，可以先出栈[0,s.size()个]到out_temp中，然后第cur_train辆车进站
        {
            out_temp.push_back(stack_temp.top());
            stack_temp.pop();
        }
        stack_temp.push(train[cur_train]);//第cur_train辆车进站
        if (cur_train == n - 1) //保存结果
        {
            int *train_out_temp = new int[n];
            int i;
            for (i = 0; i < out_temp.size(); i++)//已经出栈的车
                train_out_temp[i] = out_temp[i];
            for (; i < n; i++)//还在栈里边的车依次输出
            {
                train_out_temp[i] = stack_temp.top();
                stack_temp.pop();
            }
            all_train_orders.push_back(train_out_temp);
        }
        else
            train_out_orders(train, stack_temp, out_temp, cur_train+1, n, all_train_orders);
    }
}
int main()
{
    int n;
    vector<int*> all_train_orders;
    vector<int> out_temp;
    stack<int> s;
    cin >> n;
    vector<int> train_in(n, 0);
    for (int i = 0; i < n; i++)
        cin >> train_in[i];
    train_out_orders(train_in, s, out_temp, 0, n, all_train_orders);
    for (size_t i = 0; i < all_train_orders.size(); i++)
    {
        for (int j = 0; j < n - 1; j++)
            cout << all_train_orders[i][j] << " ";
        cout << all_train_orders[i][n - 1] << endl;
    }
    return 0;
}

参考文献1：http://www.cnblogs.com/jiayith/p/4414226.html（本文主要源自此文献）
参考2：http://blog.csdn.net/suifeng50/article/details/47070655（这个更简洁，但没有看懂）