棧與隊列常見面試題：最小值棧、出棧序列合法性 C++ 實現

題目一：實現 O(1) GetMin 的棧

同 文章 3095，此處給出另一種寫法（類內直接用 STL stack）。

#include 
#include 
using namespace std;

template 
class Stack {
public:
    void push(const T& x) {
        _stack.push(x);
        if (_minStack.empty() || x < _minStack.top())
            _minStack.push(x);
        else
            _minStack.push(_minStack.top()); // 關鍵：每次都壓入當前最小值，長度同步
    }
    void pop() {
        _stack.pop();
        _minStack.pop();
    }
    T getMin() const { return _minStack.top(); }
private:
    stack _stack;
    stack _minStack;
};

void test() {
    Stack s;
    s.push(3); s.push(2); s.push(5); s.push(1); s.push(7);
    s.pop(); s.pop(); // 彈出 7, 1
    cout << "最小值: " << s.getMin() << endl; // 2
}

int main() { test(); return 0; }

差異點：此版本 push 時 無條件向 minStack 壓入當前最小值（要么是新值，要么復制棧頂），導致兩棧長度始終相等，pop 時直接同步彈出，無需比較。代碼更簡潔，空間略大（重複存儲相同最小值）。

題目二：判斷出棧序列合法性

同 文章 3093，此處給出完整主函數測試版。

#include 
#include 
using namespace std;

bool isValidPopOrder(int* pushSeq, int* popSeq, int len) {
    if (!pushSeq || !popSeq) return false;
    stack s;
    int j = 0;
    for (int i = 0; i < len; ++i) {
        s.push(pushSeq[i]);
        while (!s.empty() && s.top() == popSeq[j]) {
            s.pop();
            ++j;
        }
    }
    return s.empty();
}

int main() {
    int pushSeq[] = {1, 2, 3, 4, 5};
    int popSeq1[] = {4, 5, 1, 2, 3}; // 合法
    int popSeq2[] = {4, 3, 5, 1, 2}; // 不合法
    int len = sizeof(pushSeq) / sizeof(pushSeq[0]);

    cout << (isValidPopOrder(pushSeq, popSeq1, len) ? "合法" : "不合法") << endl;
    cout << (isValidPopOrder(pushSeq, popSeq2, len) ? "合法" : "不合法") << endl;
    return 0;
}

總結對比

兩題均為棧的經典應用，面試高頻。掌握「輔助棧同步」與「模擬入棧匹配」兩大核心模式，可輕鬆應對變體。