题解 | #火车进站#相比递归更喜欢循环+面向对象的写法

import java.util.*;
import java.util.stream.*;
import java.util.regex.*;
import java.util.function.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int count = in.nextInt();
        LinkedList<String> queue = new LinkedList<>();
        while (count > 0 ) {
            queue.add(in.next());
            count--;
        }

        /**
        分别使用递归和循环的方法：循环实现更难，从递归转换而来
         */
        // System.out.println(String.join("\n", trainRecursion(queue)));
        System.out.println(String.join("\n", trainIteration(queue)));
    }

    static List<String> trainIteration(LinkedList<String> queue) {
        // 模拟递归
        List<List<String>> allPlans = new ArrayList<>();
        // 定义调度中的对象
        List<Progress> progresses = new ArrayList<>();
        progresses.add(new Progress(queue));

        // 还有未完成的调度
        while (progresses.size() > 0) {
            // 对每个调度进行操作
            List<Progress> newProgresses = new ArrayList<>();
            for (int i = 0 ; i < progresses.size(); i++) {
                Progress p = progresses.get(i);
                if (p.finished()) {
                    allPlans.add(p.getResult());
                } else {
                    newProgresses.addAll(p.moreProgress());
                }
            }
            progresses = newProgresses;
        }
        return allPlans.stream().map(l-> {
            return String.join(" ", l);
        }).distinct().sorted().collect(Collectors.toList());
    }

    /**
    火车站视角来思考：两种情况都要“走”到(模拟“走”完所有可能的方案)
        - 一次调度是指，让一辆车进站或者让一辆车出站
        - 调度完毕是指：当前的 N 辆车均完成了进出站
    */
    static List<String> trainRecursion(LinkedList<String> queue) {
        List<List<String>> allPlans = new ArrayList<>();
        recursion(queue, new LinkedList<String>(), new ArrayList<String>(), allPlans);

        return allPlans.stream().map(l-> {
            return String.join(" ", l);
        }).distinct().sorted().collect(Collectors.toList());
    }

    static void recursion(LinkedList<String> queue, LinkedList<String> stack,
                          List<String> plan, List<List<String>> allPlans) {
        if (queue.isEmpty() && stack.isEmpty()) {
            allPlans.add(plan);
            return;
        }
        // 1 进站
        if (!queue.isEmpty()) {
            // clone queue and stack
            LinkedList<String> q = new LinkedList<>(queue);
            LinkedList<String> s = new LinkedList<>(stack);
            List<String> p = new ArrayList<>(plan);
            s.push(q.poll());
            recursion(q, s, p, allPlans);
        }
        // 2 出站
        if (!stack.isEmpty()) {
            // clone queue and stack
            LinkedList<String> q = new LinkedList<>(queue);
            LinkedList<String> s = new LinkedList<>(stack);
            List<String> p = new ArrayList<>(plan);
            p.add(s.pop());
            recursion(q, s, p, allPlans);
        }
    }
}

class Progress {
    LinkedList<String> queue = new LinkedList<>();
    LinkedList<String> stack = new LinkedList<>();
    List<String> result = new ArrayList<>();

    Progress(LinkedList<String> queue) {
        this.queue = queue;
    }

    Progress(LinkedList<String> queue, LinkedList<String> stack,
             List<String> result) {
        this.queue = queue;
        this.stack = stack;
        this.result = result;
    }

    public boolean finished() {
        return queue.isEmpty() && stack.isEmpty();
    }

    public List<String> getResult() {
        return this.result;
    }

    public List<Progress> moreProgress() {
        List<Progress> list = new ArrayList<>();
        if (this.finished()) return null;

        if (!queue.isEmpty()) {
            // clone
            LinkedList<String> q = new LinkedList<>(queue);
            LinkedList<String> s = new LinkedList<>(stack);
            List<String> r = new ArrayList<>(result);
            s.push(q.poll());
            list.add(new Progress(q, s, r));
        }
        if (!stack.isEmpty()) {
            // clone
            LinkedList<String> q = new LinkedList<>(queue);
            LinkedList<String> s = new LinkedList<>(stack);
            List<String> r = new ArrayList<>(result);
            r.add(s.pop());
            list.add(new Progress(q, s, r));
        }
        return list;
    }
}