[数据结构与算法]剑指 Offer 31. 栈的压入、弹出序列 辅助站

辅助栈：

辅助栈模拟入栈，出栈情况，i指针指向popped当前需要弹出的数字，与辅助栈栈顶数字对比，相同则辅助栈弹出，且popped指针后移。

c++

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.size()!=popped.size()){
            return false;
        }
        stack<int> stk;  // 辅助栈装pushed数字
        int i = 0;
        for(auto n:pushed){
            stk.push(n); // n入栈
            while(!stk.empty() && stk.top() == popped[i]){ // 必须先判断!stk.empty()
                stk.pop();  // 出栈
                i++;
            }
        }

        return stk.empty();
    }
};

python

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        if len(popped) != len(pushed):
            return False
        stk = []
        i = 0
        for n in pushed:
            stk.append(n) # num 入栈
            while stk and stk[-1] == popped[i]: # 循环判断与出栈
                stk.pop()
                i+=1

        return not stk