剑指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>)

    {

        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,))

        printf("b是a的弹出序列\n");

    else

        printf("b不是a的弹出序列\n");

}

void main()

{

    int a[]={,,,,};

    int b[]={,,,,};

    int c[]={,,,,};

    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=;

        int sNextPop=;

        Stack<Integer> stack=new Stack<Integer>();

        if(sPush!=null||sPop!=null||length>){

            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={,,,,};

        int[] b={,,,,};

        int[] c={,,,,};

        IsPopOrder ipo=new IsPopOrder();

        if(ipo.isPopOrder(a, c, a.length))

            System.out.print("true");

        else

            System.out.print("false");

    }

}

巴特西

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

最新文章

热门文章