C++ 檢查棧出棧順序合法性

問題描述

給定入棧序列 stackIn 和出棧序列 stackOut，判斷 stackOut 是否為合法的出棧順序。假設元素唯一。

算法邏輯：模擬棧操作

1. 用一個輔助棧 s 模擬入棧過程。
2. 遍歷入棧序列，每入棧一個元素，檢查棧頂是否等於出棧序列當前位置的元素。
3. 若相等，彈出棧頂，出棧序列指針後移；重複直到不相等或棧空。
4. 所有入棧完成後，若輔助棧為空 → 合法；否則不合法。

代碼實現

#include 
#include 
#include 
using namespace std;

bool CheckSequence(int* stackIn, int* stackOut, int lenIn, int lenOut) {
    assert(stackIn && stackOut);
    if (lenIn != lenOut) return false; // 長度不同必不合法

    stack s;
    int j = 0; // 出棧序列指針
    for (int i = 0; i < lenIn; ++i) {
        s.push(stackIn[i]);
        while (!s.empty() && s.top() == stackOut[j]) {
            s.pop();
            ++j;
        }
    }
    return s.empty(); // 棧空說明所有元素都按序出棧
}

int main() {
    int stackIn[]  = {1, 2, 3, 4, 5};
    int stackOut[] = {5, 4, 2, 3, 1}; // 合法
    int len = sizeof(stackIn) / sizeof(stackIn[0]);

    bool ok = CheckSequence(stackIn, stackOut, len, len);
    cout << (ok ? "出棧順序合法" : "出棧順序不合法") << endl;
    return 0;
}

複雜度

• 時間：O(n) — 每個元素最多入棧、出棧各一次。
• 空間：O(n) — 輔助棧。

擴展思考

• 若元素不唯一，需用索引或指針區分，邏輯相同。
• 可生成第 k 個合法出棧序列（卡特蘭數相關）。
• 鐵路調度、編譯器語法分析（移進歸約）均為同類問題。