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

Myth丶恋晨 2022-08-04 04:12 92阅读 0赞

**题目：**输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列：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~ \*/