การตรวจสอบลำดับ Stack Sequences ใน C++

การตรวจสอบลำดับ Stack Sequences (Validate Stack Sequences)

ให้ลำดับ pushed และ popped ที่มีค่าต่างกันทั้งหมด ต้องการทราบว่าลำดับ popped นี้อาจเป็นผลลัพธ์จากการ push และ pop บน stack เริ่มต้นว่างได้หรือไม่

ตัวอย่าง: push = [1,2,3,4,5], pop = [4,5,3,2,1] → true

ลำดับการทำงาน: push(1), push(2), push(3), push(4), pop()→4, push(5), pop()→5, pop()→3, pop()→2, pop()→1

ขั้นตอนการแก้ปัญหา

1. สร้าง stack st, index := 0
2. วนลูป i จาก 0 ถึง pushed.size()-1:
   • push pushed[i] เข้า st
   • ถ้า popped[index] == st.top():
     • index++, pop จาก stack
     • วนลูปในขณะที่ !st.empty() && popped[index] == st.top(): index++, pop
3. หลังลูปหลัก: วนลูปในขณะที่ index < popped.size():
   • ถ้า popped[index] == st.top(): index++, pop
   • มิฉะนั้น break
4. คืนค่า st.empty()

ตัวอย่างโค้ด 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();
    }
};

อินพุทและเอาต์พุทตัวอย่าง

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

Output: 1 (true)