题目描述

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

思路

我的第一反应是定义一个栈和一个队列，栈就用来进行题目中的进栈和弹出操作(称为主栈)，队列用来放弹出序列，可以先进先出(称为辅助队列)

• 先把弹出序列全部依次放入辅助队列(因为是队列，所以取出来的顺序就是原来的顺序)
• 比较主栈栈顶和辅助队列队头元素，如果相等就一起弹出，如果不相等就往主栈进行入栈操作
• 上面的循环直到把元素全部入栈后停止
• 但是有个问题，全部进栈之后还需要再比较栈顶元素和队头元素
• 最后以队列是否为空作为返回的答案

以上思路没有问题，但是我一开始考虑时没有注意一点(关于空栈的问题，空栈时候不能进行top操作，所以后来在循环条件中加入了不为空的条件)

代码

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        queue<int> Queue;  //定义一个队列用来放弹出序列
        stack<int> Stack;  //定义一个栈
        for(int i=0;i<popV.size();i++) //把弹出序列放入一个队列(先进先出)
        {
            Queue.push(popV[i]);
        }
        int j=0;
        while(j<pushV.size())      //遍历压栈序列，只要还有数没进行压栈就循环
        {
            if(!Stack.empty()&&Queue.front()==Stack.top()) //如果栈顶元素等于对头元素队列和栈都弹出
            {
                Queue.pop();
                Stack.pop();
            }
            else
                Stack.push(pushV[j++]);   //如果不等，就进栈
        }
         while(!Queue.empty()&&!Stack.empty()&&Queue.front()==Stack.top())  //这个是考虑全部进栈后的情况
            {
                Queue.pop();
                Stack.pop();
            }
        return Queue.empty();
    }
};