专栏首页前端桃园[第 3 期]JavaScript数据结构之数组栈队列

[第 3 期]JavaScript数据结构之数组栈队列

1. 数组

数组是平时使用最常用的数据结构,在JavaScript中数组是动态的分配大小,在这里我不会介绍JavaScript里面数组的所有的方法,而是针对数据结构这个方向谈谈所用到的方法。

1.1 创建和初始化数组

//创建空数组
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]

1.2 添加元素

1.2.1往数组后添加元素

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]

1.2.2往数组前面添加元素

var number = [1,2,3];
number.unshift(0);
//[0,1,2,3]
number.unshift(-2,-1);
//[-2,-1,0,1,2,3]

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]

1.3 删除元素

1.3.1 删除第一位

var number = [1,2,3];
number.shift();
//[2,3]

1.3.2 删除任意位置

使用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);

1.4 排序

1.4.1 反序

var number = [3,2,1];
number.reverse();
//[1,2,3]

1.4.2 自然排序

var numebr = [2,3,4,1,3,7];
number.sort();
//[1,2,3,3,4,7]

1.4.3 自定义排序

这个自定义排序跟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}]

1.5 搜索

搜索有两个方法:indexOf方法返回与参数匹配的第一个元素的索引,lastIndexOf返回与参数匹配的最后一个元素的索引。

var number = [1,3,4,3,56,6,7,4];
number.indexOf(3);//1
number.lastIndexOf(3)//3

2. 栈

栈是一种遵循后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。在JavaScript中变量保存和函数调用都是用栈存储的。

首先创建一个类来表示一个栈,需要一种数据结构来保存栈里的元素。这里我们就选择刚学的数组:var items = []; 接下来,为我们的栈声明一些方法:

  • push(elements(s)):添加一个(或几个)新元素到栈顶
  • pop():移除栈顶的元素,同时返回被移除的元素
  • peek():获取栈顶的元素,不对栈做出任何修改
  • isEmpty():如果栈里没有任何元素就返回true,否则返回false;
  • clear():清空栈
  • size():返回栈元素的个数

如果上一节数组认真看了,我相信用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());
    }
}

3. 队列

队列是遵循先来先服务(FIFO)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素排在队列的末尾。

在现实生活中常见的例子就是排队。 在计算机科学中,一个常见的例子就是打印队列,先点击打印的文档会被先打印。

3.1 创建队列

同样先创建一个类来表示一个队列。需要用到的数据结构同样是数组var items = []; 声明可用的方法:

  • enqueue(element(s)):向队尾添加一个(或多个)新的项
  • dequeue():移除队列的第一(即排在队列最前面的)项,并返回被移除的元素。
  • front():返回队列中第一个元素
  • isEmpty():如果队列中不包含元素返回true,否则返回false
  • size():返回队列包含元素的个数 完整的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());
    }
}

3.2 优先队列

在优先队列中,元素被赋予优先级。当访问元素的时,具有最高优先级的元素先删除。优先队列具有最高进先出的行为特征。例如:医院的急救室为病人赋予优先级(这个优先级可以指病情严重的成程度),具有最高优先级的病人最先得到治疗。

实现一个优先队列有两种选项:

  1. 设置优先级,然后在正确的位置添加元素;
  2. 用入列操作添加元素,然后按照优先级移除它们。

我们这里采用第一种。

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的实现方法很多种,我这效率不是最高的,但是容易理解。将插入的元素根据优先级排个序,那么先出去的就是优先级最高的了。

本文分享自微信公众号 - 前端桃园(betaoyuan),作者:桃翁

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-03-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 22道高频JavaScript手写面试题及答案

    由于防抖函数原理:在事件被触发n秒后再执行回调,如果在这n秒内又被触发,则重新计时。

    桃翁
  • JavaScript函数式编程,真香之组合(二)

    组合是一种为软件的行为,进行清晰建模的一种简单、优雅而富于表现力的方式。通过组合小的、确定性的函数,来创建更大的软件组件和功能的过程,会生成更容易组织、理解、调...

    桃翁
  • async/await 原理及执行顺序分析

    之前写了篇文章《这一次,彻底理解Promise原理》,剖析了Promise的相关原理。我们都知道,Promise解决了回调地狱的问题,但是如果遇到复杂的业务,代...

    桃翁
  • 长期维护更新,前端面试题

    HTML,即超文本标记语言,几乎是所有网站的支柱。HTML 为网页带来标题、子标题、列表和其它一些文档结构的格式。在最近更新的 HTML5 中,甚至可以创建图表...

    FinGet
  • 【精品转载】学习 Vue 源码的必要知识储备

    我最近在写 Vue 进阶的内容。在这个过程中,有些人问我看 Vue 源码需要有哪些准备吗?所以也就有了这篇计划之外的文章。

    用户1462769
  • jQuery原理(DOM操作相关方法)

    删除所有的元素或指定元素。判断是否传入参数,如果传入参数,则删除指定元素,否则删除全部。

    Dreamy.TZK
  • 说说几个 API 和应用案例

    除了 classList.contains 方法之外,还有一个 node.contains 方法,这个方法返回的是一个布尔值,来表示传入的节点是否为该节点的后代...

    多云转晴
  • 前端AES的加密和解密

    在工作的过程中,经常要对一些数据做一些加密,当然有复杂的加密和简单的加密,也有对称加密等等。总之加密的方式有很多。今天在这里,我只是简单的分享一个我最近遇到的加...

    用户1174387
  • php编程之小程序支付所需规避的问题

    对于开发一款小程序来说,经常是需要做支付功能的,但是大家在做这个功能的时候,往往会发现遇到很多自己无法解决的问题,那么对于这个问题,我们自己也曾遇到过,下面就跟...

    用户7847861

扫码关注云+社区

领取腾讯云代金券