剑指offer：栈的压入、弹出序列（Java）

Zhuxy 发布于2019-08-19 10:11 / 3430人阅读

摘要：题目描述输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。指向压栈序列的指针指向弹栈序列的指针储存压栈序列的辅助空间第一次遍历把压栈序列放入辅助空间中如果有相等的就让弹栈序列指针。

1.题目描述

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

2.思路

首先要理解为什么栈的压入顺序一定的情况下却可以有不同的弹出顺序，就是在栈的压入过程中可以向外弹元素，不一定是全部元素进栈才开始向外弹栈，所以会产生不同的弹栈顺序。
1.题目给的是ArrayList，使用这个作为辅助空间
然后就是借助一个辅助空间，将压栈的序列储存起来，储存过程中判断是否和弹栈序列一致，如果一致就让弹栈序列指向后一位，等压栈序列全部进辅助空间后，在开始反向遍历一次，因为题目说明没有重复元素，所以进辅助空间过程中判断过的元素可以重复判断，不会出错，遍历过程中判断是否和弹栈序列元素相等，相等就弹栈序列指向后一位，并且辅助空间也指向下一个元素，不相等就只让辅助空间指向下一个元素，这样反向遍历完辅助空间后如果弹栈序列没有走到最后，就说明不是正确的弹栈序列，如果走到了最后就是正确序列。

import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length == 0 || popA.length == 0)
            return false;
        int i = 0;    //指向压栈序列的指针
        int j = 0;    //指向弹栈序列的指针
        ArrayList helpList = new ArrayList<>();    //储存压栈序列的辅助空间
        while(i < pushA.length){    //第一次遍历把压栈序列放入辅助空间中
            helpList.add(pushA[i]);    
            if(helpList.get(i) ==  popA[j]){    //如果有相等的就让弹栈序列指针++。
                j++;
            }
            i++;
        }
        i = i-1;    //这里是细节，最后i=pushA.length所以要-1.
        while(i>= 0 && j < popA.length){    //i>=0也是细节，如果只是大于0，0位置的元素就没办法判断了。
            if(helpList.get(i)== popA[j]){    
                i--;
                j++;
            }else{
                i--;
            }
        }
        return j == popA.length ? true:false;    //根据弹栈序列的指针是否走到最后判断是不是弹栈序列。
    }
}

2：使用Stack

使用栈结构的好处就是可以省去上面方法过程中的重复判断，因为可以判断到一个相等就直接弹出。

import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length == 0 || popA.length == 0)
            return false;
        Stack temp = new Stack<>();
        int popIndex = 0;
        for(int i = 0 ; i < pushA.length; i++){
            temp.push(pushA[i]);
            while(!temp.isEmpty() && temp.peek() == popA[popIndex]){
                temp.pop();
                popIndex++;
            }
        }
        return temp.isEmpty();
    }
}

方法2参考：Alias

私有云海外云主机栈的java描述 java 栈的应用 java栈的深度 java栈的源代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/75592.html

【剑指offer】让抽象问题具体化

摘要：假设压入栈的所有数字均不相等。注意这两个序列的长度是相等的思路借助一个辅助栈来存储数据。当所有数据入栈完成，如果出栈顺序正确，那么辅助栈应该为空。若存在，左右子树，递归检测左右子树是否复合规范。 1.包含min函数的栈定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。思路 1.定义两个栈，一个栈用于存储数据，另一个栈用于存储每次数...

Keagan 2019-08-23 15:15 评论0 收藏0
【刷算法】栈的压入、弹出序列

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

CarlBenjamin 2019-08-22 18:17 评论0 收藏0
2019秋招知识盲点总结

摘要：实际上是一个让出线程的标志遇到会立即返回一个状态的。一个简单的防抖函数如果定时器存在则清除重新开始定时执行缺点只能在最后执行，不能立即被执行，在某些情况下不适用。假设压入栈的所有数字均不相等。接收数据不受同源政策限制。开始尽管秋招还没有拿到offer（好难过），但是一些知识点还是要总结的，既然自己选了这条路，那就一定要坚定不移的走下去...... 注意 new 运算符的优先级 fu...

Doyle 2019-08-23 11:52 评论0 收藏0
剑指offer/LintCode494_用两个队列实现一个栈

摘要：剑指用两个队列实现一个栈声明文章均为本人技术笔记，转载请注明出处解题思路实现功能用两个队列实现一个栈，实现，，和方法解题思路假设有队列和实现栈的操作实现栈操作始终用来入队实现实现栈的方法模拟栈的过程中，保证两个队列中始终有一个队列为空，另一剑指offer/LintCode494_用两个队列实现一个栈声明文章均为本人技术笔记，转载请注明出处https://segmentfault....

rose 2019-08-14 18:10 评论0 收藏0
Java数据结构与算法[原创]——栈

摘要：前言数据结构与算法专题会不定时更新，欢迎各位读者监督。方法调用编写的程序在进行方法函数调用时，会完成对方法的压栈操作，等方法执行结束后，对应的会完成对方法的弹栈操作。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本文介绍数据结构中的栈的概念、存储结构、栈的特点以及栈的适用场景，另外会穿插介绍面试中的一些经典问题...

hiyang 2019-08-19 10:42 评论0 收藏0