隊列是一種列表,不同的是隊列只能在隊尾插入元素,在隊首刪除元素。佇列用來儲存依序排列的數據,先進先出,這點和棧不一樣(後入先出)。在堆疊中,最後入棧的元素反而優先處理。我們現在可以把隊列想像對我們去餐廳吃飯的情景,很多人排隊吃飯,排在最前面的人先打飯。新來的人只能在後面排隊。直到輪到他們為止。本文主要介紹了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類別;
function Queue() { this.dataStore = []; }如上:
this.dataStore = []; 空數組時儲存佇列中所有的元素的。
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佇列原理與用法實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章!