用栈解决铁轨问题

一 问题描述

某城市有一个火车站，铁轨铺设如下图所示。有 n（n<=1000）节车厢从 A 方向驶入车站，将其按进站的顺序编号为 1~n。你的任务是判断是否能让它们按照某种特定的顺序进入 B 方向的铁轨并驶出车站。例如，出站顺序（5 4 1 2 3）是不可能的，但出站顺序（5 4 3 2 1）是可能的。为了重组车厢，可以借助中转站 C。中转站 C 是一个可以停放任意多节车厢的车站，但是由于末端封顶，驶入 C 的车厢必须按照相反的顺序驶出 C。对于每节车厢，一旦从 A 移入 C，就不能返回 A了；一旦从 C 移入 B，就不能返回 C 了。在任意时刻只有两种选择：从 A 到 C和 C 到 B。

输入：输入包含多组数据，对于每一组数据，第 1 行是一个整数 n。接下来的若干行，每行 n 个数，代表 1~n 车厢的出站顺序，最后一行只有一个整数 0。最后一组数据 n=0，输入结束，不输出答案。

输出：对每行的出站顺序都单行输出“Yes”或“No”。对每组数据都在最后输出空行。

输入样例

5

1 2 3 4 5

5 4 3 2 1

0

6

6 5 4 3 2 1

0

0

输出样例

Yes

No

Yes

二 思路

本问题的 C 就是一个栈，1 ~ n 车厢按顺序依次从 A 端进来，首先和 B 端的字符进行比较，如果相等，则直接从 B 端出去，如果不相等则进入栈 C。如果栈非空，则判断栈顶元素是否与 B 端的字符相等，如果相等则出栈，一直比较下去。如果 1~n 车厢都已处理完毕，B端字符还未处理完，则输出 No，否则输出 Yes。

输入包含多组数据，每组数据都以 0 结束，每组数据输出结束时都会加一个空行。最后一组数据为 0，不输出。

三 算法设计

1 输入 n，如果 n 为0，则结束。

2 输入第 1 组数据的第 1 个字符。

3 如果 B[1]不为0，则读入余下的字符并将其存入B[]。

4 初始化一个栈 s。

5 1~n 车厢依次与 B 端的字符进入比较，相等则直接出栈，否则入栈。

6 如果栈非空，则判断栈顶元素是否与 B 端字符是否相等，相等则出栈，并一直比较下去。

7 如果 1~n 车厢都已经处理完毕，B 端字符还未处理完，则输出“No”，否则输出“Yes”。

四 图解

1 以输入 3 2 1 5 4 为例，将序列存入 B[],j = 1,初始化一个栈。

2 i=1，将 i 与 B[1]=3 进行比较，不相等，1 入栈。

3 i=2，将 i 与 B[1]=3 进行比较，不相等，2 入栈。

4 i=3，将 i 与 B[1]=3 进行比较，相等，j++，j=2

5 栈非空，栈顶元素 2和B[2]=2比较，相等，出栈，j++，j=3；栈非空，栈顶元素1和B[3]=1比较，相等，出栈，j++(j=4);此时栈空。

6 i=4，将 i 与 B[4]=5 进行比较，不相等，4 入栈。

7 i=5，将 i 与B[4]=5进行比较，相等，j++,j=5。

8 栈非空，栈顶元素 4 和 B[5]=4 相等，出栈，j++，j=6；此时栈空。

9 此时 j>n,输出 Yes

五 代码

package stackdemo;import java.util.Scanner;
import java.util.Stack;public class RailProblem {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (true) {int n = scanner.nextInt();if (n == 0) {break;}while (true) {int i = 1;int j = 1;Integer B[] = new Integer[n + 1];B[1] = scanner.nextInt();if (B[1] == 0) {break;}for (int k = 2; k <= n; k++) {B[k] = scanner.nextInt();}Stack<Integer> s = new Stack<>();while (i <= n) {if (i == B[j]) {i++;j++;} else {s.push(i++);}while (!s.isEmpty() && s.peek() == B[j]) {j++;s.pop();}}if (j <= n) {System.out.println("No");} else {System.out.println("Yes");}}}}
}

六 测试

绿色为输入，白色为输出。