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

问题描述

给定两个整数序列：pushV（压栈序列）和 popV（待验证的弹栈序列）。我们需要判断 popV 是否可能是 pushV 对应的合法弹栈序列。

核心思路

解决这个问题的关键在于理解栈的后进先出特性。我们可以通过模拟整个压栈和弹栈的过程来验证序列的合法性。

具体策略如下：

1. 压栈操作：元素按照 pushV 的顺序依次入栈。
2. 弹栈操作：在任意时刻，如果栈顶元素与当前期望弹出的元素匹配，则立即弹出。
3. 贪心选择：只要栈顶能匹配，就立刻弹出，因为如果不现在弹出，后续再想弹出它就必须先把上面的元素压进去，这会导致顺序错乱。

代码实现

下面是一个基于 C++ STL 的实现，利用辅助栈和双指针来跟踪进度。

#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.();
    }
};