棧與隊列經典題：HDU 1072 / POJ 1702 解題詳解

本題要求模擬火車調度：給定進站順序 (1..N)，判斷給定的出站序列是否合法。棧 (站內軌道) 具有後進先出 (LIFO) 特性，是解題關鍵。

問題抽象

• 輸入：多組測試資料，每組先給 N，再給一個長度 N 的排列 (0 結束)。
• 輸出：若該排列可由棧操作產生，輸出 "Yes"，否則 "No"。

演算法邏輯

1. 維護一個棧 `st`，變數 `next_in = 1` 表示下一輛待進站火車。
2. 遍歷目標出站序列 `target[i]`：
   • 若 `st` 非空且棧頂等於 `target[i]`，彈出 (出站)。
   • 否則，將 `next_in` 依序壓入棧直到棧頂等於 `target[i]` 或 `next_in > N`。
   • 若最終棧頂仍不等於 `target[i]`，序列非法。
3. 全序列處理完且棧為空 → 合法。

C++ 參考實作

#include <cstdio>
#include <stack>
using namespace std;

int main() {
    int N;
    while (scanf("%d", &N) == 1 && N) {
        while (true) {
            int target[1005];
            scanf("%d", &target[0]);
            if (target[0] == 0) { puts(""); break; }
            for (int i = 1; i < N; i++) scanf("%d", &target[i]);

            stack st;
            int next_in = 1;
            bool ok = true;
            for (int i = 0; i < N; i++) {
                while (next_in <= N && (st.empty() || st.top() != target[i])) {
                    st.push(next_in++);
                }
                if (!st.empty() && st.top() == target[i]) st.pop();
                else { ok = false; break; }
            }
            puts(ok ? "Yes" : "No");
        }
    }
    return 0;
}

複雜度分析

• 時間：O(N) – 每輛火車至多進棧、出棧各一次。
• 空間：O(N) – 棧深度最多 N。

延伸思考

• 若改用隊列 (FIFO) 或雙端隊列，可產生何種排列？
• 輸出所有合法出站序列 (Catalan 數) 如何生成？

此題是棧模擬的經典入門，掌握「壓入直到滿足、否則失敗」模板，可解決大量類似調度、括號匹配、遞迴消除問題。