程序员面试题精选100题(24)－栈的push、pop序列[数据结构] - 何海涛的日志 - 网易博客

程序员面试题精选100题(24)－栈的push、pop序列[数据结构] - 何海涛的日志 - 网易博客
题目：输入两个整数序列。其中一个序列表示栈的push顺序，判断另一个序列有没有可能是对应的pop顺序。为了简单起见，我们假设push序列的任意两个整数都是不相等的。
    比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。 

其实这个题目就直接模拟push和pop的过程即可 
有一个栈push_stack={1,2,3,4,5} , 一个栈pop_stack={4,5,3,2,1} 
一个空栈 temp 
http://mojijs.com/2015/07/198759/index.html
    public static boolean isCorrespondPopOrder(int[] pushArr, int[] popArr){
        if (pushArr.length != popArr.length){
            return false;
        }
        Stack<Integer> stack = new Stack<Integer>();
        int i = 0, j = 0;
        while (i < popArr.length){
            //入栈
            while (j < pushArr.length){
                stack.push(pushArr[j]);
                j++;
                if (pushArr[j-1] == popArr[i]){ // why j-1?
                    break;
                }
            }
            //出栈
            int top = stack.pop();           //获取栈顶元素
            while (i < popArr.length){
                //栈顶元素等于出栈序列当前元素，则继续出栈
                if (top == popArr[i]){
                    i++;
                    if (stack.isEmpty()){    //栈已空，跳出循环
                        break;
                    }
                    top = stack.pop();
                }
                //栈顶元素不等于出栈序列当前元素，恢复栈顶元素
                else {
                    stack.push(top);
                    break;
                }
            }
            //正确情况下，入栈已经完毕，那么出栈也完毕，因为入栈在出栈之前
            if (j == pushArr.length){
                break;
            }
        }
        return stack.isEmpty();
    }

http://www.haosearch.com/it-technology/2014-10-30-36683.html

bool IsPopOrder(const int* pPush, const int* pPop, int nLength)
{
    bool bPossible = false;

    if(pPush != NULL && pPop != NULL && nLength > 0)
    {
        const int* pNextPush = pPush;
        const int* pNextPop = pPop;

        std::stack<int> stackData;

        while(pNextPop - pPop < nLength)
        {
            // 当辅助栈的栈顶元素不是要弹出的元素
            // 先压入一些数字入栈
            while(stackData.empty() || stackData.top() != *pNextPop)
            {
                // 如果所有数字都压入辅助栈了，退出循环
                if(pNextPush - pPush == nLength)
                    break;

                stackData.push(*pNextPush);

                pNextPush ++;
            }

            if(stackData.top() != *pNextPop)
                break;

            stackData.pop();
            pNextPop ++;
        }

        if(stackData.empty() && pNextPop - pPop == nLength)
            bPossible = true;
    }

    return bPossible;
}

http://www.cnblogs.com/fxplove/articles/2500898.html

    stack<int> stk;
    int j = 0;
    for(int i = 0;i < 5;i++){
        stk.push(arr[i]);    
        if(stk.top()!=arr2[j])continue;
        while(stk.size()>0){
            if(stk.top() == arr2[j]){
                j++;
                stk.pop();
            }else break;
        }
    }
    if(stk.size()!=0){
        cout << "no" << endl;    
    }
    else cout << " yes " << endl;

Read full article from 程序员面试题精选100题(24)－栈的push、pop序列[数据结构] - 何海涛的日志 - 网易博客