栈的压入弹出序列判断算法详解

题目描述

给定两个整数序列：

• pushV：压栈序列
• popV：待验证的弹栈序列

需要判断 popV 是否可能是 pushV 对应的弹栈序列。

核心思路

要解决这个问题，我们需要理解栈的工作机制：压栈操作：元素按照 pushV 的顺序依次入栈。弹栈操作：在任意时刻，只能弹出栈顶元素。时机选择：可以在压入任意元素后选择弹出栈顶元素。

关键洞察：我们可以通过模拟整个压栈弹栈过程来验证序列的合法性。

完整代码实现

#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // 使用辅助栈模拟压栈弹栈过程
        stack<int> st;
        // 双指针：_push 指向当前要压入的元素，_pop 指向当前要弹出的元素
        size_t _push = 0; // 压栈序列的索引
        size_t _pop = 0;  // 弹栈序列的索引

        // 遍历所有需要压入的元素
        while (_push < pushV.size()) {
            // 将当前元素压入栈中
            st.push(pushV[_push++]);
            // 检查栈顶元素是否与当前期望弹出的元素匹配
            // 如果匹配，则连续弹出所有匹配的元素
            while (!st.empty() && st.top() == popV[_pop]) {
                _pop++; 
                st.(); 
            }
        }
        
         st.();
    }
};