题解 | #栈的压入、弹出序列#

class Solution {
  public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV) {
        int len = pushV.size();
        stack<int> s;
        int j = 0;//表示进栈元素的个数
        for (int i = 0; i < len; i++) {
            while (j < len && (s.empty() || s.top() != popV[i])) {
			//刚刚初始化的s执行top()会报错，所以放在or后面，当s为空时不再执行后面的s.top()。
                s.push(pushV[j]);
                j++;//j永远不会减小
            }
		  //如果不满足while条件，说明：1.top==popV[i]，代表有数据需要出栈；2.数据已经全部入栈。
		  //如果出栈元素和栈顶元素相同，则pop该元素；若两元素不同，则报错
            if (s.top() == popV[i]) {
                s.pop();
            } else {
                return false;
            }

        }
        return true;//最后没有报错，则返回true
    }
};

这道题目其实就是模拟进栈和出栈的过程，然后再这个过程当中判断pop是否合法。

我们需要不断的push数据，指导popV中的第一个元素，然后我们判断栈s中的元素与popV的第一个元素是否相同（第一个肯定相同），相同则pop该元素；

接着继续判断是否需要进栈，判断的方法在于s的top元素与popV中第二个元素相等，如果不相等，代表需要进栈；直到全部元素入栈完成或者中途出现错误。