JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之隊列原理與用法實例詳解
本文實例講述了JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之隊列原理與用法。分享給大家供大家參考，具體如下：
隊列是一種列表，不同的是隊列只能在隊尾插入元素，在隊首刪除元素。隊列用于存儲按順序排列的數(shù)據(jù)，先進先出，這點和棧不一樣(后入先出)。在棧中，最后入棧的元素反而被優(yōu)先處理。我們現(xiàn)在可以把隊列想象對我們?nèi)ゲ宛^吃飯的情景，很多人排隊吃飯，排在最前面的人先打飯。新來的人只能在后面排隊。直到輪到他們?yōu)橹埂?/p>
一：對隊列的操作
隊列有2種主要的操作，向隊尾中插入新元素enqueue()方法和刪除隊列中的隊首的元素的dequeue()方法，另外我們還有一個讀取隊頭的元素，這個方法我們可以叫front()方法。該方法返回隊頭元素等等方法。
看到如上描述，我們很多人可能會想到數(shù)組，數(shù)組里面也有2個方法和上面的方法功能類似，數(shù)組中push()方法也是往數(shù)組后面加入新元素，數(shù)組中shift()方法則可以刪除數(shù)組里面的第一個元素。如下代碼：
var arrs = [];
arrs.push("a");
arrs.push("b");
console.log(arrs); // ["a","b"];
arrs.shift();
console.log(arrs); // ['b'];
下面我們可以使用上面的數(shù)組中的push()和shift()的2個方法來封裝我們的隊列Queue類；
1. 我們可以先定義一個構(gòu)造函數(shù)Queue類，如下：
function Queue() {
this.dataStore = [];
}
如上：this.dataStore = []; 空數(shù)組時存儲隊列中所有的元素的。
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];
},
// 顯示隊列內(nèi)的所有元素
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;
}
}
};
我們現(xiàn)在可以對以上代碼測試下：如下：
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
二：使用隊列對數(shù)據(jù)進行排序
比如對于 0 ~ 99 的數(shù)字進行排序，原理是：先對個位上的數(shù)字進行排序一次，然后對十位上的數(shù)字再進行排序一次。每個數(shù)字根據(jù)對應位上的數(shù)值被分在不同的盒子里面，然后對于個位上的數(shù)字采用除余數(shù)的方法，對于10位上的數(shù)字采用除法的方法，那么這種排序叫做 “基數(shù)排序”. 但是它不是最快的排序方法，但是它描述了一些有趣的隊列使用方法。
比如如下數(shù)組：
var nums = ["50","12","95","7","90","3","74","81","91","72"];
1. 經(jīng)過基數(shù)排序--個位排序后，數(shù)字被分配在不同的盒子里面。（在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]
根據(jù)盒子的順序，對數(shù)字第一次個位排序后結(jié)果如下：
nums = [50,90,81,91,12,72,3,74,95,7]
2. 然后根據(jù)十位上的數(shù)值再將上次排序后的結(jié)果分配到不同的盒子中。如下：
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
最后，將盒子中的數(shù)字取出，組成一個新的列表，該列表即為排序好的數(shù)字。如下：
即可生成如下：
nums = [3,7,12,50,72,74,81,90,91,95];
如上使用隊列列表盒子，可以實現(xiàn)這個算法，我們需要10個隊列，每個隊列對應一個數(shù)字，將所有隊列保存在一個數(shù)組中，使用取余和除法操作決定個位和十位。算法的剩余部分將數(shù)字加入相應的隊列，根據(jù)個位數(shù)值進行重新排序，然后再根據(jù)十位上的數(shù)值進行排序，結(jié)果加入排序好的數(shù)字。
下面根據(jù)個位或十位上的數(shù)值，將數(shù)字分配到相應隊列的函數(shù)。
/*
* 根據(jù)個位或十位上的數(shù)值，將數(shù)字分配到相應隊列的函數(shù)
* @param digit
* digit=1 表示先按個位來分配
* digit = 10 表示是按十位來分配的
* @param n 表示循環(huán)比較多少次 一般數(shù)組幾個數(shù)字就比較多少次
*/
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]);
}
}
}
下面是從隊列中收集數(shù)字的函數(shù)如下：
// 收集數(shù)字的函數(shù)
collect: function(queues,nums,n) {
var i = 0;
for(var digit = 0; digit < n; ++digit) {
while(!queues[digit].empty()) {
nums[i++] = queues[digit].dequeue();
}
}
}
由于上面省略了很多步驟，可能描述的不是很清楚，我們現(xiàn)在先來看看流程圖，結(jié)合流程圖，最后結(jié)合JS的所有代碼就可以理解"基數(shù)排序的"基本原理了；下面我們可以看看如下的流程圖；
最后是所有的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];
},
// 顯示隊列內(nèi)的所有元素
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;
}
},
/*
* 根據(jù)個位或十位上的數(shù)值，將數(shù)字分配到相應隊列的函數(shù)
* @param digit
* digit=1 表示先按個位來分配
* digit = 10 表示是按十位來分配的
* @param n 表示循環(huán)比較多少次 一般數(shù)組幾個數(shù)字就比較多少次
*/
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]);
}
}
},
// 收集數(shù)字的函數(shù)
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]);
}
}
};
下面的是對 "基數(shù)排序的" 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);
如上測試代碼 大家可以運行下 就可以看到排序后的效果！
更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學運算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯誤與調(diào)試技巧總結(jié)》
希望本文所述對大家JavaScript程序設計有所幫助。
相關(guān)文章
JavaScript創(chuàng)建對象方式總結(jié)【工廠模式、構(gòu)造函數(shù)模式、原型模式等】
這篇文章主要介紹了JavaScript創(chuàng)建對象方式,結(jié)合實例形式總結(jié)分析了工廠模式、構(gòu)造函數(shù)模式、原型模式等各種常見的javascript對象創(chuàng)建方式與相關(guān)操作注意事項,需要的朋友可以參考下2018-12-12
不同的排序算法，執(zhí)行效率有著天壤之別，本腳本用JavaScript演示了各種常見的排序算法，包括：冒泡排序、選擇排序、插入排序、謝爾排序、快速排序(遞歸)、快速排序(堆棧)、歸并排序、堆排序2014-09-09
本文這里給大家總結(jié)了一些常用的javascript方法，都是些短小精悍的小代碼，提高執(zhí)行效率，這里推薦給大家。2015-02-02
本文主要分享了js實現(xiàn)無縫滾動圖的示例代碼，具有很好的參考價值，下面跟著小編一起來看下吧2017-02-02
JavaScript 對Cookie 操作的封裝小結(jié)
通過本篇,您能了解到: 匿名函數(shù) 閉包的產(chǎn)生 JavaScript實現(xiàn)private 以及 public 訪問權(quán)限 document.cookie 的操作2009-12-12
JS也玩OO繼承...2007-01-01
bootstrap-table組合表頭的實現(xiàn)方法
本篇文章主要介紹了bootstrap-table組合表頭的實現(xiàn)方法，非常具有實用價值，需要的朋友可以參考下2017-09-09
這篇文章主要為大家詳細介紹了js實現(xiàn)簡單選項卡制作，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-08-08
這篇文章主要為大家詳細介紹了微信小程序?qū)崿F(xiàn)選項卡的方法，利用swiper組件實現(xiàn)選項卡功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-07-07
最近使用for-in語句遍歷對象屬性時發(fā)現(xiàn)遍歷順序并非屬性構(gòu)建順序,這篇文章主要給大家介紹了關(guān)于JS?for?in遍歷對象順序不對的解決辦法,需要的朋友可以參考下2023-11-11