前言
数据结构就是关系,没错,就是数据元素相互之间存在的一种或多种特定关系的集合。
常用的数据结构有:
数组,队列(queue),堆(heap),栈(stack),链表(linked list ),树(tree),图(graph)和散列表(hash)
本文主要介绍的是数组、栈与队列,下面来一起看看详细的介绍吧。
一、数组
数组是平时使用最常用的数据结构,在JavaScript中数组是动态的分配大小,在这里我不会介绍JavaScript里面数组的所有的方法,而是针对数据结构这个方向谈谈所用到的方法。
创建和初始化数组
//创建空数组 var array = new Array(); //[] //初始化数组 var array = new Array(1,2,3); var array = Array.of(1,2,3);//ES6的方法 //[1,2,3] //创建大小为5的数组 var array = new Array();//ES6的方法 //[undefined,undefined,undefined,undefined,undefined] //给数组赋值 var array = new Array(); array[0] = 1 ; array[1] = 2 ; array[2] = 3 ; //[1,2,3]
添加元素
往数组后添加元素
var number = [1,2,3]; number[number.length] = 4; //[1,2,3,4] //或者 var number = [1,2,3]; number.push(4); //[1,2,3,4]
往数组前面添加元素
var number = [1,2,3]; number.unshift(0); //[0,1,2,3] number.unshift(-2,-1); //[-2,-1,0,1,2,3]
往数组的任意位置插入元素
运用splice方法
//在索引1后面添加2,3,4 var number = [1,5,6]; number.splice(1,0,2,3,4); //[1,2,3,4,5,6]
删除元素
删除第一位
var number = [1,2,3]; number.shift(); //[2,3]
删除任意位置
使用splice方法删除数组任意位置的元素
var numebr = [1,2,3,4,5,6]; //如果想删除元素3 number.splice(2,1); //[1,2,4,5,6] //如果想删除元素4,5 number.splice(3,2);
排序
反序
var number = [3,2,1]; number.reverse(); //[1,2,3]
自然排序
var numebr = [2,3,4,1,3,7]; number.sort(); //[1,2,3,3,4,7]
自定义排序
这个自定义排序跟java里面实现comparator接口一个意思。用处可大了。
var number = [4,5,6,7,1,2,3,8,9,10,11,12,13]; number.sort(); //[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
仿佛看起有点不对啊,我们应该想要的是
[1,2,3,4,5,6,7,8,9,10,11,12,13],这个时候我们就用自定义排序来解决这个问题
var number = [4,5,6,7,1,2,3,8,9,10,11,12,13]; function compare(a,b){ if(a < b){ return -1; } if(a > b){ return 1; } return 0; } number.sort(compare); //[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
这还只是最简单的,也可以对任何对象类型进行数组排序。例如,对象Person有名字和年龄属性,我们希望根据年龄排序
var friends = [{name:'李晨',age:40},{name:'范冰冰',age:35}]; function comparePerson(a,b){ if(a.age < b.age){ return -1; } if(a.age > b.age){ return 1; } return 0; } friends.sort(comparePerson); //[{name:'范冰冰',age:35},{name:'李晨',age:40}]
搜索
搜索有两个方法:indexOf方法返回与参数匹配的第一个元素的索引,lastIndexOf返回与参数匹配的最后一个元素的索引。
var number = [1,3,4,3,56,6,7,4]; number.indexOf(3);//1 number.lastIndexOf(3)//3
二、栈
栈是一种遵循后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。在JavaScript中变量保存和函数调用都是用栈存储的。
首先创建一个类来表示一个栈,需要一种数据结构来保存栈里的元素。这里我们就选择刚学的数组:var items = [];
接下来,为我们的栈声明一些方法:
如果上一节数组认真看了,我相信用JavaScript实现一个栈是非常简单的。在这里就直接来代码了,不用一个方法一个方法去解释了。
function Stack(){ var items = []; this.push = function(element){ items.push(element); } this.pop = function(){ return items.pop(); } this.peek = function(){ return items[items.length-1]; } this.isEmpty = function(){ return items.length === 0; } this.size = function(){ return items.length; } this.clear = function(){ items = []; } this.print = funciton(){ console.log(items.toString()); } }
三、队列
队列是遵循先来先服务(FIFO)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素排在队列的末尾。
在现实生活中常见的例子就是排队。
在计算机科学中,一个常见的例子就是打印队列,先点击打印的文档会被先打印。
创建队列
同样先创建一个类来表示一个队列。需要用到的数据结构同样是数组var items = [];
声明可用的方法:
完整的Queue类
function Queue(){ var items = []; this.enqueue = function(element){ items.push(element); } this.dequeue = function(){ return items.shift(); } this.front = function(){ return items[0]; } this.isEmpty = function(){ return items.length === 0; } this.clear = function(){ items = []; } this.size = funciton(){ return items.length; } this.print = function(){ console.log(items.toString()); } }
优先队列
在优先队列中,元素被赋予优先级。当访问元素的时,具有最高优先级的元素先删除。优先队列具有最高进先出的行为特征。例如:医院的急救室为病人赋予优先级(这个优先级可以指病情严重的成程度),具有最高优先级的病人最先得到治疗。
实现一个优先队列有两种选项:
我们这里采用第一种。
function PriorityQueue(){ var items = []; funciton QueueElement(element,priority){ this.element = element; this.priority = priority; } function comparePriority(a,b){ if(a.priority > b.priority){ return 1; } if(a.priority < b.priority){ return -1; } return 0; } this.enqueue = funciton(element,priority){ var queueElement = new QueueElement(element,priority); items.push(queueElement); items.sort(comparePriority); } //其它方法和默认的Queue实现相同 }
当然,这个enqueue的实现方法很多种,我这效率不是最高的,但是容易理解。将插入的元素根据优先级排个序,那么先出去的就是优先级最高的了。
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流,谢谢大家对小牛知识库的支持。
本文向大家介绍JavaScript数据结构与算法之栈与队列,包括了JavaScript数据结构与算法之栈与队列的使用技巧和注意事项,需要的朋友参考一下 学习起因 曾经有一次在逛V2EX时,碰到这么一个帖子。 数学完全还给老师了,想学回一些基础数学,大概是高中程度的,有什么书籍推荐? 发帖的楼主大学没有高数课程,出去工作时一直在从事前端的工作。感觉到数学知识的匮乏,所以想补一补数学。 看了看帖子,感
本文向大家介绍JavaScript数组实现数据结构中的队列与堆栈,包括了JavaScript数组实现数据结构中的队列与堆栈的使用技巧和注意事项,需要的朋友参考一下 一、队列和堆栈的简单介绍 1.1、队列的基本概念 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 如下图所示: 1.2、堆栈的基本概念 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,
栈(Stack) 是限定仅在 表尾 进行 插入和删除 操作的线性表。对前前端工程师来说日操作浏览后退前进 我们把允许插入和删除的一端为栈顶(top),另一端为栈底(bottom)。 栈又称为 后进先出 (Last In Firsot Out)的线性表,简称 LIFO 结构。 栈的实现 数组 - 顺序栈(内存地址连续性) 链表 - 链式栈 数组 - 顺序栈 用数组来一实现个栈 /** push(e
本文向大家介绍JavaScript数据结构与算法之栈详解,包括了JavaScript数据结构与算法之栈详解的使用技巧和注意事项,需要的朋友参考一下 在上一篇博客介绍了下列表,列表是最简单的一种结构,但是如果要处理一些比较复杂的结构,列表显得太简陋了,所以我们需要某种和列表类似但是更复杂的数据结构---栈。栈是一种高效的数据结构,因为数据只能在栈顶添加或删除,所以这样操作很快,而且容易实现。 一:对
数组是一种线性表数据结构,它用一组连续的内存空间,来存储一组具有相同类型的数据(JS里可以是任意类型)。 关键点:连续的存储空间(数组可以进行随机访问) // js let data = [] // c int data[200] = { 0 }; // 编译时 就已经确定所有的值为零 // java int data[] = new int[3]; // 开辟了一个长度为3的数组 在Ch
本文向大家介绍堆栈和队列数据结构之间的区别,包括了堆栈和队列数据结构之间的区别的使用技巧和注意事项,需要的朋友参考一下 在堆栈和队列有所不同之前,最好在编程时了解数据类型的概念,该状态指出数据类型是在其中创建变量以存储数据的数据类型。主要有两种类型的数据类型,即原始数据类型和非原始数据类型,其中原始数据类型是数据的预定义类型,它们由编程语言支持,而非原始数据类型不是由编程语言定义的,而是由编程语言