算法：使用栈

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int i = 0;
        for (int x : pushed) //注意pushed和popped是一组数据
        {
            st.push(x); //把x放进去(总的来看是按序)
            while (st.size() && st.top() == popped[i]) //每次都尽可能的把栈顶的元素pop()弹出，只要和所需popped数据相同即弹出
            {
                st.pop();
                i++;
            }
            //所以最后所有能按序压入弹出的操作都进行了，如果栈空就是符合题意。
        }
        return st.size() == 0; //return st.empty(); 也能过。（据说效率高些）但评论区有争议貌似..(划掉，并没有争议，那个人看错了题意要的是pushed长度==popped长度)

    }

Python

def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        st = []
        i = 0
        for x in pushed:
            st.append(x)
            while st and st[-1] == popped[i]:
                i += 1
                st.pop()
        return len(st) == 0

或者直接就用pushed这个数据来充当栈
TC O(N), SC O(1) 空间

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int i = 0, j = 0;
        for (int x : pushed){
            pushed[i] = x;
            i ++;
            while (i > 0 && pushed[i - 1] == popped[j])
                --i, ++j;
        }
        return i == 0;
    }

Python

def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        i = j = 0
        for x in pushed:
            pushed[i] = x
            while i >= 0 and pushed[i] == popped[j]:
                i, j = i - 1, j + 1
            i += 1
        return i == 0