JS中算法和数据结构队列实例的详细说明

本文通过实例描述了JS中队列的算法和数据结构。分享给大家参考，如下：

队列(Queue)

我们谈到了stack，它是一种相对高效的数据结构，遵循LIFO(后进先出)的原则。我们今天要讨论的队列也是一个特殊的列表。与栈不同，队列只能在队列末尾插入元素，在队列头删除元素，就像我们平时排队买票一样~

队列用于存储按顺序排列的数据，遵循先进先出的原则。它也是计算机中常用的一种数据结构，很多地方没有用到，比如提交给操作系统的一系列进程，打印池任务等等。

与栈类似，队列操作主要有两种：向队列中插入新元素和删除队列中的元素，即入队和出队。

此外，队列还有一些其他的操作，比如读取队列头的元素，只返回头元素，不从队列中删除，类似于栈的peek方法；back方法读取队列末尾的元素；ToString方法可以打印当前队列中的所有元素；清除方法清空当前队列等。

队列数据定义

我们定义了数据类型，可以通过JS中的数组来实现。

队列的实现

//定义队列函数queue(){ this . datastore=[]；this.enqueue=enqueue//加入this .出列=出列；//离开这个. front=front；//检查组长元素this.back=back//检查team tail元素this.toString=toString//显示队列的所有元素this.clear=clear//清空当前队列this.empty=empty//判断当前队列是否为空}我们先实现入队操作：

入队：向队列中添加元素

//在队列的末尾添加一个元素，直接调用push方法函数enqueue(element){ this . datastore . push(element)；}因为JS中的数组有一些其他语言没有的优点，可以通过shift方法直接删除数组的第一个元素，所以出列操作的实现变得非常简单。

出列：删除队列头部的元素

//要删除队列头的元素，可以使用shift方法函数出列(){if (this。empty())返回“此队列为空”；else this . Datastore . shift()；}我们注意到我对队列中是否有元素做了判断，因为删除空队列中的元素是没有意义的，所以我们来看看空方法是如何实现的。

空：确定队列是否为空

//通过判断dataStore的长度，我们可以知道队列是否为空。函数empty () {if (this。数据存储。length==0)返回true否则返回false}我们先来看看测试这些方法。

var queue=新队列()；console . log(queue . empty())；//true//添加几个元素queue . enqueue(' Apple ')；queue . enqueue(' Banna ')；排队。排队('梨')；console . log(queue . empty())；//false现在，我不知道谁是第一个，谁是最后一个，所以我们可以使用前面和后面的方法分别进行检查。

正面：查看团队领导元素

//看队列的第一个元素，直接将数组的第一个元素返回给函数front () {if (this。empty())返回“此队列为空”；否则返回this . Datastore[0]；}返回：查看队列末尾的元素

//查看队列头部的元素，直接返回数组的最后一个元素。//读取队列末尾的元素，functionback () {if (this。empty())返回“此队列为空”；否则返回this . Datastore[this . Datastore . length-1]；}让我们看看是否正确：

//查看team leader元素console . log(queue . front())；//Apple//检查end元素console . log(queue . back())；//Pear//queue . queue()；//查看team leader元素console . log(queue . front())；//Banana//检查队列结束元素console . log(queue . back())；//梨，没问题！现在，我想看看总共有多少个水果，这是通过toString方法实现的。

查看队列中的所有元素

//正确检查所有元素。这里我使用数组的join方法实现functiontostring(){ return this . datastore . join(' \ n ')；}现在，你可以看到你还剩下什么水果可以吃了。

console . log(queue . tostring())//apple//banana//pear我们只剩下一个清晰的方法了。如果你已经吃了所有的水果，你应该使用清除方法。

//清空当前队列也很简单。我们可以直接清空dataStore值来运行clear(){删除它。数据存储；this . datastor=[]；}到目前为止，我们已经用JS实现了一个队列。怎么样？你觉得JS数组超级好用，省事吗？

//清除队列queue . clear()；console . log(queue . empty())；//true接下来，我们使用队列对基数进行排序。

基数排序属于“分布排序”，通过键值的一些信息，将需要排序的元素分布到一些“桶”中，从而实现排序功能。基数排序属于稳定排序，时间复杂度为O (nlog(r)m)，其中r为采用的基数，m为堆数。在某些情况下，

首先看基数排序的实现步骤(以两位数为例)。需要扫描两次。第一次按个位数排序，第二次按十位数排序。根据相应的数值，每个数字被分配到不同的框中。最后依次取出盒子里的数字组成新的列表，就是排序后的数字。

假设我们有一系列的数字，分别是73，22，93，43，55，14，28，65，39，81。首先，按个位数排序，放在不同的盒子里，如下图

第一次排序后，这些框中的值会再次串联起来，变成下面的系列：81、22、73、93、43、14、55、65、28、39，然后按照十位数排序，再放在不同的框中，如下图

第二次排序，然后这些框中的值再次串联，整个序列已经排序：14、22、28、39、43、55、65、73、81、93。我们已经理解了基数排序的算法思想，然后我们想用队列来实现它。让我们来看看。

//基数排序var queues=[]；//定义队列数组var nums=[]；//定义一个数字数组//从0到99中选择十个随机数进行排序(var I=0；i 10I){ queues[I]=new Queue()；nums[I]=Math . floor(Math . random()* 101)；}//console.log先于排序('先于radix sort : ' nums)；//基数排序分布(nums，queues，10，1)；收集(队列、nums)；分发(nums，queues，10，10)；收集(队列、nums)；//排序后的console . info(' after radix sort : ' nums)；//根据对应的(一位和十位)值，将数字分配给对应的queues函数分配(nums，queues，n，digit) {//digit表示一位或十位的值为(var I=0；I n；i ){ if(数字==1){ queues[ nums[i] % 10 ]。入队(nums[I])；} else { queues[Math . floor(nums[I]/10)]。入队(nums[I])；} } }//从queues函数收集数字收集(queues，nums){ var I=0；for (var数字=0；数字10；数字){ while(！队列[数字]。empty() ){ nums[ i ]=queues[digit]。front()；队列[数字]。出列()；}}}我会把两组测试的结果贴在这里。我们自己做吧。

//第一组测试是辐射排序前： 23、39、2、67、90、41、47、21、98、13辐射排序后3360 2、13、21、23、39、41、47、67、90、98//55、26、33、54、76、65部首排序后： 16、26、29、33、38、54、55、65希望大家能发散思维。

感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具：http://tools.jb51.net/code/HtmlJsRun来测试上述代码的运行效果。

更多对JavaScript相关内容感兴趣的读者可以查看本网站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》、《JavaScript错误与调试技巧总结》和0103010

希望本文对JavaScript编程有所帮助。