题解 | #火车进站#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static List<String> allPopStack = new ArrayList<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int[] waStack = new int[a];
            for (int i = 0; i < a; i++) {
                waStack[i] = in.nextInt();
            }

            LinkedList<Integer> stackInsert = new LinkedList<>();
            for (int i = 0; i < waStack.length; i++) {
                stackInsert.add(waStack[i]);
            }
            visitStack(stackInsert, new Stack<Integer>(), new LinkedList<Integer>(),
                       waStack.length);
            Collections.sort(allPopStack);
            for (String s : allPopStack) {
                System.out.println(s);
            }
        }
    }

    public static void visitStack(LinkedList<Integer> insert, Stack<Integer> stack,
                                  LinkedList<Integer> record, int size) {
        //栈已经全部入完
        if (record.size() == size) {
            //已经全部记录
            StringBuilder builder = new StringBuilder();
            for (Integer integer : record) {
                builder.append(integer).append(" ");
            }
            allPopStack.add(builder.toString().trim());
            return;
        }

        //入栈, 还有数据可以入栈的时候,才能
        if (insert.size() > 0) {
            Integer inte = insert.pollFirst();
            stack.push(inte);
            visitStack(insert, stack, record, size);

            // 恢复原貌
            insert.addFirst(inte);
            //还回去
            stack.pop();
        }

        //出栈
        if (stack.size() > 0) {
            Integer pop = stack.pop();
            record.add(pop);
            visitStack(insert, stack, record, size);

            stack.push(pop);
            record.removeLast();
        }
    }
}

这个难点是如何 定义三个状态 栈已经全部入完\入栈, 还有数据可以入栈的时候\出栈 并且入栈与出栈的时候需要还原入栈与出栈时候的场景