剑指OFFER面试题22：判断栈的压入和弹出

前提摘要

先从弹出序列入手，获取中途弹出的元素（即弹出序列中排在前面的元素），不把这些中途弹出的元素压入栈，其它元素按照压入序列的次序进栈。若遇到某次弹出多个元素则需将元素出栈。当所有元素进栈完成后，比较弹出序列后面的元素是否和出栈次序相同。

排除

若入栈完成后未找到与弹出序列相同的元素则返回false
若出栈过程中弹出序列已经遍历完或中途不相同则返回false

bool isPushAndPoP(int in[],int out[],int n){
    if(in==NULL || out == NULL || n<=0 ) return false;
    stack<int> sData;
    int i,j=0;
    for(i=0;i<n;i++){
        while(in[j]!=out[i]){
            sData.push(in[j++]);
            if(j==n) return false;  //no same element in in[]
        }
        //at this moment in[j]==out[i]
        int k=j-1;
        while(k>=0 && in[k]==out[i+1]){
            sData.pop();
            k--;i++;
        }
        if(++j==n) break;   
    }
    while(!sData.empty()){
        if(out[++i]!=sData.top() || i==n) return false;
        sData.pop();
    }
    return true;
}

上面思维比较混乱，实际上关键在遍历弹出序列，比较当前元素和栈顶元素即可：
1.相等，则应出栈
2.不相等，则栈里继续压入元素

反思

1、没有利用好栈顶元素，只想着减少进出栈操作
2、没有耐心画图，将问题具体化