剑指offer——栈的压入、弹出序列

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

思路：主要是栈的压入和弹出序列

借用大神链接：

https://www.cnblogs.com/edisonchou/p/4779755.html

为此我们加入一个辅助栈，在将压入顺序矩阵依次压入辅助栈的同时，判断其栈顶元素是否是弹出序列的栈顶元素，若是，则将辅助栈的栈顶元素弹出，并将弹出序列的待判断数向后移一位。若辅助矩阵不为空，则继续判断辅助矩阵栈顶元素是否和弹出序列的待判断数相同，若相同，则继续弹出辅助矩阵，若不相同，则将压入序列继续压入辅助矩阵。

当弹出序列被遍历完成，且辅助矩阵为空，则匹配成功。

 import java.util.ArrayList;

 import java.util.Stack;

 //首先判断是否为空，若为空则返回错误

 //采用辅助栈的方法来对栈进行操作

 //将push中的元素依次压入辅助栈中，压入一个则将其与pop中的元素进行比较，如相等，则将辅助栈中该元素弹出

 //之后再将pop中需要判断的元素向后推一个，并与辅助栈中元素对比，相等则继续弹出，不相等，则将push中元素继续压入辅助栈，并进行对比

 //直到pop栈中元素遍历结束，若此时辅助栈不为空，则返回false，否则返回true

 public class Solution {

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

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

           return false;

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

         int popIndex = 0;//用于标识弹出序列的位置

         for(int i = 0;i<popA.length;i++){

             s.push(pushA[i]);

             //如果栈顶元素不为空，且其和弹出序列相同

             while(!s.empty() &&s.peek() == popA[popIndex]){

                 s.pop();

                 popIndex++;

             }

         }

         return(s.empty());

     }

 }

在对上述程序进行验证的过程中，我发现当pushA的大小大于popA时，也会输出true，这说明题目中假定两个序列长度相同，就代表我们不需要对序列长度再次进行判断。

     public static void main(String [] args) {

         Solution1 x = new Solution1();

         int [] pushA = {1,2,3,4,5,6};

         int [] popA = {4,5,3,2,1};

         System.out.println(x.IsPopOrder(pushA,popA));

     }

此时依旧返回True.开心，自己看出并验证出的小发现。

巴特西

剑指offer——栈的压入、弹出序列

最新文章

热门文章