程序员吧
首页 >编程 >正文

yocto queue微型队列数据结构源码解读

2023-01-04 16:54出处/作者：小冰整合编辑：@小冰
这篇文章主要为大家介绍了yocto queue微型队列数据结构源码解读，有需要的朋友可以借鉴参考下，希望能够有所帮助，祝大家多多进步，早日升职加薪

引言

yocto-queue是一个微型队列的数据结构，根据作者的介绍，如果在你一个数据量很大的数组上，大量的操作Array.push和Array.shift，那么你可以考虑使用yocto-queue来替代Array。

因为Array.shift的时间复杂度是O(n)，而Queue.dequeue的时间复杂度是O(1)，这对于大量的数据来说，性能上的提升是非常明显的。

时间复杂度和空间复杂度

学习算法和数据结构的时候，我们经常会听到时间复杂度和空间复杂度，这两个概念是什么呢？

时间复杂度

时间复杂度是指一个算法执行所耗费的时间，它是一个函数，这个函数的变量是问题规模的函数；

通常会使用大O符号来表示时间复杂度，比如O(n)，O(n^2)，O(logn)等等，这就是大 O 表示法（Big O notation）。

O代表的是算法的渐进时间复杂度（asymptotic time complexity），也就是说，随着问题规模的增大，算法的执行时间的增长率和O中的函数相同，称作渐进时间复杂度。

O(1)表示算法的执行时间与问题规模无关，也就是说，不管问题规模有多大，算法执行所耗费的时间都是一样的，这种算法称为时间复杂度为常数阶的算法。

O(n)表示算法的执行时间与问题规模成正比，也就是说，随着问题规模的增大，算法执行所耗费的时间也随之增大，这种算法称为时间复杂度为线性阶的算法。

O(n^2)表示算法的执行时间与问题规模成平方比，也就是说，随着问题规模的增大，算法执行所耗费的时间呈二次方增长，这种算法称为时间复杂度为平方阶的算法。

通过上面的介绍，我们可以将O比喻成函数，O(1)就是一个常数函数，O(n)就是一个线性函数，O(n^2)就是一个平方函数，O(logn)就是一个对数函数。

说了这么多概念性的问题，不如直接来看看代码；

例如，我们有一个数组，我们要遍历这个数组，然后将数组中的每个元素都乘以2，那么我们可以这么写：

function multiplyBy2(arr) {
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    result.push(arr[i] * 2);
  }
  return result;
}

这段代码的时间复杂度是O(n)，因为我们遍历了数组，所以时间复杂度就是O(n)，O代表这个函数，n代表问题规模，也就是数组的长度，组合起来就是O(n)。

再直观一点，我们可以这么理解，当数组的长度为n时，我们需要执行n次循环，所以时间复杂度就是O(n)，用代码表示就是：

function O(n) {
    for (let i = 0; i < n; i++) {
        // do something
    }
}
O(1); // O(1)
O(2); // O(2)
O(3); // O(3)
O(n); // O(n)

空间复杂度

空间复杂度是指一个算法执行所耗费的内存空间，它是一个函数，这个函数的变量是问题规模的函数；

和时间复杂度一样，空间复杂度也有O(1)、O(n)、O(n^2)、O(logn)等等，它们的含义和时间复杂度一样，只不过它们是表示算法执行所耗费的内存空间的增长率。

当然空间复杂度计算的不是内存消耗，而是变量的个数，例如冒泡排序的空间复杂度是O(1)，因为它只需要一个变量temp：

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

而快速排序的空间复杂度是O(logn)，因为它需要一个变量pivot，而且它是递归的，所以空间复杂度是O(logn)：

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = arr.splice(pivotIndex, 1)[0];
  const left = [];
  const right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

源码分析

上面了解了时间复杂度和空间复杂度的概念，那么我们开始正式分析yocto-queue的源码；

代码不多，可以直接通过github1s在线阅读，然后使用浏览器控制台来查看效果；

代码分析

先来看一下yocto-queue的使用方式：

  • 安装
npm install yocto-queue
  • 使用
import Queue from 'yocto-queue';
const queue = new Queue();
queue.enqueue('🦄');
queue.enqueue('🌈');
console.log(queue.size);
//=> 2
console.log(...queue);
//=> '🦄 🌈'
console.log(queue.dequeue());
//=> '🦄'
console.log(queue.dequeue());
//=> '🌈'

然后再来看一下yocto-queue的代码：

