数据结构与算法JavaScript描述——使用队列

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描述——使用队列的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。