队列是一种遵从先进先出(FIFO)原则的一组有序的项
生活中队列的例子有很多,例如吃饭排队、小学生出勤做广播体操、打印机打印文件、去地铁坐车也要排队,去海底捞吃饭也要叫号排队,这些都是队列的一种;还有一种就是优先队列,例如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());
最后我们生成的低配版的队列代码是这样子的。
首先我们先明确下我们要测什么?测方法对不对,像enqueue、dequeue、size、front、isEmpty等等。那么我们先这样定义,我们先创建一个队列,这个时候可以测下isEmpty(),然后我们把“大春、夏洛、秋雅、冬梅。“按春夏秋冬的排序进行队列操作,这个时候你可以测下size(),应该是4对吧。然后你dequeue()一下,这个时候大春没了,size()应该是3,最后你把它打出来看看,这样简单地编写完我们的一个测试用例。测试结果如图:
这里留个问题,有兴趣的同学可以把它改写成ES6语法的,提示下用class和WeakMap。
有两种思路,我们知道既然是优先队列,那么应该是有一个它本身的元素以及它的优先级构成的对吧。第一种思路就是像食堂打饭插队一样,先比较优先级,优先级越低越靠前,拿来插入;第二种就是我不允许你食堂打饭插队,但是在打完饭走的时候,优先级越低的先去打菜,也就是判断它的出队,谁优先级最低谁先走呗(备注:这边以1的优先级为最低,以此类推),我这边更倾向于前者。
其核心代码如下:
我们做这样子一个小游戏,A蹲完B蹲的例子,用循环队列,就是一圈下来,第二圈开始那位淘汰,具体的代码如下:
结果如图:
其实这里还是有一个小的Bug,就是每次蹲都是第一个人开始的,而我们实际大多数是从被淘汰那个人的下一个人开始的,时间关系,最后留个小任务给同学们完善一下这个bug,做完的可以和我校对下哈哈。
参考:
《学习JavaScript数据结构和算法(第2版)》