/*
How it works:
`this.#head` is an instance of `Node` which keeps track of its current value and nests another instance of `Node` that keeps the value that comes after it. When a value is provided to `.enqueue()`, the code needs to iterate through `this.#head`, going deeper and deeper to find the last value. However, iterating through every single item is slow. This problem is solved by saving a reference to the last value as `this.#tail` so that it can reference it to add a new value.
*/
class Node {
    value;
    next;
    constructor(value) {
        this.value = value;
    }
}
export default class Queue {
    #head;
    #tail;
    #size;
    constructor() {
        this.clear();
    }
    enqueue(value) {
        const node = new Node(value);
        if (this.#head) {
            this.#tail.next = node;
            this.#tail = node;
        } else {
            this.#head = node;
            this.#tail = node;
        }
        this.#size++;
    }
    dequeue() {
        const current = this.#head;
        if (!current) {
            return;
        }
        this.#head = this.#head.next;
        this.#size--;
        return current.value;
    }
    clear() {
        this.#head = undefined;
        this.#tail = undefined;
        this.#size = 0;
    }
    get size() {
        return this.#size;
    }
    * [Symbol.iterator]() {
        let current = this.#head;
        while (current) {
            yield current.value;
            current = current.next;
        }
    }
}

可以直接直接粘贴到浏览器控制台中运行

构造函数

首先来看一下Queue的构造函数：

class Queue {
  #head;
  #tail;
  #size;
  constructor() {
    this.clear();
  }
}

一个Queue类，它有三个私有属性：#head、#tail、#size；

在class中，如果属性名前面加上#，表示这个属性是私有属性，外部是无法访问的；

  • #head：指向队列的头部；
  • #tail：指向队列的尾部；
  • #size：队列的长度；

然后在构造函数中调用了this.clear()方法，这个方法的作用是清空队列，代码如下：

class Queue {
    clear() {
        this.#head = undefined;
        this.#tail = undefined;
        this.#size = 0;
    }
}

enqueue

接下来看一下enqueue方法：

class Queue {
    enqueue(value) {
        const node = new Node(value);
        if (this.#head) {
            this.#tail.next = node;
            this.#tail = node;
        } else {
            this.#head = node;
            this.#tail = node;
        }
        this.#size++;
    }
}

enqueue方法的作用是向队列中添加一个元素；

首先创建一个Node实例，然后判断this.#head是否存在，如果存在，说明队列中已经有元素了，那么就把新创建的Node实例添加到队列的尾部；

如果this.#head不存在，说明队列中还没有元素，那么就把新创建的Node实例添加到队列的头部；

最后，队列的长度加一；

这里使用到了一个Node类，它的作用是用来保存队列中的元素的，代码如下：

class Node {
    value;
    next;
    constructor(value) {
        this.value = value;
    }
}
  • value：指向的是队列中的元素；
  • next：指向下一个Node实例；

dequeue

接下来看一下dequeue方法：

class Queue {
    dequeue() {
        const current = this.#head;
        if (!current) {
            return;
        }
        this.#head = this.#head.next;
        this.#size--;
        return current.value;
    }
}

dequeue方法的作用是从队列中移除一个元素；

首先获取队列的头部元素，然后判断current是否存在，如果不存在，说明队列中没有元素，那么就直接返回；

如果current存在，说明队列中有元素，那么就把队列的头部元素移除，然后把队列的长度减一；

最后，返回移除的元素；

图例

一个队列结构只会有两个操作：入队和出队，下面通过一个图例来说明一下；

入队时，会把新的元素添加到队列的尾部；

出队时，会把队列的头部元素移除；

yocto queue微型队列数据结构源码解读

上面的图例中，Node0表示队列的头部元素，Node_n表示队列的尾部元素；

Current0表示队列中的第一个元素，Current_n表示队列中的最后一个元素；

在队列中，只会关心头部和尾部的元素，头部的元素用于弹出队列，尾部的元素用于添加元素；

在上面的图例中，如果我们执行dequeue方法，那么就会把Node0移除，然后把Node1设置为队列的头部元素；

yocto queue微型队列数据结构源码解读

上面的dequeue方法执行完毕后，队列的头部元素就变成了Node1；

Node0因为没有任何引用指向它，所以会被垃圾回收机制回收；

如果我们执行enqueue方法，那么就会把新的元素添加到队列的尾部：

yocto queue微型队列数据结构源码解读

上面的enqueue方法执行完毕后，队列的尾部元素就变成了newNode；

迭代器

yocto-queue到最后还提供了一个迭代器，用于遍历队列中的元素；

class Queue {
    // ...
    *[Symbol.iterator]() {
        let current = this.#head;
        while (current) {
            yield current.value;
            current = current.next;
        }
    }
}

上面的代码中，使用了一个generator函数，它会返回一个迭代器；

迭代器中，会从队列的头部元素开始遍历，然后把每个元素的值返回出去；

迭代器的使用

迭代器是es6中的一个新特性，它可以用于遍历数据结构中的元素，使用起来也非常简单，只需要在数据结构上调用Symbol.iterator方法即可；

const obj = {
    [Symbol.iterator]() {
        let i = 0;
        return {
            next() {
                return {
                    value: i++,
                    done: i > 10
                };
            }
        };
    }
};
for (const item of obj) {
    console.log(item);
}

