JavaScript数组实现数据结构中的队列与堆栈

一、队列和堆栈的简单介绍

1.1、队列的基本概念

  队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出!

  如下图所示:

1.2、堆栈的基本概念

  堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出!

  如下图所示:

  

二、 在JavaScript中实现队列和堆栈

  在JavaScript中实现队列和数组主要是通过数组,js数组中提供了以下几个方法可以让我们很方便实现队列和堆栈:

•shift:从数组中把第一个元素删除,并返回这个元素的值。

•unshift: 在数组的开头添加一个或更多元素,并返回新的长度

•push:在数组的中末尾添加元素,并返回新的长度

•pop:从数组中把最后一个元素删除,并返回这个元素的值。

2.1、实现队列

<script type="text/javascript">
//创建一个数组来模拟队列
var a=new Array();
console.log(a);
//unshift: 在数组的开头添加一个或更多元素,并返回新的长度
console.log("入队");
a.unshift()
console.log(a);//----->
a.unshift();
console.log(a);//----->,
a.unshift();
console.log(a);//----->,,
a.unshift();
console.log(a);//----->,,,
console.log("出队,先进先出");
console.log(a);
//pop:从数组中把最后一个元素删除,并返回这个元素的值
a.pop();//----->
console.log(a);
a.pop();//----->
console.log(a);
a.pop();//----->
console.log(a);
a.pop();//----->
console.log(a);
</script> 

  在google浏览器控制台输出的效果如下图所示:

  

2.2、实现堆栈

<script type="text/javascript">
//创建一个数组来模拟堆栈
var a=new Array();
console.log(a);
//push: 在数组的末尾添加一个或更多元素,并返回新的长度
console.log("入栈");
a.push()
console.log(a);//----->
a.push();
console.log(a);//----->,
a.push();
console.log(a);//----->,,
a.push();
console.log(a);//----->,,,
console.log("出栈,后进先出");
console.log(a);
//pop:从数组中把最后一个元素删除,并返回这个元素的值
a.pop();//----->
console.log(a);
a.pop();//----->
console.log(a);
a.pop();//----->
console.log(a);
a.pop();//----->
console.log(a);
</script> 

  在google浏览器控制台输出的效果如下图所示:

2.3、push方法和unshift方法的性能测试

  Array的push与unshift方法都能给当前数组添加元素,不同的是,push是在末尾添加,而unshift则是在开头添加,从原理就可以知道,unshift的效率是较低的。原因是,它每添加一个元素,都要把现有元素往下移一个位置。但到底效率差异有多大呢?下面来简单测试一下。

<script type="text/javascript">
/*
关于代码中"var s=+newDate();"的技巧说明
解释如下:=+这个运算符是不存在的;
+相当于.valueOf();
+new Date()相当于new Date().valueOf()
//个结果一样返回当前时间的毫秒数
alert(+new Date());
alert(+new Date);
var s=new Date();
alert(s.valueOf());
alert(s.getTime());
*/
var arr = [ ];
var startTime = +new Date(); //+new Date()相当于new Date().valueOf(),返回当前时间的毫秒数
// push性能测试
for (var i = ; i < ; i++) {
  arr.push(i);
}
var endTime = +new Date();
console.log("调用push方法往数组中添加个元素耗时"+(endTime-startTime)+"毫秒");
startTime = +new Date();
arr = [ ];
// unshift性能测试
for (var i = ; i < ; i++) {
  arr.unshift(i);
}
endTime = +new Date();
console.log("调用unshift方法往数组中添加个元素耗时"+(endTime-startTime)+"毫秒");
</script> 

  这段代码分别执行了100000次push和unshift操作,在Google浏览器运行一次,得到的结果如下图所示:

  可见,unshift比push要慢差不多100倍!因此,平时还是要慎用unshift,特别是对大数组。那如果一定要达到unshift的效果,可以借助于Array的reverse方法,Array的reverse的方法能够把一个数组反转。先把要放进数组的元素用push添加,再执行一次reverse,就达到了unshift的效果。比如:

<script type="text/javascript">
//创建一个数组来模拟堆栈
var a=new Array();
//使用push方法在数组的末尾添加元素
a.push()
a.push();
a.push();
a.push();
console.log("数组反转之前数组中的元素顺序");
console.log(a);//----->,,,
//Array有一个叫做reverse的方法,能够把一个数组反转。先把要放进数组的元素用push添加,再执行一次reverse,就达到了unshift的效果
a.reverse();//使用reverse方法将数组进行反转
console.log("数组反转之后数组中的元素顺序");
console.log(a);
</script> 

  在google浏览器控制台输出的效果如下图所示:

  从运行结果来看,数组元素的顺序已经反转过来了。

2.4、reverse方法的性能测试

  reverse的性能又如何呢,下面再来测试:

<script type="text/javascript">
var arr = [ ], s = +new Date;
for (var i = ; i < ; i++) {
   arr.push(i);
}
//调用reverse方法将数组里面的元素的顺序反转
arr.reverse();
console.log("调用reverse方法将数组里面的元素的顺序反转耗时:"+(+new Date - s)+"毫秒");
</script>

  在google浏览器控制台输出的效果如下图所示:

  从运行效果中可以看到,reverse方法的性能极高,可以放心使用。

  以上就是关于在javascript中通过数组来实现队列和堆栈的总结,并且简单测试了一下push、unshift、reverse这几个方法在操作大数组方面的性能优劣。

以上所述是小编给大家介绍的JavaScript数组实现数据结构中的队列与堆栈,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我们网站的支持!

(0)

