前言
数据结构就是关系,没错,就是数据元素相互之间存在的一种或多种特定关系的集合。
常用的数据结构有:
数组,队列(queue),堆(heap),栈(stack),链表(linked list ),树(tree),图(graph)和散列表(hash)
本文主要介绍的是数组、栈与队列,下面来一起看看详细的介绍吧。
一、数组
数组是平时使用最常用的数据结构,在JavaScript中数组是动态的分配大小,在这里我不会介绍JavaScript里面数组的所有的方法,而是针对数据结构这个方向谈谈所用到的方法。
创建和初始化数组
添加元素
往数组后添加元素
往数组前面添加元素
往数组的任意位置插入元素
运用splice方法
删除元素
删除第一位
删除任意位置
排序
反序
自然排序
自定义排序
这个自定义排序跟java里面实现comparator接口一个意思。用处可大了。
仿佛看起有点不对啊,我们应该想要的是 [1,13],这个时候我们就用自定义排序来解决这个问题
这还只是最简单的,也可以对任何对象类型进行数组排序。例如,对象Person有名字和年龄属性,我们希望根据年龄排序
搜索
搜索有两个方法:indexOf方法返回与参数匹配的第一个元素的索引,lastIndexOf返回与参数匹配的最后一个元素的索引。
二、栈
栈是一种遵循后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。在JavaScript中变量保存和函数调用都是用栈存储的。
首先创建一个类来表示一个栈,需要一种数据结构来保存栈里的元素。这里我们就选择刚学的数组:var items = [];
接下来,为我们的栈声明一些方法:
push(elements(s))
:添加一个(或几个)新元素到栈顶pop()
:移除栈顶的元素,同时返回被移除的元素peek()
:获取栈顶的元素,不对栈做出任何修改isEmpty()
:如果栈里没有任何元素就返回true,否则返回false;clear()
:清空栈size()
:返回栈元素的个数
如果上一节数组认真看了,我相信用JavaScript实现一个栈是非常简单的。在这里就直接来代码了,不用一个方法一个方法去解释了。
三、队列
队列是遵循先来先服务(FIFO)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素排在队列的末尾。
在现实生活中常见的例子就是排队。 在计算机科学中,一个常见的例子就是打印队列,先点击打印的文档会被先打印。
创建队列
同样先创建一个类来表示一个队列。需要用到的数据结构同样是数组var items = [];
声明可用的方法:
enqueue(element(s))
:向队尾添加一个(或多个)新的项dequeue()
:移除队列的第一(即排在队列最前面的)项,并返回被移除的元素。front()
:返回队列中第一个元素isEmpty()
:如果队列中不包含元素返回true,否则返回falsesize()
:返回队列包含元素的个数
完整的Queue类
优先队列
在优先队列中,元素被赋予优先级。当访问元素的时,具有最高优先级的元素先删除。优先队列具有最高进先出的行为特征。例如:医院的急救室为病人赋予优先级(这个优先级可以指病情严重的成程度),具有最高优先级的病人最先得到治疗。
实现一个优先队列有两种选项:
我们这里采用第一种。
当然,这个enqueue的实现方法很多种,我这效率不是最高的,但是容易理解。将插入的元素根据优先级排个序,那么先出去的就是优先级最高的了。
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流,谢谢大家对编程之家的支持。