上面的代码中，我们定义了一个对象，它的Symbol.iterator方法返回了一个迭代器；

一个迭代器是一个对象，它有一个next方法，每次调用next方法，都会返回一个对象，这个对象中包含了当前元素的值和一个done属性，表示是否已经遍历完毕；

可以使用generator函数来简化上面的代码：

const obj = {
    *[Symbol.iterator]() {
        let i = 0;
        while (i < 10) {
            yield i++;
        }
    }
};
for (const item of obj) {
    console.log(item);
}

上面的代码中，我们使用了generator函数来简化迭代器的定义；

参考：

Symbol.iterator

Generator 函数

总结

yocto-queue是一个非常简单的队列实现，它的核心是使用了链表来存储数据；

链表的优点是插入和删除元素的时间复杂度是O(1)，但是查找元素的时间复杂度是O(n)，不过对于队列来说，查找元素的操作是不需要的；

对比于数组，每次插入和删除元素都需要移动元素，所以时间复杂度是O(n)，但是查找元素的时间复杂度是O(1)；

所以正如文章开头，作者提到的，对于一个大数组来实现队列，效率是非常低的，而应该使用链表来实现（因为这个库的核心实现就是链表，所以肯定优先推荐用这个库=）；

通过阅读yocto-queue的源码，我们学习到了很多：

  • 时间复杂度、空间复杂度的概念
  • 链表的实现
  • 如何使用es6的Symbol.iterator来实现可迭代对象；
  • 如何使用es6的generator函数来实现迭代器；
  • 数组、队列、链表的区别；

以上就是yocto queue微型队列数据结构源码解读的详细内容，更多关于yocto queue队列数据结构的资料请关注脚本之家其它相关文章！

Idea中如何查看SpringSecurity各Filter信息
Feign调用中的两种Header传参方式小结

网友评论

登录 注册
iCMS
验证码 换一张
取 消
暂无评论...
24小时内最火资讯
  1. 1Python之列表推导式最全汇总(上篇)
  2. 2Win11安装VMware Workstation Pro,Centos,Xshell,Xftp图文教程(Linux学习必备)
  3. 3springboot使用mybatis开启事务回滚
  4. 4windows2003 的安装及安装过程遇到的问题小结
  5. 5git可视化工具Sourcetree使用全攻略(git冲突解决)
  6. 6django+vue项目搭建实现前后端通信
  7. 7Redis 分片集群的实现
  8. 8springboot使用mybatis开启事务回滚
  9. 9GPU版本安装Pytorch的最新方法步骤
  10. 10Win11安装VMware Workstation Pro,Centos,Xshell,Xftp图文教程(Linux学习必备)
三日内热门评论文章
  1. 1 Win11安装VMware Workstation Pro,Centos,Xshell,Xftp图文教程(Linux学习必备)
  2. 2 Redis处理高并发之布隆过滤器详解
  3. 3 一文带你了解MySQL字符集和比较规则
  4. 4 MySQL常见内置函数以及其使用教程
  5. 5 解决Spring Cloud feign GET请求无法用实体传参的问题
  6. 6 Feign调用中的两种Header传参方式小结
  7. 7 yocto queue微型队列数据结构源码解读
  8. 8 Idea中如何查看SpringSecurity各Filter信息
  9. 9 arrify 转数组实现示例源码解析
  10. 10 Css-In-Js实现classNames库源码解读
精彩图赏
热门视频
月度热门文章
  1. 264
    全网最强下载神器IDM使用教程之利用IDM加速下载百度网盘大文件的方法
    ·
  2. 218
    MySQL如何查看正在运行的SQL详解
    ·
  3. 198
    关于yolov8训练的一些改动及注意事项
    ·
  4. 150
    chatgpt国内镜像 pycharm idea插件使用详解
    ·
  5. 148
    VS Code里使用Debugger for Unity插件调试的方法(2023最新版)
    ·
  6. 125
    全网最强下载神器IDM使用教程之利用IDM加速下载百度网盘大文件的方法
    ·
  7. 117
    JavaWeb day5 Tomcat配置及idea创建Maven-Tomcat项目
    ·
  8. 103
    buildcheck包报错问题排查解决
    ·
  9. 97
    vscode远程开发使用SSH远程连接服务器的方法「内网穿透」
    ·
  10. 96
    全网最强下载神器IDM使用教程之利用IDM加速下载百度网盘大文件的方法
    ·
关键词

为您推荐
  • 相关阅读
  • 业界资讯
  • 手机通讯
  • 电脑办公
  • 新奇数码
  • 软件游戏
  • 科学探索
用户反馈 返回首页 相关阅读 参与讨论 回到顶部

程序员吧感受编程的乐趣

法律声明：本站内容均为网友上传，网站举办方负责审核和监督，如存在版权或非法内容，欢迎举报，我们将尽快予以删除。

Copyright © 2022 程序员吧. All rights reserved. Powered by ITBeta V7.0.16