剑指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;
				
               
            }