剑指offer 面试题22：栈的压入、弹出序列
参与人数：3413 时间限制：1秒 空间限制：32768K
本题知识点：栈
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
分析：
当无法解决抽象问题时，应该给出正面和反面的实例来分析问题，发现规律。
要判断一个输入序列按照顺序压栈出栈，能否得到一个给定的输出序列？
那么我们需要一个辅助栈，来按照给定输出序列的顺序，将输入序列顺序入栈。
例如：
◆当1,2,3,4,5是某栈的压入顺序时，判断4,5,3,2,1 是否可能是其相应的弹出序列?
第一个希望弹出4，则4应该在栈顶，而压入4之前，1,2,3已经入栈。4出栈后，希望弹出5, 5不在栈顶，继续压入输入直至栈顶为5，弹出 5；希望弹出3，发现3在栈顶，弹出3；希望弹出2,1，发现都在栈顶。则该序列是一个弹出序列。
◆当1,2,3,4,5是某栈的压入顺序时，判断4,3,5,1,2 是否可能是其相应的弹出序列?
第一个希望弹出4，则4应该在栈顶，而压入4之前，1,2,3已经入栈。4出栈后，希望弹出3，发现3在栈顶，弹出 3；希望弹出5, 5不在栈顶，继续压入输入直至栈顶为5，弹出 5；希望弹出1，发现1不在栈顶，继续压入输入，发现已无输入。则该序列不是一个弹出序列。
总结如下：
判断一个 序列是否是一个栈的弹出序列的规律：
如果下一个希望弹出的数字刚好是栈顶数字，则直接弹出；如果下一个数字不在栈顶，我们把压栈序列中还没有入栈的数字压入栈，直至把下一个需要弹出的数字压入栈顶为止。如果所有数字已入栈，仍没有找到下一个要弹出的数字，那么该序列不是一个弹出序列。
<注>：上述解析参考了《剑指offer》2014纪念版
AC代码：
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
if(pushV.size() == 0 || popV.size() == 0)
return false; // 如果其中一个序列长度为0，则不合题意，返回false
stack<int> s;
int k=0;
for(int i=0;i<pushV.size();i++)
{
if(pushV[i] != popV[k])
{
s.push(pushV[i]); // 压栈，直至栈顶元素等于输出队列
}
else {
k++;
while (!s.empty() && s.top()==popV[k])
{
s.pop(); // 输出序列和栈顶一致，继续
k++;
}
}
}
if(k==popV.size()) return true; // 压完所有输入后，相等，判断结果为：是出栈序列
return false; // 仍不等，则判断结果为：不是出栈序列
}
};
// 以下为测试部分
/*
int main()
{
Solution sol;
int in[] = {1,2,3,4,5};
int a[] = {4,5,3,2,1};
int b[] = {4,3,5,1,2};
vector<int> invec(in,in+5);
vector<int> vec1(a,a+5);
vector<int> vec2(b,b+5);
//vector<int> invec(0);
//vector<int> vec1(0);
//vector<int> vec2(0);
cout<<"Is the sequence possible pop order ?: "<<sol.IsPopOrder(invec,vec1)<<endl;
cout<<"Is the sequence possible pop order ?: "<<sol.IsPopOrder(invec,vec2)<<endl;
return 0;
}
*/