相关推荐

  • JavaScript实现的链表数据结构实例

    此例是javascript来建立链表.. 并对此进行了排序.. 还可以在GenericList一般链表上进行扩展. 实现各种排序及增,删,改结点.. 复制代码 代码如下: function Node(){   this.data=null;   this.next=null; } function GenericList(){   this.head=null;   this.current=null;   //打出所有的链表结点   this.print= function(){   this

  • JavaScript数据结构之双向链表定义与使用方法示例

    本文实例讲述了JavaScript数据结构之双向链表定义与使用方法.分享给大家供大家参考,具体如下: 双向链表和普通链表的区别在于,在链表中,一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个元素,另一个链向前一个元素. 双向链表提供了两种迭代列表的方法:从头到尾,或者反过来.我们也可以访问一个特定节点的下一个或前一个元素.在单向链表中,如果迭代列表时错过了要找的元素,就需要回到列表起点,重新开始迭代.这是双向链表的一个优点. function DoubleLink(

  • JavaScript数据结构之链表的实现

    前面楼主分别讨论了数据结构栈与队列的实现,当时所用的数据结构都是用的数组来进行实现,但是数组有的时候并不是最佳的数据结构,比如在数组中新增删除元素的时候需要将其他元素进行移动,而在javascript中使用spit()方法不需要访问其他元素.如果你在使用数组的时候发现很慢,就可以考虑使用链表. 链表的概念 链表是一种常见的数据结构.它是动态地进行存储分配的一种结构.链表有一个"头指针"变量,以head表示,它存放一个地址,指向一个元素.每个结点都使用一个对象的引用指标它的后继,指向另一

  • javascript数据结构之双链表插入排序实例详解

    本文实例讲述了javascript数据结构之双链表插入排序实现方法.分享给大家供大家参考,具体如下: 数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入. 换成链表时,显然无需做这种大量移动,根据每个节点的前驱节点"指针",向前找到插入点后,直接把目标值从原链表上摘下,然后在插入点把链表断成二截,然后跟目标点重新接起来即可. <!doctype html> <html> <head> <t

  • js实现双向链表互联网机顶盒实战应用实现

    上实战代码: linkedlistnode.js 节点类 复制代码 代码如下: /* * 链表节点 */ Dare.LinkedListNode = function () { this.data = null;//数据域 this.prev = null;//前驱 this.next = null;//后驱 }; Dare.extend(Dare.LinkedListNode, Dare); Dare.LinkedListNode.prototype.getValue = function (

  • JavaScript数据结构和算法之图和图算法

    图的定义 图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合. 有向图 有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也成为弧(Arc),用有序偶<Vi,Vj>来表示,Vi称为弧尾,Vj称为弧头. 无序图 无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边(Edge),用无序偶(Vi,Vj)来表示. 简单图 简单图:在图结构中,若不存在顶点到其自身的边,且同一条边不重复出现,

  • javascript循环链表之约瑟夫环的实现方法

    前言 传说在公元1 世纪的犹太战争中,犹太历史学家弗拉维奥·约瑟夫斯和他的40 个同胞被罗马士兵包围.犹太士兵决定宁可自杀也不做俘虏,于是商量出了一个自杀方案.他们围成一个圈,从一个人开始,数到第三个人时将第三个人杀死,然后再数,直到杀光所有人.约瑟夫和另外一个人决定不参加这个疯狂的游戏,他们快速地计算出了两个位置,站在那里得以幸存.写一段程序将n 个人围成一圈,并且第m个人会被杀掉,计算一圈人中哪两个人最后会存活.使用循环链表解决该问题. 看到这个问题首先想到的是要用到循环链表,还有就是要计算

  • 使用JavaScript实现链表的数据结构的代码

    链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)   - 维基百科 上面是维基百科对 链表 的解读.下面我们用 JavaScript 代码对链表的数据结构进行实现 实现Node类表示节点 /** * Node 类用来表示节点 * element 用来保存节点上的数据 * next 用来保存指向下一个节点的链接 */ function Node(element) { this.elemen

  • JavaScript实现链表插入排序和链表归并排序

    本篇文章详细的介绍了JavaScript实现链表插入排序和链表归并排序,链表的归并排序就是对每个部分都进行归并排序,然后合并在一起. 1.链表 1.1链表的存储表示 //链表的存储表示 typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; 1.2基本操作 创建链表: /* * 创建链表. * 形参num为链表的长度,函数返回链表的头指针. */ Link

  • Node.js环境下JavaScript实现单链表与双链表结构

    单链表(LinkedList)的javascript实现 npmjs相关库: complex-list.smart-list.singly-linked-list 编程思路: add方法用于将元素追加到链表尾部,借由insert方法来实现: 注意各个函数的边界条件处理. 自己的实现: SingleNode.js (function(){ "use strict"; function Node(element){ this.element = element; this.next = n

  • js单向链表的具体实现实例

    复制代码 代码如下: function linkNode(_key, _value){    /// <summary>    /// 链表类的节点类    /// </summary>    this.Key = _key;    this.Value = _value;    this.next = null;}function Link(){    /// <summary>    /// 创建一个链表类    /// </summary>    th

  • JavaScript数据结构和算法之二叉树详解

    二叉树的概念 二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的.分别称为根结点的左子树和右子树的二叉树组成. 二叉树的特点 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点.二叉树中每一个节点都是一个对象,每一个数据节点都有三个指针,分别是指向父母.左孩子和右孩子的指针.每一个节点都是通过指针相互连接的.相连指针的关系都是父子关系. 二叉树节点的定义 二叉树节点定义如下: 复制代码 代码如下: struct

随机推荐