【刷算法】栈的压入、弹出序列

CarlBenjamin 发布于2019-08-22 18:17 / 1279人阅读

摘要：题目描述输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

题目描述

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

分析

其实该题就是考察一个进栈序列能否和一个出栈序列对应起来，但是棘手的地方在于：一个进栈序列可能会有多个出栈的顺序，所以还是得好好想一想。

可以从一个简单的例子开始：

序列A：1,2,3

序列B：2,3,1

1先进栈，B序列中未出栈的第一个数字是2，说明此时1不能再接着出栈；

2再进栈，B序列中未出栈的第一个数字是2，说明第一个出栈的数字是2，那么2就此出栈；

此时栈顶元素为1，B序列中未出栈的第一个数字是1，说明1是自2出栈后的再一个出栈元素，那么1就此出栈，此时栈为空；

3继续进栈，此时B序列的中未出栈的第一个数字是3，说明3是再一个出栈元素，那么3就此出栈，此时栈为空，序列A也全都进栈完毕了；

栈空了，序列A也进栈完毕了，说明B就是A的弹出序列。

代码实现

接着这个思路，可以试着写代码了

function IsPopOrder(pushV, popV)
{
    if(pushV.length === 0 || popV.length === 0 || pushV.length !== popV.length)
        return false;
    // 进栈序列和出栈序列分别有一个指针，从头开始
    var curPushIndex = 0, curPopIndex = 0;
    var stack = [];
    
    for(;curPushIndex < pushV.length;curPushIndex++) {
        
        stack.push(pushV[curPushIndex]);
        while(curPopIndex < popV.length && stack[stack.length-1] === popV[curPopIndex]){
        // 栈顶元素和当前popIndex指向的数字一样的话，stack弹出栈顶元素，且当前popIndex指向pop序列的下一个数字
            stack.pop();
            curPopIndex++;
        }
    }
    // 栈中元素没有全部弹出，说明两个序列并不匹配，否则，就是匹配
    return stack.length === 0;
}

云服务器 GPU云服务器最大功序列算法 php 压入 web服务器的压测全栈的

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

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

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

摘要：题目描述输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。指向压栈序列的指针指向弹栈序列的指针储存压栈序列的辅助空间第一次遍历把压栈序列放入辅助空间中如果有相等的就让弹栈序列指针。 1.题目描述输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压...

Zhuxy 2019-08-19 10:11 评论0 收藏0
【剑指offer】让抽象问题具体化

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

Keagan 2019-08-23 15:15 评论0 收藏0
Java数据结构与算法[原创]——栈

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

hiyang 2019-08-19 10:42 评论0 收藏0
栈的实现原理

摘要：使用栈实现字符串逆序将字符串反转用两个栈实现队列用两个栈来实现一个队列，完成队列的和操作。假设栈中有个元素，基于简单数组实现的栈。可以看到栈是实现，其实底层也是用数组来实现的。移除此堆栈顶部的对象，并将该对象作为此函数的值返回。目录介绍 01.栈由简单数据实现 1.1 简单数组代码实现 1.2 可能出现问题 1.3 性能和局限性 02.栈由动态数组实现 2.1 基于简单...

soasme 2019-08-19 11:35 评论0 收藏0
2019秋招知识盲点总结

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

Doyle 2019-08-23 11:52 评论0 收藏0