剑指offer-第四章解决面试题的思路（栈的压入和弹出序列）

题目：输入两个整数序列，第一个序列表示栈的压入序列，请判断第二个序列是否为弹出序列。

思路：定义两个指针sPush和sPop分别指向两个整数序列的开头，借助一个辅助的栈，将第一个序列的数据依次压入栈中，直到压入栈中的数据和第二个栈中sPop所指向的数据相等，就将这个数据弹出栈。sPop指向下一个数字。重复上述过程。直到sPop等于序列的长度并且栈为空。

将抽象的问题具体化的过程如下：

C++代码：

#include<iostream>
#include<stack>

bool isPopOrder(const int* sPush,const int* sPop,int nLength)
{
    bool isPopOrder=false;
    if(sPush!=NULL&&sPop!=NULL&&nLength>0)
    {
        const int* pNextPush=sPush;
        const int* pNextPop=sPop;
        std::stack<int> stack;
        while(pNextPop-sPop<nLength)
        {
            while(stack.empty()||*pNextPop!=stack.top())
            {
                if(pNextPush-sPush==nLength)
                break;
                stack.push(*pNextPush);
                pNextPush++;
            }
            if(stack.top()!=*pNextPop)
                break;
            stack.pop();
            pNextPop++;

        }
        if(stack.empty()&&pNextPop-sPop==nLength)
            isPopOrder=true;
    }
    return isPopOrder;
}
void test(const int* a,const int * b)
{
    if(isPopOrder(a,b,5))
        printf("b是a的弹出序列
");
    else
        printf("b不是a的弹出序列
");
}
void main()
{
    int a[]={1,2,3,4,5};
    int b[]={4,3,5,1,2};
    int c[]={4,5,3,2,1};
    test(a,b);
    test(a,c);

}

Java代码：

import java.util.Stack;
public class IsPopOrder {
    public boolean isPopOrder(int[] sPush,int[] sPop,int length){
        boolean isPop=false;
        int sNextPush=0;
        int sNextPop=0;
        Stack<Integer> stack=new Stack<Integer>();
        if(sPush!=null||sPop!=null||length>0){
            while(sNextPop<length){
                while(stack.empty()||stack.peek()!=sPop[sNextPop])
                {
                    if(sNextPush==length)
                        break;
                    stack.push(sPush[sNextPush]);
                    sNextPush++;
                }
                if((int)stack.peek()!=sPop[sNextPop])
                    break;
                stack.pop();
                sNextPop++;
            }
            if(stack.isEmpty()&&sNextPop==length){
                isPop=true;
            }
        }
        return isPop;
    }
    public static void main(String[] args)
    {
        int[] a={1,2,3,4,5};
        int[] b={4,5,3,2,1};
        int[] c={4,5,3,1,2};
        IsPopOrder ipo=new IsPopOrder();
        if(ipo.isPopOrder(a, c, a.length))
            System.out.print("true");
        else
            System.out.print("false");
    }
}