题解 | #火车进站#
火车进站
https://www.nowcoder.com/practice/97ba57c35e9f4749826dc3befaeae109
import java.util.*; // 队列表示未进站的火车 // 栈表示已进站的火车 // 每次火车进站后有两种选择:1.直接出站 2.等待下列火车进站 使用递归考虑 public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); // 未进站的火车 Deque<Integer> queue = new LinkedList<>(); // 已进站的火车 Stack<Integer> stack = new Stack<>(); for (int i = 0; i < n; i++) { queue.offer(sc.nextInt()); } List<String> outQueueList = new ArrayList<>(); // 获取所有出站队列保存到outQueueList processOutQueue(queue, stack, "", outQueueList); // 排序 Collections.sort(outQueueList); for (String str : outQueueList) { System.out.println(str); } } } private static void processOutQueue(Deque<Integer> queue, Stack<Integer> stack, String outQueue, List<String> outQueueList) { { if (queue.isEmpty() && stack.isEmpty()) { outQueueList.add(outQueue); } if (!stack.isEmpty()) { int res = stack.pop(); String tempQueue = outQueue + res + " "; processOutQueue(queue, stack, tempQueue, outQueueList); stack.push(res); } if (!queue.isEmpty()) { int res = queue.poll(); stack.push(res); processOutQueue(queue, stack, outQueue, outQueueList); stack.pop(); queue.addFirst(res); } } } }