剑指offer_面试题22_栈的压进、弹出序列（总结规律）

剑指offer_面试题22_栈的压入、弹出序列（总结规律）

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

直观想法：建立一个辅助栈，把输入的第一个序列中的数字依次压入栈，并按照第二个序列的顺序依次从该栈中弹出数字。

总结规律：

1、如果下一个要弹出的数字刚好是栈顶元素，那么直接弹出

2、如果下一个要弹出的数字不在栈顶，那么把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字数字压入栈顶为止

3、如果所有数字都压入栈了，仍然没有找到下一个需要弹出的数字，那么这个序列不可能是一个弹出序列

4、如果要弹出的数字全部弹出了，则该序列是弹出序列

算法如下：

bool IsPopOrder(const int *pPush, const int *pPop, int nLength)
{
    bool bPossible = false;                             /**在返回类型是 bool 类型的时候，可以设置这样一个变量*/

    if(pPush != NULL && pPop != NULL && nLength > 0)    /**也可以这样写，表示传进来的指针为空的情况，直接跳过if返回false*/
    {
        const int *pNextPush = pPush;                   /*指向压栈序列*/
        const int *pNextPop = pPop;                     /*指向弹出序列*/

        stack<int> stackData;

        while(pNextPop - pPop < nLength)            /**什么情况下，表示要开始一项工作了*/
        {
            while(stackData.empty() || stackData.top() != *pNextPop)   /**什么情况下，该压栈*/
            {
                if(pNextPush - pPush == nLength)
                    break;

                stackData.push(*pNextPush);
                pNextPush++;
            }

            if(stackData.top() != *pNextPop)    /**什么情侣下，表示该序列不是弹出系列*/
                break;

            stackData.pop();                  /**什么情况下，该出栈*/
            pNextPop++;
        }
        if(stackData.empty() && pNextPop - pPop == nLength)    /**什么情侣下，表示确认是弹出系列*/
            bPossible = true;
    }

    return bPossible;
}

总结：

算法 与 规律 是对应的，从上面的代码也可以看出，因此 在解题时，不仅要通过一步步分析明白这个过程，还总结相关规律，这些规律，就是相应的判断条件。

/* 点滴积累，我的一小步O(∩_∩)O~ */