【剑指Offer】（栈和队列）栈的压入、弹出序列

太过爱你忘了你带给我的痛 2022-03-15 07:38 162阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&tqId=11174&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_d77d11405cc7470d82554cb392585106_tpId_13_tqId_11174_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

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

#### 解决方法 ####

class Solution { 
    public:
        bool IsPopOrder(vector<int> pushV,vector<int> popV) { 
            if(pushV.size()!=popV.size()) return false;
            int len=pushV.size();
            if(len==0) return true;
            
            stack<int> st; //建立一个辅助栈
            st.push(pushV[0]);
            int k=1;
            for(int i=0;i<len;i++){ 
                while(popV[i]!=st.top()) {  //如果栈顶元素不等于弹出数字，则将压入序列一次压入栈中，直至栈顶元素等于弹出数字
                    if(k==len) return false; //如果压入序列都压完了，还没找到弹出数字，则该序列不可能是一个弹出序列
                    st.push(pushV[k++]);
                }
                st.pop();
            }
            return true;
        }
    };

[https_www.nowcoder.com_practice_d77d11405cc7470d82554cb392585106_tpId_13_tqId_11174_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&tqId=11174&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking