Chương trình kiểm tra chuỗi push/pop có hợp lệ cho stack bằng Python

Cho danh sách pushes và pops. Kiểm tra xem có phải trình tự push/pop hợp lệ của stack hay không.

Ví dụ: pushes=[1,2,5,7,9], pops=[2,1,9,7,5] → True.

Giải thuật

• Mô phỏng stack: duyệt pushes, push vào stack.
• Sau mỗi push, lặp: nếu đỉnh stack == pops[i] thì pop và tăng i.
• Cuối cùng stack rỗng → hợp lệ.

Ví dụ minh họa

class Solution:
    def solve(self, pushes, pops):
        s = []
        i = 0
        for ele in pushes:
            s.append(ele)
            while len(s) > 0 and pops[i] == s[-1]:
                s.pop()
                i += 1
        return len(s) == 0

ob = Solution()
pushes = [1, 2, 5, 7, 9]
pops = [2, 1, 9, 7, 5]
print(ob.solve(pushes, pops))

Đầu vào

[1, 2, 5, 7, 9], [2, 1, 9, 7, 5]

Đầu ra

True