方法1

(不用栈进行模拟)

本题为判断某序列是否为栈混洗序列。我们知道，只要某序列中不存在“312”禁形即为合法的栈混洗。当然这题我们直接模拟栈混洗的过程即可解决。
首先，注意题目说空序列不是合法的栈混洗序列，但是后台用例认为是，翻了下剑指offer书，应该是题目写错了，两个空序列是合法的。
不用栈，使用哈希map来标识各个元素的状态：0-未入栈；1-已入栈；2-已出栈。然后人为的对序列进行遍历，首先定义p指针指向入栈序列，向右移动直到找到第一个等于出栈序列首位元素的元素，移动过程中将扫过的元素均入栈（设标识为1）。
在匹配下一个出栈序列元素时，判断该元素的状态，未入栈p则右移，已入栈p则左移，并且将扫过的元素出栈（设标识为2）。如果出栈序列中出现了标识为01以外的元素，则不匹配。

C++ 代码

class Solution {
public:
    bool isPopOrder(vector<int> pushV,vector<int> popV) {
        int n = pushV.size();
        if(!n)  return true;
        if(popV.size() != n)  return false;
        unordered_map<int,int> m;//0未入栈，1已入栈，2已出栈
        for(int i = 0;i < n;i++)    m[pushV[i]] = 0;
        int p = 0;
        for(int i = 0;i < n;i++){
            if(m[popV[i]] == 0){
                while(pushV[p] != popV[i]){
                    if(m[pushV[p]] == 0)    m[pushV[p]]++;
                    p++;
                }
                m[pushV[p]] = 2;
                continue;
            }
            if(m[popV[i]] == 1){
                while(pushV[p] != popV[i]){
                    if(m[pushV[p]] == 1)    m[pushV[p]]++;
                    p--;
                }
                m[pushV[p]] = 2;
                continue;
            }
            else{
                return false;
            }
        }
      return true;  
    }
};

方法2

(用栈模拟)

用栈模拟栈混洗。
 先将最先要入栈的元素入栈，然后判断当前栈顶元素是否等于q指向的出栈序列元素，相等则出栈，q++，继续判断，不等则在继续入栈，重复操作。
注意这题的边界，不匹配时肯定是p最先用完，所以判断p即可，最后p到达n，循环结束，栈空则说明栈混洗序列合法，否则不合法。

C++ 代码

class Solution {
public:
    bool isPopOrder(vector<int> pushV,vector<int> popV) {
        int n = pushV.size();
        if(!n)  return true;
        if(popV.size() != n)  return false;
        stack<int> s;
        s.push(pushV[0]);
        int p = 0,q = 0;
        while(p < n){
            while(!s.empty() && s.top() == popV[q]){
                s.pop();
                q++;
            }
            if(++p < n) s.push(pushV[p]);
        }
        if(s.empty())   return true;
        return false;
    }
};