栈的弹出压入序列＜难度系数＞

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

提示：

• 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。

🧷 平台：Visual studio 2017 && windows

核心思想：这道题之前我们有碰到过选择题。这道题本质就是模拟栈的特性 “Last In First Out”。

这里定义了一个栈来模拟，不管三七二十一，pushi 先入栈，随后 ++，出栈的顺序一定是入栈后再出的，所以每次入栈后都需要判断 pushi and popi 是否相等，相等就出(且要循环着出)，否则就入，它们两个都能走到最后，就说明是匹配的。

nowcoder原题

class Solution {public:    bool IsPopOrder(vector<int> pushV,vector<int> popV) {        stack<int> st;        size_t pushi = 0, popi = 0;        //压入顺序结束就必须出结果        while(pushi < pushV.size())        {             //先入一个数据,然后++            st.push(pushV[pushi++]);            //循环出栈            while(!st.empty() && st.top() == popV[popi])            {                ++popi;                st.pop();            }        }        //st为空,说明匹配        return st.empty();        //同上        //return popi == popV.size();    }};