专栏首页前端路桥Javascript[0x03] -- 队列

Javascript[0x03] -- 队列

队列是一种遵从先进先出(FIFO)原则的一组有序的项

知识点

  • 队列的数据结构
  • 队列的优先级
  • 循环队列

队列的一些方法

  • enqueue(element(s)):向队列尾部添加一个(或多个)新的项。
  • dequeue(): 移除队列的第一(即排在队列最前面的)项,并返回被移除的元素。
  • front():返回队列中第一个元素——最先被添加,也将是最先被移除的元素。队列不做任何变动(不移除元素,只返回元素信息——与Stack类的peek方法非常类似)。
  • isEmpty():如果队列中不包含任何元素,返回true,否则返回false。
  • size():返回队列包含的元素个数,与数组的length属性类似。

生活中队列的例子

生活中队列的例子有很多,例如吃饭排队、小学生出勤做广播体操、打印机打印文件、去地铁坐车也要排队,去海底捞吃饭也要叫号排队,这些都是队列的一种;还有一种就是优先队列,例如VIP,还有SVIP等等; 还有循环队列例如丢手绢、那种两个人玩左轮手枪看最后一颗子弹属于谁的游戏等。

实现一个简单的队列

首先我们知道我们需要一个数据结构去存储队列中的元素,很显然,数组是最佳人选。接着我们需要做的事就是把楼上的队列的一些方法翻译成JavaScript语言。

我们先把整体的脉络框定一下,如楼下所示:

向队列中添加元素

抓重点,只能往队尾添加。那么也就是往我们框定的数组数据结构中push元素

items.push(elements);
从队列中移除元素

和楼上的类似,这里只需要将存储元素的数组进行shift()操作。

return items.shift();
查看队头的元素

这个也就是返回数组数据结构中的第一个元素就好,注意数组下标是0开始的就好。

return items[0];
检查队列是否为空

也就是转换成你存储数据元素的数组长度是否为0就好了

return items.length === 0;
查看队列的长度

这个其实就是让你返回对应数组的长度就好了

return items.length;
打印队列元素

就是数组的数据结构字符串化一下然后打印出来就好。

console.log(items.toString());

最后我们生成的低配版的队列代码是这样子的。

关于queue的测试用例编写

首先我们先明确下我们要测什么?测方法对不对,像enqueue、dequeue、size、front、isEmpty等等。那么我们先这样定义,我们先创建一个队列,这个时候可以测下isEmpty(),然后我们把“大春、夏洛、秋雅、冬梅。“按春夏秋冬的排序进行队列操作,这个时候你可以测下size(),应该是4对吧。然后你dequeue()一下,这个时候大春没了,size()应该是3,最后你把它打出来看看,这样简单地编写完我们的一个测试用例。测试结果如图:

这里留个问题,有兴趣的同学可以把它改写成ES6语法的,提示下用class和WeakMap。

实现一个优先队列

有两种思路,我们知道既然是优先队列,那么应该是有一个它本身的元素以及它的优先级构成的对吧。第一种思路就是像食堂打饭插队一样,先比较优先级,优先级越低越靠前,拿来插入;第二种就是我不允许你食堂打饭插队,但是在打完饭走的时候,优先级越低的先去打菜,也就是判断它的出队,谁优先级最低谁先走呗(备注:这边以1的优先级为最低,以此类推),我这边更倾向于前者。

其核心代码如下:

实现一个循环队列

我们做这样子一个小游戏,A蹲完B蹲的例子,用循环队列,就是一圈下来,第二圈开始那位淘汰,具体的代码如下:

结果如图:

其实这里还是有一个小的Bug,就是每次蹲都是第一个人开始的,而我们实际大多数是从被淘汰那个人的下一个人开始的,时间关系,最后留个小任务给同学们完善一下这个bug,做完的可以和我校对下哈哈。

参考:

《学习JavaScript数据结构和算法(第2版)》

本文分享自微信公众号 - 前端路桥(ataola),作者:丰臣正一

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

原始发表时间:2019-11-24

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 软件推荐(蜜蜂剪辑) -- 剪辑软件(限免)

    今天是软件专场的倒数第84场,跟大家分享的是逼格很高操作很傻瓜式的剪辑软件--蜜蜂剪辑。最重要的是它限免,恰逢年终需要做一些逼格很高的视频来诉说2019的辛酸...

    丰臣正一
  • 软件推荐(office)--聊聊微软和金山

    今天是软件专场的倒数第97场,我们今天的主题是Office,看完这篇文章我期望你能够对Office办公软件有一定的了解,它怎么来?它有什么用?哪种适合我?如果喜...

    丰臣正一
  • Vue[0x03] - Vue基础实践

    抓重点讲吧,最开始可追溯的版本号是0.6.0这个,但是正式对外发布的版本是在2014年1月24日发布的0.8.0。后面就是两个打头的里程碑,一个是1.x.x,一...

    丰臣正一
  • java并发队列之阻塞队列-ArrayBlockingQueue

    今天讲阻塞队列,阻塞队列有很多,这篇文章只讲解ArrayBlockingQueue,其他的大同小异。

    胖虎
  • 0761-7.0.3-如何使用YARN Queue Manager UI配置集群资源

    在CDP DC上,YARN资源的调度程序默认为Capacity Scheduler。我们可以通过YARN Queue Manager UI来界面化配置YARN的...

    Fayson
  • 野生前端的数据结构基础练习(2)——队列

    循环队列书中并没有提及,它是一种特殊的队列。简单理解就是将基本队列只当做存储结构,而使用front和rear两个指针分别代表队列的头和尾,实际对外表现的队列是f...

    大史不说话
  • 并发编程之queue

    一、什么是queue 队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行...

    lyb-geek
  • Java队列学习第一篇之列介绍

    队列大家都知道,但是在Java中队列分哪几种呢?清楚吗?都有哪些地方用到了队列呢?最常用的场景的就是消息中间件,比如各种MQ都是使用的队列来的。如果没有用过消息...

    凯哥Java
  • AI_第一部分 数据结构与算法(8.队列)

    第四阶段我们进行深度学习(AI),本部分(第一部分)主要是对底层的数据结构与算法部分进行详尽的讲解,通过本部分的学习主要达到以下两方面的效果:

    还是牛6504957
  • 【数据结构(C语言版)系列三】 队列

    队列是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端删除元素。这和我们日常生活中的排队是一致的,最早进入队列的元素最早离开。在队列中,允许插入的一...

    闪电gogogo

扫码关注云+社区

领取腾讯云代金券