怒肝 JavaScript 数据结构 — 队列篇

作者：杨成功

2022 年 4 月 19 日
本文字数：2328 字
阅读完需：约 8 分钟

大家好，我是杨成功。

前几篇我们学习了俩个数据结构 —— 数组和栈。今天要学习的数据结构叫做队列。队列与栈其实非常相似，区别是栈遵循“后进先出”原则，而队列正好相反，只能“先进先出”。

什么是队列

队列是遵循先进先出（FIFO，也称为先来先服务）原则的一组有序集合。队列与栈一样，本质上都是数组。

队列是在尾部添加新元素，从顶部移除最近的元素。新添加的元素必须排在队列的末尾，而读取元素必须从队列最前面开始。添加与读取可以同时进行互不影响。

在生活中，我们最常见的也是最典型的例子就是排队。排队大家很熟，排在前面的先办事，办完事就能走。后面来的人只能排在最后面，等前面的人办完事才能轮到他，这就是“先来先服务”原则。

当然，也有不守规矩的人插队，这样会被大家谴责甚至挨揍，队列同样也不允许你插队，必须按照顺序，因此队列是一个“有序集合”。

在程序开发中，我们听的比较多的就是“任务对列”。任务对列就是一组计算机任务排队等待 CPU 执行。新来的任务会从底部添加到队列中，CPU 执行时则会从顶部取出任务。这样一端添加任务，另一端执行任务，公平的很。

实现一个队列

同样的，我们基于 JavaScript 当中的对象，实现一个队列。

const Queue = (() => {  let _start;  let _end;  let _items;    class Queue {    constructor() {      _start = 0;      _end = 0;      _items = {};  }  return Queue;}

复制代码

上面代码中声明了一个名为 Queue 的类，其中 items 属性就是存储队列元素的对象。我们后续操作队列基本上就是在操作这个对象。

其实这里用数组实现更简单。但是我们在栈的那一篇说过，当数组非常大的时候，数据操作的性能就会变得很低。因此为了实现一个更高效的数据结构，我们直接用对象来实现。

另外的两个属性含义如下：

start：表示队列第一个元素的 key 值
end：表示队列最后一个元素的 key 值

有了属性之后，按照 FIFO 原则，我们还需要在这个类中创建一些方法，来指定队列的添加/移除操作。具体方法如下：

enqueue()：向队列尾部添加新元素
dequeue()：移除队列的第一项
peek()：返回队列的第一个元素
isEmpty()：判断队列里是否有元素，没有则返回 true
clear()：清除队列里的所有元素
size()：返回队列里元素的数量

先看如何向队列添加元素（入列）:

enqueue(item) {  _items[_end] = item;  _end++;}

复制代码

因为元素要添加在末尾，所以我们将 end 属性作为 items 对象的 key，然后赋值为传递的参数 item，最后再将 end 属性的值加一。

end 属性是参照数组的 .length 属性实现的，不过在队列中，end 属性不会因为队列中元素的删除而变化，就是说只要有新元素加入队列，end 永远会加一。

接着再看如何从队列中移除元素（出列）：

dequeue() {  if(this.isEmpty()) {    return undefind;  }  let item = _items[_start]  delete _items[_start]  _start++;  return item;}

复制代码

这个代码也好理解，首先判空，然后获取第一个元素，删除这个元素，此时还不能忘记给 start 属性自增一，最后返回被删除的元素。

所以 start 和 end 属性，会在队列进行出列和入列操作时，分别自增一。

理解了这些，剩余的几个方法就比较简单了：

size() {  return _end - _start;}isEmpty() {  return _end - _start === 0;}peek() {  if(this.isEmpty()) {    return undefind;  }  return _items[_start]}clear() {  _items = {}  _start = 0  _end = 0}

复制代码

还需要一个 toString 方法。因为对象转换为字符串后的值是 [object Object]，我们希望的是类似于数组那样的效果，输出所有元素以逗号分隔的字符串。

我们看如何实现：

toString() {  let arr = Object.values(_items)  return arr.toString();}

复制代码

最终代码如下：

const Queue = (() => {  let _start;  let _end;  let _items;  class Queue {    constructor() {      _start = 0;      _end = 0;      _items = {};    }    enqueue(item) {      _items[_end] = item;      _end++;    }    dequeue() {      if (this.isEmpty()) {        return undefined;      }      let item = _items[_start];      delete _items[_start];      _start++;      return item;    }    size() {      return _end - _start;    }    isEmpty() {      return _end - _start === 0;    }    peek() {      if (this.isEmpty()) {        return undefined;      }      return _items[_start];    }    clear() {      _items = {};      _start = 0;      _end = 0;    }    toString() {      let arr = Object.values(_items);      return arr.toString();    }  }  return Queue;})();

复制代码

使用队列

上面实现了一个表示队列的类，现在用一下好不好使：

var queue = new Queue();console.log(queue.isEmpty()) // true

复制代码

首先执行入列操作，添加北京,上海两个元素。

queue.enqueue('北京')queue.enqueue('上海')console.log(queue.size()) // 2console.log(queue.toString()) // '北京,上海'

复制代码

通过打印结果来看，是完全符合预期的。我们再看出列操作的效果：

console.log(queue.dequeue()) // 北京console.log(queue.dequeue()) // 上海console.log(queue.dequeue()) // undefinedconsole.log(queue.size()) // 0console.log(queue.toString()) // ''

复制代码

上面几步从队列的头部开始，逐渐将元素移出，直到队列被清空。我们可以看出队列确实是遵循了先进先出的原则。

队列就介绍完了，你学会了吗？下一篇我们介绍双端队列～

加入学习群

本文来源公众号：程序员成功。这是学习 JavaScript 数据结构与算法的第 6 篇，本系列会连续更新一个月，欢迎关注公众号，点击“加群”一起加入我们的学习队伍～

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/89c3b329117d5c05ab10c7180】。文章转载请联系作者。

杨成功

关注

前端架构师 2021.07.18 加入

专注前端工程与架构，热爱分享，微信 ruidoc，欢迎交流～

发布

暂无评论

创作场景

怒肝 JavaScript 数据结构 — 队列篇

什么是队列

实现一个队列

使用队列

加入学习群

杨成功

评论