杰晶网络

JavaScript数据结构与算法之队列原理与用法实例详解
网络编程 2024/11/9 佚名
3 2

本文实例讲述了JavaScript数据结构与算法之队列原理与用法。分享给大家供大家参考，具体如下：

队列是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。队列用于存储按顺序排列的数据，先进先出，这点和栈不一样(后入先出)。在栈中，最后入栈的元素反而被优先处理。我们现在可以把队列想象对我们去餐馆吃饭的情景，很多人排队吃饭，排在最前面的人先打饭。新来的人只能在后面排队。直到轮到他们为止。

一：对队列的操作

队列有2种主要的操作，向队尾中插入新元素enqueue()方法和删除队列中的队首的元素的dequeue()方法，另外我们还有一个读取队头的元素，这个方法我们可以叫front()方法。该方法返回队头元素等等方法。

看到如上描述，我们很多人可能会想到数组，数组里面也有2个方法和上面的方法功能类似，数组中push()方法也是往数组后面加入新元素，数组中shift()方法则可以删除数组里面的第一个元素。如下代码：

var arrs = [];
arrs.push("a");
arrs.push("b");
console.log(arrs); // ["a","b"];
arrs.shift();
console.log(arrs); // ['b'];

下面我们可以使用上面的数组中的push()和shift()的2个方法来封装我们的队列Queue类；

1.  我们可以先定义一个构造函数Queue类，如下：

function Queue() {
  this.dataStore = [];
}

如上：this.dataStore = []; 空数组时存储队列中所有的元素的。

2. 向队尾中添加一个元素方法如下：

function enqueue(element) {
   this.dataStore.push(element);
}

3. 删除队首的元素如下：

function dequeue() {
  return this.dataStore.shift()
}

4. 读取队首的元素如下：

function front() {
  return this.dataStore[0];
}

5. 读取队尾的元素如下：

function back() {
  return this.dataStore[this.dataStore.length - 1];
}

6. 显示队列中的所有元素

function toString() {
  var retStr = "";
  for(var i = 0; i < this.dataStore.length; ++i) {
    retStr += this.dataStore[i] + "\n";
  }
  return retStr;
}

7. 判断队列是否为空如下：

function empty(){
  if(this.dataStore.length == 0) {
    return true;
  }else {
    return false;
  }
}

下面是完整的JS代码如下：

function Queue() {
  this.dataStore = [];
}
Queue.prototype = {
  // 向队尾添加一个元素
  enqueue: function(element) {
    this.dataStore.push(element);
  },
  // 删除队首的元素
  dequeue: function(){
    return this.dataStore.shift();
  },
  // 读取队首的元素
  front: function(){
    return this.dataStore[0];
  },
  // 读取队尾的元素
  back: function(){
    return this.dataStore[this.dataStore.length - 1];
  },
  // 显示队列内的所有元素
  toString: function(){
    var retStr = "";
    for(var i = 0; i < this.dataStore.length; ++i) {
      retStr += this.dataStore[i] + "\n";
    }
    return retStr;
  },
  // 判断队列是否为空
  empty: function(){
    if(this.dataStore.length == 0) {
      return true;
    }else {
      return false;
    }
  }
};

我们现在可以对以上代码测试下：如下：

var q = new Queue();
q.enqueue("a");
q.enqueue("b");
q.enqueue("c");
console.log(q.toString()); // a b c
q.dequeue();
console.log(q.toString()); // b c
console.log("Front of queue:" +q.front()); // b
console.log("Back of queue:" +q.back()); // c

二：使用队列对数据进行排序

比如对于 0 ~ 99 的数字进行排序，原理是：先对个位上的数字进行排序一次，然后对十位上的数字再进行排序一次。每个数字根据对应位上的数值被分在不同的盒子里面，然后对于个位上的数字采用除余数的方法，对于10位上的数字采用除法的方法，那么这种排序叫做 “基数排序”. 但是它不是最快的排序方法，但是它描述了一些有趣的队列使用方法。

比如如下数组：

var nums = ["50","12","95","7","90","3","74","81","91","72"];

1. 经过基数排序--个位排序后，数字被分配在不同的盒子里面。（在JS里面，我们可以分配在不同的队列Queue实例类里面）。如下

queues[0] = 50 或者 90
queues[1] = 81 或者 91
queues[2] = 12 或者 72
queues[3] = 3
queues[4] = 74
queues[5] = 95
queues[6] 
queues[7] = 7
queues[8]
queues[9]

根据盒子的顺序，对数字第一次个位排序后结果如下：

nums = [50,90,81,91,12,72,3,74,95,7]

2. 然后根据十位上的数值再将上次排序后的结果分配到不同的盒子中。如下：

queues[5] = 50
queues[9] = 90
queues[8] = 81
queues[9] = 91
queues[1] = 12
queues[7] = 72
queues[0] = 3
queues[7] = 74
queues[9] = 95
queues[0] = 7

最后，将盒子中的数字取出，组成一个新的列表，该列表即为排序好的数字。如下：

即可生成如下：

nums = [3,7,12,50,72,74,81,90,91,95];

如上使用队列列表盒子，可以实现这个算法，我们需要10个队列，每个队列对应一个数字，将所有队列保存在一个数组中，使用取余和除法操作决定个位和十位。算法的剩余部分将数字加入相应的队列，根据个位数值进行重新排序，然后再根据十位上的数值进行排序，结果加入排序好的数字。

下面根据个位或十位上的数值，将数字分配到相应队列的函数。

