Javascript数据结构之栈和队列怎么实现

本篇内容主要讲解“Javascript数据结构之栈和队列怎么实现”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“Javascript数据结构之栈和队列怎么实现”吧!栈是一种具有 「后入先出」(Last-in-First-Out，LIFO) 特点的抽象数据结构。了解栈的样子，最常见的例子如：一摞盘子、一个压入子弹的弹夹。还有比如我们上网使用的浏览器，都有『后退』、『前进』按钮。后退操作，就是把当前正在浏览的页面（栈顶）地址出栈，倒退回之前的地址。我们使用的编辑类的软件，比如 IDE，Word，PhotoShop，他们的撤销（undo）操作，也是用栈来实现的，软件的具体实现代码可能会有比较大的差异，但原理是一样的。由于栈后入先出的特点，每次只能操作栈顶的元素，任何不在栈顶的元素，都无法访问。要访问下面的元素，先得拿掉上面的元素。所以它是一种高效的数据结构。用 Javascript 实现一个栈，通常我们用数组就可以。可以做一个简单的封装。栈通常需要实现下面常用功能：push（插入新元素，并让新元素成为栈顶元素）pop（栈顶元素出栈，并返回栈顶元素）peek（想知道栈最后添加的是哪个，用这个方法。返回栈顶元素，不出栈。是个辅助方法）clear（清空栈）isEmpty（若栈为空，返回 true，否则返回 false）size（返回栈元素个数）那么栈如何应用解决实际问题，下面是一个例子。一个十进制转换为二进制的例子：栈也被用于内存保存变量和方法调免费云主机域名用。函数调用的时候压栈，return 结果的时候，出栈。比如我们经常用的递归 （recursion） ，就是栈应用的例子。比如下面一个计算阶乘的例子：除了栈，队列也是一种常用的数据结构。队列是由顺序元素组成的线性数据结构，又不同于栈 （Last-in-First-Out，LIFO） ，他遵循的是先进先出（First-In-First-Out，FIFO） 。队列在队尾添加新元素，在顶部移除元素。现实中，最常见的队列例子就是排队。计算机中，队列应用也相当广泛。例如计算机 CPU 作业调度（Job Scheduling）、外围设备联机并发（spooling）、树和图的广度优先搜索（BFS）一个队列数据结构，主要是要实现两个操作：enqueue 把一个新元素推入队列dequeue 从队列中移除一个已有元素我们创建一个类来封装一个队列。我们可以使用 javascript 原生的数组来存储里面的数据内容，和 javascript 自带的函数来实现队列的操作。我们在遍历一颗树的时候，可以使用栈思路进行深度优先遍历，也可以采用队列的思路，广度优先遍历。假设我们有下面这样一个树形的数据结构，我们查找它所有的节点值。我们用队列进行广度优先的思路来遍历。代码和示意图如下：在实际情况中，有的队列需要一些特殊的处理方式，出队列规则的不一定是简单粗暴的最早进入队列最先出。 比如：医院对病人的分诊，重症的优先给予治疗我们销售某件商品时，可以按照该商品入库的进货价作为条件，进货价高的优先拿出销售。于是，就有了优先队列。优先队列是普通队列的一种扩展，它和普通队列不同的在于，队列中的元素具有指定的优先级别（或者叫权重）。 让优先级高的排在队列前面，优先出队。优先队列具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序。因为设置了一些规则，我们可以用顺序存储的方式来存储队列，而不是链式存储。换句话说，所有的节点都可以存储到数组中。满足上面条件，我们可以利用线性数据结构的方式实现，但时间复杂度较高，并不是最理想方式我们要实现优先队列，就会有两种方法。第一种，就是插入的时候，不考虑其他，就在队列末尾插入。而移除的时候，则要根据优先级找出队列中合适的元素移除。第二种是，插入元素的时候，根据优先级找到合适的放置位置，而移除的时候，直接从队列前面移除。下面以第二种情况为例，实现一个优先队列：上面是简单的使用一个线性数据结构，实现了一个优先队列。我们也可以用实现。这种堆数据存储的时候也是一个线性的，只是这些数据的存放位置有一定规则。堆可以理解为可以迅速找到一堆数中的最大或者最小值的数据结构堆是具有特殊特征的完全二叉树（也叫二叉堆）。二叉堆特点：它是一个完全二叉树（complete binary tree） 的数据结构。所谓完全二叉树（complete binary tree）,就是整个二叉树，除了底层的叶子节点，其他的层都是填满的，而且底层的叶子节点，从左到右不能有空的。（这样一个完全二叉树就能使用 Array 这种线性结构来存储）大顶堆（Max heap） ：父节点的值大于或者等于子节点的值，堆顶是这个堆的最大元素小顶堆（Min heap） ：父节点的值小于或者等于子节点的值，堆顶是这个堆的最小元素因为完全二叉树的特性，我们可以用一个数组来存储二叉堆二叉堆是实现堆排序和优先队列的基础。二叉堆常用的应用场景就是优先队列，它处理最大、最小值效率很高。同时堆排序算法也用到了二叉堆。二叉堆的插入和删除操作比较复杂，我们用 max-heap 举例说明。插入（enqueue）操作新元素一律先插入到堆的尾部依次向上调整整个堆的结构（一直到根即可）HeapifyUp删除（dequeue）操作取出顶部元素（因为它永远是最大那个）将尾元素替换到顶部（先不用管它的大小）依次从根部向下调整整个堆的结构（一直到堆尾即可）HeapifyDown下面是一个 max-heap 的实现。comparator 函数里面修改一下，就可以变成一个 min-heap如上面代码所示，数据进入队列是无序的，但在出队列的时候，总是能找到最大那个。这样也实现了一个优先队列。Scheduler 存在两个队列，timerQueue（未就绪任务队列） 和 taskQueue（就绪任务队列）。当有新的未就绪任务被注册，就会 push 到 timerQueue 中，并根据开始时间重新排列任务顺序。push 方法是在一个叫 schedulerMinHeap.js 的文件中基于最小堆（min-heap）来实现的。schedulerMinHeap 源码看到代码中，在 push 之后，调用了 siftUp 来重新整理顺序这里计算 parentIndex 是用了位移的方法（等价于除以 2 再去尾），帅！到此，相信大家对“Javascript数据结构之栈和队列怎么实现”有了更深的了解，不妨来实际操作一番吧！这里是百云主机网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！

相关推荐: Android热修复及插件化原理是什么

本篇内容介绍了“Android热修复及插件化原理是什么”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！热修复一直是这几年来很热门的话题，主流方案大致有两种，一种是…