判断是否为栈的弹出顺序

---

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相同。

例如序列1，2，3，4，5是某栈的压入顺序，序列4，5，3，2，1是该压栈序列对应的一个弹出序列，但是4，3，5，1，2就不可能是该压栈序列的弹出序列。

解题思路

设一个辅助栈S，用来判断。

• 若栈A为空，则直接把压入序列A的第一个元素压入栈S。

• 将压入序列A的元素依次压入栈S中；

  • 若栈S的栈顶元素与弹出序列B的第一个元素相等，则弹出栈S中的元素，弹出序列B移动到下一个元素；

• 然后判断辅助栈S是否为空，若为空则序列B是弹出顺序；否则不是。

代码

class Solution
{
public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV)
    {
        if  (pushV.size() == 0)
            return false;
        int num = pushV.size();
        int j = 0;
        for (int i = 0; i < num; i++)
        {
            A.push(pushV[i]);
            while (j < popV.size() && A.top() == popV[j]) // &&两边的内容不可替换
            {
                A.pop();
                j++;
            }
        }
        return A.empty();
    }
private:
    stack<int> A;
};

当while()语句的判断条件中&&两边内容互换后，会出现数组越界的现象。因为只有当 j不大于 popV数组中的个数时，才能进行popV[j]的操作。

---

参考链接：https://cuijiahua.com/blog/2017/12/basis_21.html