經典算法題：鐵軌車廂重組（棧模擬）

經典算法題：鐵軌車廂重組（棧模擬）

《算法競賽入門經典》6.1.2 例題：火車站中轉站車廂重排問題。核心考察棧（LIFO）特性在實際調度中的應用。

問題描述

• n 節車廂從 A 方向駛入，編號 1~n。
• 目標：通過中轉站 C（棧，後進先出）重組，使其按給定順序 target[1..n] 從 B 方向駛出。
• 操作只有兩種：A → C（入棧）、C → B（出棧）。車廂一旦進 C 不能回 A，進 B 不能回 C。
• 判斷給定目標序列是否可行，輸出 Yes/No。

棧模擬算法邏輯

維護三個指標：

• A：下一個待從 A 進站車廂編號（初始 1）。
• B：下一個待輸出到 B 的目標序列索引（初始 1）。
• stack[top]：中轉站 C，top 為棧頂指針（0 表空）。

循環直到 B > n（全輸出成功）或無法操作：

1. 若 A == target[B]：車廂直通 A→C→B，A++、B++。
2. 否若棧非空且 stack[top] == target[B]：棧頂車廂出站，top--、B++。
3. 否若 A <= n：將 A 入棧 stack[++top] = A++。
4. 否：無車可入棧、棧頂不匹配目標 → 不可能，輸出 No。

C 語言實現

#include <stdio.h>
#define MAXN 1010

int n, target[MAXN];

int main() {
    while (scanf("%d", &n) == 1) {
        int stack[MAXN], top = 0;
        int A = 1, B = 1;
        for (int i = 1; i <= n; i++) scanf("%d", &target[i]);
        int ok = 1;
        while (B <= n) {
            if (A == target[B]) { A++; B++; }
            else if (top && stack[top] == target[B]) { top--; B++; }
            else if (A <= n) { stack[++top] = A++; }
            else { ok = 0; break; }
        }
        printf("%s\n", ok ? "Yes" : "No");
    }
    return 0;
}

C++ STL 版（更簡潔）

#include <cstdio>
#include <stack>
using namespace std;
#define MAXN 1010
int n, target[MAXN];
int main() {
    while (scanf("%d", &n) == 1) {
        stack<int> s;
        int A = 1, B = 1;
        for (int i = 1; i <= n; i++) scanf("%d", &target[i]);
        int ok = 1;
        while (B <= n) {
            if (A == target[B]) { A++; B++; }
            else if (!s.empty() && s.top() == target[B]) { s.pop(); B++; }
            else if (A <= n) { s.push(A++); }
            else { ok = 0; break; }
        }
        printf("%s\n", ok ? "Yes" : "No");
    }
    return 0;
}

關鍵點總結

• 棧 = 後進先出（LIFO），單端操作，僅需陣列 + top 指針。
• 下標從 1 起碼碼更直觀：target[1] 為首個目標，stack[1] 為棧底，top=0 為空。
• 模擬過程中 A 只增不減，B 只增不減，top 先增後減，單調性保證 O(n) 時間複雜度。
• 此題是棧在排列遞推、合法性判斷中典型應用，同類還有「出棧序列合法性」、「瀏覽器前進後退」、「括號匹配」等。