栈的压入、弹出序列

你快乐吗?

Posted by bbkgl on September 26, 2019

栈的压入、弹出序列

C++,栈模拟。

模拟所有数据出栈和入栈的过程:

  1. 遍历要出栈的每个元素;
  2. 如果栈顶不是当前要出栈的元素,说明得继续入栈;
  3. 入栈直到栈顶是当前要出栈的元素;
  4. 最后正常的话,所有元素都出栈;
  5. 不正常的话,会出现要出栈的某个元素A,就算把所有元素都入栈,都无法让栈顶元素B = A;

代码:

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> s;
        int m = pushV.size();
        int j = 0;
        for (int &it : popV) {
            while (s.empty() || s.top() != it) {
                s.push(pushV[j++]);
                if (j >= m) break;
            }
            if (j >= m && s.top() != it)
                return false;
            s.pop();
        }
        return true;
    }
};