栈的压入及弹出序列

描述

??输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

0<=pushV.length == popV.length <=1000
-1000<=pushV[i]<=1000
pushV 的所有数字均不相同

示例1

输入：
[1,2,3,4,5],[4,5,3,2,1]
返回值：
true
说明：
可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true

示例2

输入：
[1,2,3,4,5],[4,3,5,1,2]
返回值：
false
说明：
由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false

思路/解法

方式一

用一个栈结构保存pushV容器中与popV容器不相同的部分，pushV容器和popV容器相等的部分则去除（每个元素均进行比较）。最后判断栈空间剩余的数据和popV容器出栈的顺序是否相同，如果相同则合法，不相同则不合法。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> stacks;
        
        while(!pushV.empty())
        {
            if(!stacks.empty() && stacks.top() == popV[0])
            {
                stacks.pop();
                popV.erase(popV.begin());
                continue;
            }
            
            if(pushV[0] != popV[0])
                stacks.push(pushV[0]);
            else 
                popV.erase(popV.begin());
            pushV.erase(pushV.begin());
        }
        
        while(!popV.empty())
        {
            if(popV[0] != stacks.top())
                return false;
            else
            {
                popV.erase(popV.begin());
                stacks.pop();
            }
        }
        return true;
    }
};

方式二

构建一个临时栈空间用于存储pushV容器和popV容器不相同的数值，当栈顶元素和popV容器首元素相同的时候，则将栈空间的元素出栈，重复比较，直至栈空间的元素与popV容器的元素不相等为止。如果pushV容器遍历完后临时栈空间为空，则表示popV容器出栈方式合法，否则不合法。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> temp;
        for(int i =0,j  = 0;i<pushV.size();i++)
        {
            temp.push(pushV[i]);
            while(!temp.empty() && temp.top() == popV[j])
            {
                temp.pop();
                j++;
            }
        }
        return temp.empty();
    }
};