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

本文实例讲述了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的所有代码就可以理解"基数排序的"基本原理了;下面我们可以看看如下的流程图;

最后是所有的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程序设计有所帮助。

(0)

相关推荐

  • JavaScript数据结构与算法之栈与队列

    学习起因 曾经有一次在逛V2EX时,碰到这么一个帖子. 数学完全还给老师了,想学回一些基础数学,大概是高中程度的,有什么书籍推荐? 发帖的楼主大学没有高数课程,出去工作时一直在从事前端的工作.感觉到数学知识的匮乏,所以想补一补数学. 看了看帖子,感觉和我很像,因为我的专业是不开高数的,我学的也是前端.也同样感觉到了数学知识匮乏所带来的困顿.同时因为自己的数学思维实在是不怎么好,所以决定努力补习数学与计算机基础知识. 当时也有人说:"前端需要什么数据结构与算法",但是对于这个事情我有自己

  • JavaScript中数据结构与算法(二):队列

    队列是只允许在一端进行插入操作,另一个进行删除操作的线性表,队列是一种先进先出(First-In-First-Out,FIFO)的数据结构 队列在程序程序设计中用的非常的频繁,因为javascript单线程,所以导致了任何一个时间段只能执行一个任务,而且还参杂了异步的机制, 那么带来的问题: 1. 在异步操作执行的时候,同步代码还在继续,那么同步代码依赖异步,自然就会出错 2. 多个同步的任务在不同的时间段被调用 jQuery的动画中,我们经常写一段连续的动画代码 $book.animate({

  • javascript中利用数组实现的循环队列代码

    //循环队列 function CircleQueue(size){ this.initQueue(size); } CircleQueue.prototype = { //初始化队列 initQueue : function(size){ this.size = size; this.list = new Array(); this.capacity = size + 1; this.head = 0; this.tail = 0; }, //压入队列 enterQueue : functio

  • JavaScript队列、优先队列与循环队列

    队列是一种遵从先进先出(FIFO)原则的有序集合 队列在尾部添加新元素,从顶部移除元素 队列的理解 队列在我们生活中最常见的场景就是排队了 队列这个名字也已经很通俗易懂了 和栈很像,这不过队列是先入先出的数据结构 队列的前面是队头 队列的后面是队尾 出队从队头出 入队从队尾入 队列的创建 和栈类似,这里我就不就不啰嗦了 同样需要实现一些功能 这里我类比生活中的排队上厕所 向队列中添加元素(进入排队的队伍中) 移除队头元素(队伍最前面的人出队进入厕所) 查看队头元素(查看队伍最前面的人) 判断队列

  • JavaScript队列的应用实例详解【经典数据结构】

    本文实例讲述了JavaScript队列的应用.分享给大家供大家参考,具体如下: 和前面介绍的栈相反,队列是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端进行删除.JavaScript自己提供了两个队列方法shift和push方法,分别是出队和入队,其原理就是将元素插入数组最后一个和删除第一个元素. 这里需要注意一点,就是unshift方法的效率比push的效率要低很多.因为它要将入队之前的数组全部往前移动一位.这里我们就不用代码再次演示了. 和线性表类似,队列也分为顺序队列和链队列

  • JavaScript中数据结构与算法(三):链表

    我们可以看到在javascript概念中的队列与栈都是一种特殊的线性表的结构,也是一种比较简单的基于数组的顺序存储结构.由于javascript的解释器针对数组都做了直接的优化,不会存在在很多编程语言中数组固定长度的问题(当数组填满后再添加就比较困难了,包括添加删除,都是需要把数组中所有的元素全部都变换位置的,javascript的的数组确实直接给优化好了,如push,pop,shift,unshift,split方法等等-) 线性表的顺序存储结构,最大的缺点就是改变其中一个元素的排列时都会引起

  • 深入JavaScript高级程序设计之对象、数组(栈方法,队列方法,重排序方法,迭代方法)

    继承是OO语言中的一个最为人津津乐道的概念. 许多OO语言都支持两种继承方式:接口继承和实现继承. 接口继承只继承方法签名,而实现继承则继承实际的方法. 如其所述,由于函数没有签名,在ECMAScript中无法实现接口继承. ECMAScript只支持实现继承,而且其实现继承主要是依靠原型链来实现的. 1.使用对象字面量定义对象 var person={}; 使用这种方式创建对象时,实际上不会调用Object构造函数. 开发人员更喜欢对象字面量的语法. 2.有时候需要传递大量可选参数的情形时,一

  • JavaScript数组的栈方法与队列方法详解

    数组(Array)和对象(Object)应该是JavaScript中使用最多也是最频繁的两种类型了,Array提供了很多常用的方法:栈方法.队列方法.重排序方法.操作方法.位置方法.迭代方法等等. 1.Array的栈方法 栈是一种LIFO(Last-In-First-Out,后进先出)的数据结构,也就是最新添加的项最早被移除.栈中项的插入(push)和移除,只发生在一个位置--栈的顶部.ECMAScript为数组提供了push()和pop()方法,可以实现类似栈的行为.下面两图分别演示了入栈与出

  • JavaScript数组实现数据结构中的队列与堆栈

    一.队列和堆栈的简单介绍 1.1.队列的基本概念 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 如下图所示: 1.2.堆栈的基本概念 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 如下图所示: 二. 在JavaScript中实现队列和堆栈 在JavaScript中实现队列和数组主要是通过数组,js数组中提供了以下几个方法可以让我们很方便实现队列和堆栈: •shift:从数组中把第一个元素删除,并返回这个元素的值. •unshift: 在数组

  • JavaScript中数据结构与算法(四):串(BF)

    串是由零个或多个字符组成的有限序列,又叫做字符串 串的逻辑结构和线性表很相似的,不同的是串针对是是字符集,所以在操作上与线性表还是有很大区别的.线性表更关注的是单个元素的操作CURD,串则是关注查找子串的位置,替换等操作. 当然不同的高级语言对串的基本操作都有不同的定义方法,但是总的来说操作的本质都是相似的.比如javascrript查找就是indexOf, 去空白就是trim,转化大小写toLowerCase/toUpperCase等等 这里主要讨论下字符串模式匹配的几种经典的算法:BF.BM

  • JavaScript中数据结构与算法(一):栈

    序 数据结构与算法JavaScript这本书算是讲解得比较浅显的,优点就是用javascript语言把常用的数据结构给描述了下,书中很多例子来源于常见的一些面试题目,算是与时俱进,业余看了下就顺便记录下来吧 git代码下载:https://github.com/JsAaron/data_structure.git 栈结构 特殊的列表,栈内的元素只能通过列表的一端访问,栈顶 后入先出(LIFO,last-in-first-out)的数据结构 javascript提供可操作的方法, 入栈 push,

随机推荐