九度 1512 用兩個棧實現隊列 - 模擬隊列操作

題目大意

用兩個棧 S1, S2 實現隊列。支援操作：

• PUSH X：入隊。
• POP：出隊並輸出值，隊列空輸出 -1。

n ≤ 100000 操作。

雙棧實現邏輯

• S1：入隊棧 (push 進 S1)。
• S2：出隊棧 (pop 從 S2)。
• POP 時：

if S2 不空：輸出 S2.top(), S2.pop()
else if S1 空：輸出 -1
else：將 S1 所有元素 pop 並 push 進 S2 (順序反轉)，再輸出 S2.top(), S2.pop()

完整代碼

#include 
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        stack s1, s2;
        for (int i = 0; i < n; ++i) {
            string op; cin >> op;
            if (op == "PUSH") {
                int x; cin >> x;
                s1.push(x);
            } else { // POP
                if (!s2.empty()) {
                    cout << s2.top() << '\n';
                    s2.pop();
                } else if (s1.empty()) {
                    cout << -1 << '\n';
                } else {
                    while (!s1.empty()) {
                        s2.push(s1.top());
                        s1.pop();
                    }
                    cout << s2.top() << '\n';
                    s2.pop();
                }
            }
        }
    }
    return 0;
}

複雜度

• 均攤 O(1)：每個元素進 S1 一次、轉移到 S2 一次、從 S2 出一次。
• 空間：O(n)。

關鍵細節

• 輸入可能多測資 (while cin>>n)。
• POP 後 S2 變空且 S1 不空時，下次 POP 會再次觸發轉移，邏輯正確。