Xác thực chuỗi stack trong C++

Cho hai chuỗi pushed và popped với các giá trị riêng biệt, xác định xem chúng có thể là kết quả của các phép push/pop trên một stack ban đầu rỗng. Ví dụ: push = [1,2,3,4,5], pop = [4,5,3,2,1] → true. Thứ tự: push(1), push(2), push(3), push(4), pop()→4, push(5), pop()→5, pop()→3, pop()→2, pop()→1.

Giải thuật

• Tạo stack st, index := 0.
• Duyệt i từ 0 đến pushed.size()-1:
  • Push pushed[i] vào st.
  • Nếu popped[index] == st.top():
    • index++, pop stack.
    • Khi st không rỗng và popped[index] == st.top(): index++, pop.
• Khi index < popped.size():
  • Nếu popped[index] == st.top(): index++, pop.
  • Ngược lại thoát vòng lặp.
• Trả về true nếu stack rỗng.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int idx = 0;
        for (int x : pushed) {
            st.push(x);
            while (!st.empty() && idx < popped.size() && st.top() == popped[idx]) {
                st.pop();
                idx++;
            }
        }
        return st.empty();
    }
};

Đầu vào

[1,2,3,4,5] [4,5,3,2,1]

Đầu ra

1