剑指offer(16)栈的压入、弹出序列

题目：

　　输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路：

　　添加一个辅助栈

　　我们将用上面一个指针，pNextPush，进行移动，每移动一次将里面的数压栈，直到栈顶与下面一个指针指向的数相同时停下，

（至于为什么pNextPush跑到5，详情见代码）

　　接下来我们弹栈，把下面一个指针pNextPop向前移动，发现不相等，那么我们就执行上面一步

以此类推，最后当我们得到pNextPop走到最后，而且栈为空时，我们就可以得出题设成立，接下来贴出一段书中不成立的例子，就不具体分析了

import java.util.ArrayList;

import java.util.Stack;

public class Solution {

    public boolean IsPopOrder(int [] pushA,int [] popA) {

     boolean bPossible = false;

        if(pushA.length==0&&popA.length==0)

            return bPossible;

            int pNextPush = 0;

            int pNextPop = 0;

            Stack stack = new Stack();

            while(pNextPop<pushA.length){

                while(stack.isEmpty()||(int)stack.peek()!=popA[pNextPop]){

					if(pNextPush==pushA.length)

                        break;

                    stack.push(pushA[pNextPush]);

                    pNextPush++;

                }

				if((int)stack.peek()!=popA[pNextPop])

					break;

                if(pNextPop<popA.length&&(int)stack.peek()==popA[pNextPop]){

                    int out = (int)stack.pop();

					System.out.println(out);

                    pNextPop++;

                }

            }

            if(stack.isEmpty()&&pNextPop==popA.length){

                bPossible = true;

            }

        return bPossible;

    }

}

　　这道题的判断条件非常值得推敲，第一个while:

　　 while(pNextPop<pushA.length)如果这里把它改成pNextPush<Length，那么我们的循环将会提前结束，也就是如下图情况

　　接下来还有中间的判断

    public boolean IsPopOrder(int [] pushA,int [] popA) {

        boolean bPossible = false;

        if(pushA.length==0&&popA.length==0)

            return bPossible;

            int pNextPush = 0;

            int pNextPop = 0;

            Stack stack = new Stack();

            while(pNextPop<pushA.length){

                while(stack.isEmpty()||(int)stack.peek()!=popA[pNextPop]){

		if(pNextPush==pushA.length)

                        break;

                    stack.push(pushA[pNextPush]);

                    pNextPush++;

                }

                if(pNextPop<popA.length&&(int)stack.peek()==popA[pNextPop]){

                    int out = (int)stack.pop();

                    pNextPop++;

                }

                /*这是我第一版的代码

            这里这么写主要是为了防止死循环，重新进入循环内第一个while

            然而这也导致了卡在了上图的时候，就直接跳出循环*/

		if(pNextPush==pushA.length)

			break;

            }

            if(stack.isEmpty()&&pNextPop==popA.length){

                bPossible = true;

            }

        return bPossible;

    }

 while(pNextPush<pushA.length){

                while(stack.isEmpty()||(int)stack.peek()!=popA[pNextPop]){

			if(pNextPush==pushA.length)

                        break;

                    stack.push(pushA[pNextPush]);

                    pNextPush++;

                }

                if(pNextPop<popA.length&&(int)stack.peek()==popA[pNextPop]){

                    int out = (int)stack.pop();

					System.out.println(out);

                    pNextPop++;

                }

/*这是第二版的循环体，显然不科学，当4弹出时，5还未进栈，条件成立，直接退出*/

		if((int)stack.peek()!=popA[pNextPop])

					break;

            }

巴特西

剑指offer(16)栈的压入、弹出序列

最新文章

热门文章