基础进出栈问题

思路：

建立一个辅助栈，开始时，指针分别指向入栈数组pushV和出栈数组popV第一个元素，再让与当前出栈数组元素对应的入栈数组元素前的所有数入栈。此时栈顶元素与出栈数组元素相等，让栈顶元素出栈、出栈数组指针后移，继续判断直到不等。重复上述过程，直到入栈数组和出栈数组访问完毕，判断此时栈内是否还有元素。时间复杂度O(n)，空间复杂度O(n)。

进阶版《火车进站》>>题解。 
#include <stdbool.h>
bool IsPopOrder(int* pushV, int pushVLen, int* popV, int popVLen ) {
    // write code here
    int stack[pushVLen],top=-1,top_in=0,top_out=0;//建立辅助栈stack，top为栈顶指针，top_in为入栈数组pushV的指针,top_out为出栈数组popV的指针
    while(top_in<pushVLen && top_out<pushVLen){
        while(top_in<pushVLen && pushV[top_in]!=popV[top_out]){
            //与当前出栈数组元素对应的入栈数组元素前的所有数入栈
            stack[++top]=pushV[top_in++];
        }
        stack[++top]=pushV[top_in++];
        while(top>-1 && stack[top]==popV[top_out]){
            //栈顶元素若与出栈数组元素相等就出栈
            top--;
            top_out++;
        }
    }
    if(top!=-1){//栈不为空匹配失败
        return false;
    }
    return true;
}

优化：

分析代码可以看出：因为进栈数组指针不会回退，且不会出现出来的数比进去的数多的情况。因此可以直接把进栈数组当作辅助栈，在该数组上进行上述操作，这样可以节省一个额外的栈开销。时间复杂度O(n)，空间复杂度O(1)。

C: 

#include <stdbool.h>
bool IsPopOrder(int* pushV, int pushVLen, int* popV, int popVLen ) {
    // write code here
    int top=-1,top_in=0,top_out=0;//以pushV为辅助栈，top为栈顶指针，top_in为入栈数组pushV的指针,top_out为出栈数组popV的指针
    while(top_in<pushVLen && top_out<pushVLen){
        while(top_in<pushVLen && pushV[top_in]!=popV[top_out]){
            //与当前出栈数组元素对应的入栈数组元素前的所有数入栈
            pushV[++top]=pushV[top_in];
            top_in++;
        }
        pushV[++top]=popV[top_out];
        top_in++;
        while(top>-1 && pushV[top]==popV[top_out]){
            //栈顶元素若与出栈数组元素相等就出栈
            top--;
            top_out++;
        }
    }
    return top==-1?true:false;//栈不为空匹配失败
}

C++: 

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        int top=-1,top_in=0,top_out=0;
        while(top_in<pushV.size() && top_out<pushV.size()){
            while(top_in<pushV.size() && pushV[top_in]!=popV[top_out]){
                pushV[++top]=pushV[top_in];
                top_in++;
            }
            pushV[++top]=popV[top_out];
            top_in++;
            while(top>-1 && pushV[top]==popV[top_out]){
                top--;
                top_out++;
            }
        }
        return top==-1?true:false;
    }
};