0 引言
题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出
序列。（注意：这两个序列的长度是相等的）
1 抽象问题具体化
举例1：序列1，2，3，4，5为某栈的压入顺序，判断4，5，3，2，1是否为该压栈序列对应的一个弹出序列。
可知4，5，3，2，1是该压栈序列对应的一个弹出序列
举例2：序列1，2，3，4，5为某栈的压入顺序，判断4，3，5，1，2是否为该压栈序列对应的一个弹出序列。
可知4，3，5，1，2不是该压栈序列对应的一个弹出序列。
2 具体问题抽象分析
根据压栈顺序以及出栈序列，对当前栈状态进行判断分析。
1）遍历出栈序列，访问数num；
2）根据num对辅助栈进行操作，将num之前的数入栈myStack，之后的数入队myQueue.
3）逐个遍历出栈序列中的数，分三种情况进行处理。
1. 当前数据在栈顶，继续访问出栈序列；
2. 当前数据不在栈顶，到队列中去找，没有找到，直接返回false;
3. 当前数据不在栈顶，到队列中去找，找到了，将该数在队列中的位置返回，并将该数之前的数出对入栈，将该数本身出队不入栈。
4）遍历完毕，表示所有的出战序列中的数均判读完毕合格，最后返回true.
3 demo
int FindNumInQueue(int num, queue<int> myQueue){ int position = -1; bool myBool = false; while(!myQueue.empty()){ if(myQueue.front() == num){ ++ position; myBool = true; break; } myQueue.pop(); ++ position; } if(myBool) return position; else return -1; } bool IsPopOrder(vector<int> pushV,vector<int> popV) { if(pushV.empty() || popV.empty()) return true; stack<int> myStack; // 入栈了的数 queue<int> myQueue; // 未入栈的数 int seprateIndex = -1; for(int i = 0; i<pushV.size();i++){ if(pushV[i] == popV[0]) seprateIndex = i; } for(int i = 0; i <= seprateIndex;i++) myStack.push(pushV[i]); for(int i = seprateIndex + 1; i < pushV.size();i++) myQueue.push(pushV[i]); // 遍历出栈序列，逐个判断 for(int i=0;i<popV.size();i++){ // 第一种情况：当前数据在栈顶，继续 bool myBool = false; if(!myStack.empty()){ if(popV[i] == myStack.top()) myStack.pop(); else myBool = true; } else myBool = true; if(myBool){ // 第二种情况：不在栈顶，去队列里边找，找不到，返回false int position = FindNumInQueue(popV[i],myQueue); if(position == -1) return false; // 第三种情况：不在栈顶，去队列里边找，找到了，将前边的出队并入栈 else{ for(int i = 0 ;i< position;i++){ myStack.push(myQueue.front()); myQueue.pop(); } myQueue.pop(); } } } return true; }
4 代码优化
代码逻辑存在冗余的地方，后边慢慢修改吧，一时之间没有什么思路。