/*
* 根据个位或十位上的数值，将数字分配到相应队列的函数
* @param digit
* digit=1 表示先按个位来分配
* digit = 10 表示是按十位来分配的
* @param n 表示循环比较多少次 一般数组几个数字就比较多少次
*/
distribute: function(nums,queues,n,digit){
   for(var i = 0; i < n; ++i) {
    if(digit == 1) {
      queues[nums[i] % 10].enqueue(nums[i]);
     }else {
      queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
     }
   }
}

下面是从队列中收集数字的函数如下：

// 收集数字的函数
collect: function(queues,nums,n) {
  var i = 0;
  for(var digit = 0; digit < n; ++digit) {
    while(!queues[digit].empty()) {
      nums[i++] = queues[digit].dequeue();
    }
  }
}

由于上面省略了很多步骤，可能描述的不是很清楚，我们现在先来看看流程图，结合流程图，最后结合JS的所有代码就可以理解"基数排序的"基本原理了；下面我们可以看看如下的流程图；

JavaScript数据结构与算法之队列原理与用法实例详解

最后是所有的JS代码如下：

function Queue() {
  this.dataStore = [];
}
Queue.prototype = {
  // 向队尾添加一个元素
  enqueue: function(element) {
    this.dataStore.push(element);
  },
  // 删除队首的元素
  dequeue: function(){
    return this.dataStore.shift();
  },
  // 读取队首的元素
  front: function(){
    return this.dataStore[0];
  },
  // 读取队尾的元素
  back: function(){
    return this.dataStore[this.dataStore.length - 1];
  },
  // 显示队列内的所有元素
  toString: function(){
    var retStr = "";
    for(var i = 0; i < this.dataStore.length; ++i) {
      retStr += this.dataStore[i] + "\n";
    }
    return retStr;
  },
  // 判断队列是否为空
  empty: function(){
    if(this.dataStore.length == 0) {
      return true;
    }else {
      return false;
    }
  },
  /*
   * 根据个位或十位上的数值，将数字分配到相应队列的函数
   * @param digit
   * digit=1 表示先按个位来分配
   * digit = 10 表示是按十位来分配的
   * @param n 表示循环比较多少次 一般数组几个数字就比较多少次
   */
  distribute: function(nums,queues,n,digit){
    for(var i = 0; i < n; ++i) {
      if(digit == 1) {
        queues[nums[i] % 10].enqueue(nums[i]);
      }else {
        queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
      }
    }
  },
  // 收集数字的函数
  collect: function(queues,nums,n) {
    var i = 0;
    for(var digit = 0; digit < n; ++digit) {
      while(!queues[digit].empty()) {
        nums[i++] = queues[digit].dequeue();
      }
    }
  },
  dispArray: function(arr) {
    for(var i = 0; i < arr.length; ++i) {
      console.log(arr[i]);
    }
  }
};

下面的是对 "基数排序的" JS代码进行测试；如下代码：

var q = new Queue();
  q.enqueue("a");
  q.enqueue("b");
  q.enqueue("c");
console.log(q.toString());
q.dequeue();
console.log(q.toString());
console.log("Front of queue:" +q.front());
console.log("Back of queue:" +q.back());
var queues = [];
for(var i = 0; i < 10; ++i) {
   queues[i] = new Queue();
}
var nums = ["50","12","95","7","90","3","74","81","91","72"];
console.log("before radix sort: ");
console.log(nums);
q.distribute(nums,queues,10,1);
q.collect(queues,nums,10);
q.dispArray(nums);
console.log("分割线");
q.distribute(nums,queues,10,10);
q.collect(queues,nums,10);
q.dispArray(nums);

如上测试代码 大家可以运行下 就可以看到排序后的效果！

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

希望本文所述对大家JavaScript程序设计有所帮助。

标签：
JavaScript,数据结构,算法,队列
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
www.imxmx.com 杰晶网络
8,675无损音乐
1,324高清电影
213破解软件
120,141站长资源
一句话新闻
苹果官宣WWDC 2024！预计会有大批AI功能 - 2024/11/9

3月27日消息，苹果宣布2024年全球开发者大会（WWDC）将于6月10日至6月14日举行，巧合的是，这次大会与端午假期重合。

苹果官方表示：

在线参加 Apple 每年规模最大的开发者盛会。亲眼见证 Apple 最新平台、技术和工具的发布。了解如何创建和改进你的 App 和游戏。与 Apple 设计师和工程师互动交流，与全球开发者社区建立联系。以上活动均免费在线举行。

探索各种新的工具、框架和功能，助力你打造出理想的 App 和游戏。通过视频讲座学习新技能，与 Apple 专家进行一对一会面，以推进你的项目，完善你的构思。

Swift Student Challenge 旨在支持和鼓舞下一代开发者、创作者和企业家。太平洋时间 3 月 28 日，我们将公布今年的获奖者名单。获奖者将有资格参加在 Apple Park 举办的特别活动。我们还会选出 50 名杰出获胜者，他们将受邀前往库比提诺，获得为期三天的非凡体验，包括参加 Apple Park 的特别活动。

RTX 5090要首发 性能要翻倍！三星展示GDDR7显存

三星在GTC上展示了专为下一代游戏GPU设计的GDDR7内存。

首次推出的GDDR7内存模块密度为16GB，每个模块容量为2GB。其速度预设为32 Gbps（PAM3），但也可以降至28 Gbps，以提高产量和初始阶段的整体性能和成本效益。

据三星表示，GDDR7内存的能效将提高20%，同时工作电压仅为1.1V，低于标准的1.2V。通过采用更新的封装材料和优化的电路设计，使得在高速运行时的发热量降低，GDDR7的热阻比GDDR6降低了70%。

更新动态

友情链接

杰晶网络 DDR爱好者之家 南强小屋 黑松山资源网 白云城资源网