JZ31 栈的压入                 、弹出序列

描述

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


 


 


 


 


 


 


 


 

，序列4,5,3,2,1是该压栈序列对应的一个弹出序列 
 
 
 
 
 
 
 
，但4,3,5,1,2就不可能是该压栈序列的弹出序列


 


 


 


 


 


 


 


 

。 1. 0<=pushV.length == popV.length <=1000 2. -1000<=pushV[i]<=1000 3. pushV 的所有数字均不相同

方法1 辅助栈（推荐使用）

思路：

题目要我们判断两个序列是否符合入栈出栈的次序  
   
   
   
   
   
   
   
   ，我们就可以用一个栈来模拟 
 
 
 
 
 
 
 
。对于入栈序列

 

 

 

 

 

 

 

 
，只要栈为空
 

 

 

 

 

 

 

 

，序列肯定要依次入栈  
   
   
   
   
   
   
   
   。那什么时候出来呢？自然是遇到一个元素等于当前的出栈序列的元素                 ，那我们就放弃入栈
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 ，让它先出来

 

 

 

 

 

 

 

 
。 //入栈：栈为空或者栈顶不等于出栈数组 while (j < n && (q.isEmpty() || q.peek() != popA[i])) { q.push(pushA[j]); j++; } 如果能按照这个次序将两个序列都访问完
















，那说明是可以匹配入栈出栈次序的
 

 

 

 

 

 

 

 

。 具体做法： step 1：准备一个辅助栈                         ，两个下标分别访问两个序列                 。 step 2：辅助栈为空或者栈顶不等于出栈数组当前元素
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ，就持续将入栈数组加入栈中
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 。 step 3：栈顶等于出栈数组当前元素就出栈
















。 step 4：当入栈数组访问完
























，出栈数组无法依次弹出                 ，就是不匹配的
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 ，否则两个序列都访问完就是匹配的                         。

代码

public boolean IsPopOrder(int[] pushA, int[] popA) { Stack<Integer> q = new Stack<>(); int n = pushA.length; //记录进栈位置 int j = 0; for (int i = 0; i < n; i++) { while (j < n && (q.isEmpty() || q.peek() != popA[i])) { q.push(pushA[j]); j++; } if (q.peek() == popA[i]) q.pop(); else return false; } return true; }

方法2 原地栈（扩展思路）

思路：

方法一我们使用了一个辅助栈来模拟
















，但是数组本来就很类似栈啊  
  
  
  
  
  
  
  
 ，用下标表示栈顶
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 。在方法一种push数组前半部分入栈了 
  
  
  
  
  
  
  
  ，就没用了


 


 


 


 


 


 


 


 

，这部分空间我们就可以用来当成栈
























。原理还是同方法一一样 
 
 
 
 
 
 
 
，只是这时我们遍历push数组的时候  
   
   
   
   
   
   
   
   ，用下标n表示栈空间

 

 

 

 

 

 

 

 
，n的位置就是栈顶元素                 。 具体做法： step 1：用下标n表示栈空间
 

 

 

 

 

 

 

 

，用j表示出栈序列的下标
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 。 step 2：遍历每一个待入栈的元素                 ，加入栈顶
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 ，即push数组中n的位置
















，同时增加栈空间的大小                         ，即n的大小
















。 step 3：当栈不为空即栈顶n大于等于0
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ，且栈顶等于当前出栈序列
























，就出栈                 ，同时缩小栈的空间
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 ，即减小n  
  
  
  
  
  
  
  
 。 step 4：最后若是栈空间大小n为0
















，代表全部出栈完成  
  
  
  
  
  
  
  
 ，否则不匹配 
  
  
  
  
  
  
  
  。

代码

package mid.JZ31栈的压入弹出序列; import java.util.Stack; public class Solution { public boolean IsPopOrder(int[] pushA, int[] popA) { //初始化栈 int n = 0; //出栈元素位置 int j = 0; for (int i = 0; i < popA.length; i++) { //当前push元素入栈 pushA[n] = pushA[i]; //出栈 while (n >= 0 && pushA[n] == popA[j]){ n--; j++; } n++; } return n == 0; } /*public boolean IsPopOrder(int[] pushA, int[] popA) { Stack<Integer> q = new Stack<>(); int n = pushA.length; //记录进栈位置 int j = 0; for (int i = 0; i < n; i++) { while (j < n && (q.isEmpty() || q.peek() != popA[i])) { q.push(pushA[j]); j++; } if (q.peek() == popA[i]) q.pop(); else return false; } return true; }*/ }