本文实例讲述了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 cq.dequeue();console.log(q.toString()); // b cconsole.log("Front of queue:" +q.front()); // bconsole.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 或者 90queues[1] = 81 或者 91queues[2] = 12 或者 72queues[3] = 3queues[4] = 74queues[5] = 95queues[6] queues[7] = 7queues[8]queues[9]
根据盒子的顺序，对数字第一次个位排序后结果如下：
nums = [50,90,81,91,12,72,3,74,95,7]
2. 然后根据十位上的数值再将上次排序后的结果分配到不同的盒子中。如下：
queues[5] = 50queues[9] = 90queues[8] = 81queues[9] = 91queues[1] = 12queues[7] = 72queues[0] = 3queues[7] = 74queues[9] = 95queues[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程序设计有所帮助。
新闻热点
疑难解答
