1.使用隊列：方塊舞的舞伴分配問題　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

前面我們提到過，經常用隊列模擬排隊的人。下面我們使用隊列來模擬跳方塊舞的人。當 男男女女來到舞池，他們按照自己的性別排成兩隊。當舞池中有地方空出來時，選兩個隊 列中的第一個人組成舞伴。他們身后的人各自向前移動一位，變成新的隊首。當一對舞伴 邁入舞池時，主持人會大聲喊出他們的名字。當一對舞伴走出舞池，且兩排隊伍中有任意 一隊沒人時，主持人也會把這個情況告訴大家。 為了模擬這種情況，我們把跳方塊舞的男男女女的姓名儲存在一個文本文件中： 下面是程序代碼的實現： <script type="text/javascript"> function Queue(){this.dataStore = [];this.enqueue = enqueue;this.dequeue = dequeue;this.front = front;this.back = back;this.toString = toString;this.empty = empty;this.count = count; }/** * 向隊尾添加一個元素 */ function enqueue(element){this.dataStore.push(element); }/** * 刪除隊首的元素： */ function dequeue(){this.dataStore.shift(); }/** * 讀取隊首的元素： */ function front(){return this.dataStore[0]; }/** * 讀取隊尾的元素： */ function back(){return this.dataStore[this.dataStore.length - 1]; }/** * 顯示隊列內的所有元素 */ function toString(){var retStr = "";for (var i = 0; i < this.dataStore.length; ++i) {retStr += this.dataStore[i] + "\n";}return retStr; }/** * 判斷隊列是否為空 */ function empty(){if(this.dataStore.length == 0){return true;}else{return false;} }/** * 顯示隊列中有多少個元素 */ function count(){return this.dataStore.length; }//===================================使用Queue類============================================= /** * 每個舞者信息都被存儲在一個Dancer 對象中 */ function Dancer(name, sex) {this.name = name;this.sex = sex; }/** * 將舞者信息從文件中讀到程序里來 * trim() 函數除去了每行字符串后的空格 * 根據性別，將舞者加入不同的隊列 */ function getDancers(males, females){var names = read("dancers.txt").split("\n");for (var i = 0; i < names.length; ++i) {names[i] = names[i].trim();}for (var i = 0; i < names.length; ++i) {var dancer = names[i].split(" ");var sex = dancer[0];var name = dancer[1];if (sex == "F") {females.enqueue(new Dancer(name, sex));}else{males.enqueue(new Dancer(name, sex));}} }/** * 將男性和女性組成舞伴，并且宣布配對結果 */ function dance(males, females){console.log("The dance partners are: \n");while (!females.empty() && !males.empty()) {person = females.dequeue();console.log("Female dancer is: " + person.name);person = males.dequeue();console.log(" and the male dancer is: " + person.name);} }/** *測試程序： */ var maleDancers = new Queue(); var femaleDancers = new Queue(); getDancers(maleDancers, femaleDancers); dance(maleDancers, femaleDancers); if (!femaleDancers.empty()) {print(femaleDancers.front().name + " is waiting to dance."); } if (!maleDancers.empty()) {print(maleDancers.front().name + " is waiting to dance."); }//顯示等候跳舞的人數 if (maleDancers.count() > 0) {print("There are " + maleDancers.count() +" male dancers waiting to dance."); } if (femaleDancers.count() > 0) {print("There are " + femaleDancers.count() +" female dancers waiting to dance."); }</script> View Code

?

?

2.使用隊列對數據進行排序　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

隊列不僅用于執行現實生活中與排隊有關的操作，還可以用于對數據進行排序。 計算機剛剛出現時，程序是通過穿孔卡輸入主機的，每張卡包含一條程序語句。 這些穿孔卡裝在一個盒子里，經一個機械裝置進行排序。我們可以使用一組隊列來模擬這一過程。 這種排序技術叫做基數排序，它不是最快的排序算法，但是它展示了一些有趣的隊列使用方法。 對于0~99 的數字，基數排序將數據集掃描兩次。 第一次按個位上的數字進行排序，第二次按十位上的數字進行排序。每個數字根據對應位上的數值被分在不同的盒子里。 假設有如下數字： 91, 46, 85, 15, 92, 35, 31, 22 經過基數排序第一次掃描之后，數字被分配到如下盒子中：

