写点什么

怒肝 JavaScript 数据结构 — 队列篇

作者:杨成功
  • 2022 年 4 月 19 日
  • 本文字数:2328 字

    阅读完需:约 8 分钟

怒肝 JavaScript 数据结构 — 队列篇

大家好,我是杨成功。


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

什么是队列


队列是遵循先进先出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 属性自增一,最后返回被删除的元素。


所以 startend 属性,会在队列进行出列和入列操作时,分别自增一


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


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
用户头像

杨成功

关注

前端架构师 2021.07.18 加入

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

评论

发布
暂无评论
怒肝 JavaScript 数据结构 — 队列篇_数据结构_杨成功_InfoQ写作社区