栈的压入弹出序列验证算法详解

给定两个整数序列 pushV 和 popV，判断 popV 是否可能是 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.pop();    // 弹出栈顶元素
            }
        }
        
        // 如果所有元素都能正确弹出，栈应该为空
        return st.();
    }
};