栈的压进、弹出序列（剑指offer）

栈的压入、弹出序列（剑指offer）

栈的压入、弹出序列

参与人数：1430时间限制：1秒空间限制：32768K
通过比例：22.97%
最佳记录：0 ms|0K（来自 oneyear）

题目描述

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

链接：http://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

就是一个栈的应用吧！思路是：如果要弹出的数是要压入的数的话，就不压入栈；如果，序列1还有数就入栈，然后接着判断。。。这里我WA了一次，原因是当序列1和序列2都为空的时候，输出false；。。。这里如果是面试可以面试官讨论！

#include<stdio.h>
#include<vector>
#include<stack>
using namespace std;

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> st;
        int lenin=pushV.size();
        int lenout=popV.size();
        if(!lenin || !lenout) return false;/***不要忘记空的情况**/
        int i,j;
        i=j=0;
        while(j<lenout)
        {
            if(i==lenin && !st.empty() && st.top()!=popV[j]){break;}
 //           if(!st.empty()) ans=st.top();
            if(i!=lenin && (popV[j]!=pushV[i] || (!st.empty() && st.top()!=popV[j])))
            {
                st.push(pushV[i]);
                i++;
            }
            if(popV[j]==pushV[i]) {j++;i++;}
            if(!st.empty() && st.top()==popV[j])
            {
                st.pop();
                j++;
            }
        }
        if(st.empty()) return true;
        else return false;
    }
};
int main()
{
    int n;
    scanf("%d",&n);
    vector<int> p;
    vector<int> q;
    int tp;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&tp);
        p.push_back(tp);
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&tp);
        q.push_back(tp);
    }
    Solution so;
    printf("%s\n",so.IsPopOrder(p,q)?"yes":"No");
}
/*
测试用例:
[],[]

对应输出应该为:
false
*/

栈的压进、弹出序列（剑指offer）

题目描述

相关推荐