HDU 1022 Train Problem I：棧模擬判斷火車出站序列

問題描述

只有一條鐵路軌道，火車從一端進入，另一端離開。若火車 A 先進站，B 後進站，則 A 必須等 B 離開後才能離開（後進先出，棧結構）。給定進站序列 O1 和擬定出站序列 O2，判斷 O2 是否可行。若可行，輸出操作序列（in 進站、out 出站），最後輸出 FINISH；否則輸出 No. 並換行 FINISH。

解題思路：模擬棧操作

維護一個棧模擬站內軌道。遍歷進站序列 O1，依次將車廂壓入棧（輸出 in）。每次壓入後，檢查棧頂是否等於出站序列 O2 的下一個待出站車廂；若相等，彈出棧（輸出 out），並推進 O2 指針。重複直到棧頂不匹配或棧空。最後若所有車廂皆能按序出站，則序列合法。

算法流程

1. 讀入 n、O1、O2。
2. 初始化空棧、out_idx = 0、操作記錄列表。
3. 對 O1 中每個車廂 c：
   • 壓入棧，記錄 in。
   • 當棧非空且棧頂 == O2[out_idx] 時：彈出，記錄 out，out_idx++。
4. 若最終 out_idx == n，輸出 Yes. 和操作序列；否則輸出 No.。
5. 每組測試案例結束輸出 FINISH。

複雜度分析

每個車廂最多進棧、出棧各一次，時間 O(n)，空間 O(n)。n ≤ 9 極小，但算法可擴展至大規模。

參考代碼 (Java)

import java.util.*;

public class TrainProblem {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            String inSeq = sc.next();
            String outSeq = sc.next();
            Deque stack = new ArrayDeque<>();
            List ops = new ArrayList<>();
            int outIdx = 0;
            for (char c : inSeq.toCharArray()) {
                stack.push(c);
                ops.add("in");
                while (!stack.isEmpty() && stack.peek() == outSeq.charAt(outIdx)) {
                    stack.pop();
                    ops.add("out");
                    outIdx++;
                }
            }
            if (outIdx == n) {
                System.out.println("Yes.");
                for (String op : ops) System.out.println(op);
            } else {
                System.out.println("No.");
            }
            System.out.println("FINISH");
        }
    }
}

核心點

• 棧的後進先出特性完美對應鐵路軌道限制。
• 貪心地在可能時立即執行 out 操作，保證找到合法序列（若存在）。
• 輸出格式嚴格遵循題目要求，注意大小寫與標點。