题目：
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
思路：
直观的想法就是模拟第一个序列的数字依次入栈，并按照第二个序列依次弹出，如果第一个序列全部入栈，并最后栈中元素都被弹出来，就说明第二个序列是该栈的弹出顺序。
- 建立一个辅助栈；
- 将第一个序列的数字压入辅助栈；
- 如果第二个序列的下一个弹出数字刚好是栈顶数字，则直接弹出，第二个序列弹出当前数字，辅助栈也弹出该数字；
- 否则，就把第一个序列中尚未入栈的数字压入辅助栈，直到把第二个序列中下一个需要弹出的数字压入栈顶为止。
- 如果第一个序列的所有数字都已经入栈了，仍然没有找到下一个弹出的数字，那么第二个序列不可能是一个弹出序列。
代码：
#include <iostream>
#include <stack> using namespace std; bool IsPopOrder(const int* push,const int* pop,int length){
bool bPossible=false;
if(push!=NULL && pop!=NULL && length>0){
std::stack<int> stackData;
int i=0;
int j=0;
while(j<length){
while(stackData.empty() || stackData.top()!=pop[j]){
if(i>length-1)
break;
stackData.push(push[i]);
++i;
}
if(stackData.top()!=pop[j])
break;
stackData.pop();
++j;
}
if(stackData.empty() && j==length)
bPossible=true;
}
return bPossible;
} int main()
{
int A[]={1,2,3,4,5};
int B[]={4,5,3,2,1};
int length=sizeof(A)/sizeof(A[0]); cout << IsPopOrder(A,B,length) << endl;
return 0;
}
在线测试OJ：
http://www.nowcoder.com/books/coding-interviews/d77d11405cc7470d82554cb392585106?rp=1
AC代码：
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
int length=pushV.size();
if(pushV.size()>0 && popV.size()>0 && pushV.size()==popV.size()){
std::stack<int> stackData;
int i=0;
int j=0;
while(j<length){
while(stackData.empty() || stackData.top()!=popV[j]){
if(i>length-1)
break;
stackData.push(pushV[i]);
++i;
}
if(stackData.top()!=popV[j])
break;
stackData.pop();
++j;
}
if(stackData.empty() && j==length)
return true;
}
return false;
}
};