根據盒子的順序，對數字進行第一次排序的結果如下： 91, 31, 92, 22, 85, 15, 35, 46 然后根據十位上的數值再將上次排序的結果分配到不同的盒子中： 最后，將盒子中的數字取出，組成一個新的列表，該列表即為排好序的數字： 15, 22, 31, 35, 46, 85, 91, 92 使用隊列代表盒子，可以實現這個算法。 我們需要十個隊列，每個對應一個數字。將所有隊列保存在一個數組中，使用取余和除法操作決定個位和十位。 算法的剩余部分將數字加入相應的隊列，根據個位數值對其重新排序，然后再根據十位上的數值進行排序， 結果即為排好序的數字。 下面是代碼的實現： <script type="text/javascript"> function Queue(){this.dataStore = [];this.enqueue = enqueue;this.dequeue = dequeue;this.front = front;this.back = back;this.toString = toString;this.empty = empty;this.count = count; }/** * 向隊尾添加一個元素 */ function enqueue(element){this.dataStore.push(element); }/** * 刪除隊首的元素： */ function dequeue(){return this.dataStore.shift(); }/** * 讀取隊首的元素： */ function front(){return this.dataStore[0]; }/** * 讀取隊尾的元素： */ function back(){return this.dataStore[this.dataStore.length - 1]; }/** * 顯示隊列內的所有元素 */ function toString(){var retStr = "";for (var i = 0; i < this.dataStore.length; ++i) {retStr += this.dataStore[i] + "\n";}return retStr; }/** * 判斷隊列是否為空 */ function empty(){if(this.dataStore.length == 0){return true;}else{return false;} }/** * 顯示隊列中有多少個元素 */ function count(){return this.dataStore.length; }//===================================使用Queue類============================================= /** * 根據相應位（個位或十位）上的數值,將數字分配到相應隊列 * nums: 待排序的數組 * queues: 隊列數組 * n: nums的length * 參數digit 1-按照個位數排序，10-按照十位數排序 */ function distribute(nums, queues, n, digit){for(var i=0; i<n; i++){if(digit == 1){queues[nums[i]%10].enqueue(nums[i]);}else{var k = Math.floor(nums[i]/10); queues[k].enqueue(nums[i]);}} }/** * 從隊列中收集數字的函數 */ function collect(queues, nums){var i=0;for(var j=0; j<queues.length; j++){while(!queues[j].empty()){nums[i++] = queues[j].dequeue();}} }//測試程序 //1.定義queues 和 nums var queues = []; for (var i = 0; i < 10; ++i) {queues[i] = new Queue(); } var nums = []; for (var i = 0; i < 10; ++i) {nums[i] = Math.floor(Math.random() * 101); }console.log("Before radix sort: "); console.log(nums); distribute(nums, queues, nums.length, 1); //按照個位數進行第一次排序 collect(queues, nums); //對按照個位數排好序的隊列，每個隊列挨排出列，組成新的數組 distribute(nums, queues, nums.length, 10); //按照十位數進行第二次排序 collect(queues, nums); console.log("After radix sort: "); console.log(nums);</script> View Code

打印出來如下：

?

?

3.優先隊列：

在一般情況下，從隊列中刪除的元素，一定是率先入隊的元素。 但是也有一些使用隊列的應用，在刪除元素時不必遵守先進先出的約定。這種應用，需要使用一個叫做優先隊列的數據結構來進行模擬。 從優先隊列中刪除元素時， 需要考慮優先權的限制。 比如醫院急診科的候診室，就是一個采取優先隊列的例子。當病人進入候診室時，分診護士會評估患者病情的嚴重程度，然后給一個優先級代碼。高優先級的患者先于低優先級的患者就醫，同樣優先級的患者按照先來先服務的順序就醫。 先來定義存儲隊列元素的對象，然后再構建我們的優先隊列系統： function Patient(name, code) { this.name = name; this.code = code; } 變量code 是一個整數，表示患者的優先級或病情嚴重程度。 現在需要重新定義dequeue() 方法，使其刪除隊列中擁有最高優先級的元素。 我們規定：優先碼的值最小的元素優先級最高。 新的dequeue() 方法遍歷隊列的底層存儲數組，從中找出優先碼最低的元素，然后使用數組的splice() 方法刪除優先級最高的元素。 最后，需要定義toString() 方法來顯示Patient 對象。 代碼實現如下： <script type="text/javascript"> function Queue(){this.dataStore = [];this.enqueue = enqueue;this.dequeue = dequeue;this.front = front;this.back = back;this.toString = toString;this.empty = empty;this.count = count; }/** * 向隊尾添加一個元素 */ function enqueue(element){this.dataStore.push(element); }/** * 使用簡單的順序查找方法尋找優先級最高的元素（優先碼越小優先級越高，比如，1 比5 的優先級高） * 返回包含一個元素的數組——從隊列中刪除的元素。 * * 假設第0個位置的優先級最小。 * 找到比這個優先級更小的位置，然后更新位置。 */ function dequeue(){var priority = 0;for(var i=1; i<this.dataStore.length; i++){if(this.dataStore[i].code < this.dataStore[priority].code){priority = i;}}return this.dataStore.splice(priority, 1); }/** * 讀取隊首的元素： */ function front(){return this.dataStore[0]; }/** * 讀取隊尾的元素： */ function back(){return this.dataStore[this.dataStore.length - 1]; }/** * 顯示隊列內的所有元素 */ function toString(){var retStr = "";for (var i = 0; i < this.dataStore.length; ++i) {retStr += this.dataStore[i].name + ", code: "+ this.dataStore[i].code + "\n";}return retStr; }/** * 判斷隊列是否為空 */ function empty(){if(this.dataStore.length == 0){return true;}else{return false;} }/** * 顯示隊列中有多少個元素 */ function count(){return this.dataStore.length; }//===================================使用Queue類============================================= function Patient(name, code) {this.name = name;this.code = code; }//優先隊列的實現： var p = new Patient("Smith",5); var ed = new Queue(); ed.enqueue(p); p = new Patient("Jones", 4); ed.enqueue(p); p = new Patient("Fehrenbach", 6); ed.enqueue(p); p = new Patient("Brown", 1); ed.enqueue(p); p = new Patient("Ingram", 1); ed.enqueue(p); console.log(ed.toString()); console.log("-------------------------------");var seen = ed.dequeue(); console.log("Patient being treated: " + seen[0].name); console.log("Patients waiting to be seen: "); console.log(ed.toString()); console.log("-------------------------------");// 下一輪 var seen = ed.dequeue(); console.log("Patient being treated: " + seen[0].name); console.log("Patients waiting to be seen: "); console.log(ed.toString()); console.log("-------------------------------");var seen = ed.dequeue(); console.log("Patient being treated: " + seen[0].name); console.log("Patients waiting to be seen: "); console.log(ed.toString());</script>

打印結果：

?

轉載于:https://www.cnblogs.com/tenWood/p/7215502.html

總結

以上是生活随笔為你收集整理的数据结构与算法JavaScript描述——使用队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。