题解 | #火车进站#

import java.util.*;

public class Main {
    private static int[] nums = null;
    //待进站列车
    private static Deque<Integer> waiting = new LinkedList<Integer>();
    //站内/待出站列车(后进先出)
    private static Stack<Integer> station = new Stack<Integer>();
    //已出站列车
    private static Deque<Integer> already = new LinkedList<Integer>();
    //结果集，一个元素表示一种方案
    private static List<String> result = new ArrayList<String>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        //放入待进站队列
        for (int i = 0; i < n; i++) {
            waiting.add(in.nextInt());
        }
        dfs();
        Collections.sort(result);
        for (String str : result) {
            System.out.println(str);
        }
    }
    //深度优先搜索
    private static void dfs() {
        if (waiting.isEmpty() && station.isEmpty()) {
            add2Result();
            return;
        }
        //进站
        if (!waiting.isEmpty()) {
            int in = waiting.pollFirst();//待进站列车移出一个
            station.push(in);//进入到站内
            //进入下一层搜索
            dfs(); //因为子搜索会执行完会还原所有队列，所以对外层来说相当于没有操作
            //还原,假装没进
            waiting.addFirst(in);
            station.pop();
        }
        //出站
        if (!station.isEmpty()) {
            int out = station.pop();//出站一个
            already.addLast(out);//放进已出站列表
            //进入下一层搜索
            dfs();
            //还原,假装没出
            station.push(out);
            already.pollLast();
        }
    }
    //将当前出站队列加入到结果集
    private static void add2Result() {
        StringBuilder sb = new StringBuilder();
        for (Integer i : already) {
            sb.append(i + " ");
        }
        sb.deleteCharAt(sb.length() - 1);
        result.add(sb.toString());
    }
}