第五章队列

队列介绍

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

Queue 类定义和一些测试代码

function Queue() { this.dataStore=[]; this.enqueue=enqueue; this.dequeue=dequeue; this.front=front; this.back=back; this.toString=toString; this.isEmpty=isEmpty; } //向队尾添加一个元素 function enqueue(ele) { this.dataStore.push(ele); } //删除队首的元素 function dequeue() { return this.dataStore.shift(); } function front() { return this.dataStore[0]; } function back() { return this.dataStore[this.dataStore.length-1]; } function toString() { let retStr=""; for(let i=0;i<this.dataStore.length;i++){ retStr +=this.dataStore[i]+"\n"; } return retStr; } function isEmpty() { if(this.dataStore.length<=0){ return true; }else{ return false; } } //测试 let q=new Queue(); q.enqueue('Tom'); q.enqueue('Jack'); q.enqueue('Cynthia'); q.enqueue('Jennifer'); console.log(q.toString()); q.dequeue(); console.log(q.toString()); console.log("Front of queue:"+q.front()); console.log("Back of queue:"+q.back());

队列的使用

1）方块舞的舞伴分配问题：使用队列来模拟跳方块舞的人。当 男男女女来到舞池，他们按照自己的性别排成两队。当舞池中有地方空出来时，选两个队 列中的第一个人组成舞伴。他们身后的人各自向前移动一位，变成新的队首。当一对舞伴 迈入舞池时，主持人会大声喊出他们的名字。当一对舞伴走出舞池，且两排队伍中有任意 一队没人时，主持人也会把这个情况告诉大家。

把跳方块舞的男男女女的姓名储存在一个dancers.txt文件中,引入node fs模块。

dancers.txt文件数据:

F Allison McMillan
M Frank Opitz
M Mason McMillan
M Clayton Ruff
F Cheryl Ferenback
M Raymond Williams
F Jennifer Ingram
M Bryan Frazer
M David Durr
M Danny Martin
F Aurora Adney

//舞者信息存储在Dancer对象中 function Dancer(name,sex) { this.name=name; this.sex=sex; } //从dancers.txt中读取舞者信息 function getDanners(males,females) { let names=fs.readFileSync('dancers.txt','utf-8').split("\n"); for(let i=0;i<names.length;i++) { names[i]=names[i].trim();//去除空格 } for(let i=0;i<names.length;i++) { let dancer=names[i].split(" "); let sex=dancer[0]; let 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.isEmpty()&&!males.isEmpty()){ let person=females.dequeue(); console.log("Females dancer is:"+person.name); person=males.dequeue(); console.log("Males dancer is:"+person.name); } } //测试 let maleDancers=new Queue(); let femaleDancers=new Queue(); getDanners(maleDancers,femaleDancers); console.log("maleDancers:",maleDancers); console.log("femaleDancers:",femaleDancers); dance(maleDancers,femaleDancers); if (!femaleDancers.isEmpty()) { console.log(femaleDancers.front().name+"is waiting to dance"); } if (!maleDancers.isEmpty()) { console.log(maleDancers.front().name+"is waiting to dance"); }

91, 46, 85, 15, 92, 35, 31, 22

经过基数排序第一次扫描之后，数字被分配到如下盒子中：

Bin 0:

Bin 1: 91, 31

Bin 2: 92, 22

Bin 3:

Bin 4:

Bin 5: 85, 15, 35

Bin 6: 46

Bin 7:

Bin 8:

Bin 9:

根据盒子的顺序，对数字进行第一次排序的结果如下：
91, 31, 92, 22, 85, 15, 35, 46
然后根据十位上的数值再将上次排序的结果分配到不同的盒子中：

Bin 0:

Bin 1: 15

Bin 2: 22

Bin 3: 31, 35

Bin 4: 46

Bin 5:

Bin 6:

Bin 7:

Bin 8: 85

Bin 9: 91, 92

最后，将盒子中的数字取出，组成一个新的列表，该列表即为排好序的数字：
15, 22, 31, 35, 46, 85, 91, 92

//将数字分配到对应队列 function distribute(nums,queues,n,digit) { for(let i=0;i<n;i++){ if(nums[i]==""|| !nums[i]){ continue; } if(digit==1){ queues[nums[i]%10].enqueue(nums[i]);//按个位排列 }else{ queues[Math.floor(nums[i]/10)].enqueue(nums[i]);//按十位排列 } } } //从队列中收集数字 function collect(queues,nums){ let i=0; for(let digit=0;digit<10;digit++){ while(!queues[digit].isEmpty()){ nums[i++]=queues[digit].dequeue(); } } } //展示数组内容 function dispArray(arr){ for(let i=0;i<arr.length;i++){ console.log(arr[i]+" "); } } //测试 let queues=[]; for(let i=0;i<10;i++){ queues[i]=new Queue(); } let nums=[]; for(let i=0;i<10;i++){ nums[i]=Math.floor(Math.floor(Math.random()*101)); } //nums=[91,46,85,15,92,35,31,22]; console.log("Before redix sort:"); dispArray(nums); distribute(nums,queues,10,1); collect(queues,nums); distribute(nums,queues,10,10); collect(queues,nums); console.log("After redix sort:"); dispArray(nums);

当病人进入候诊室时，分诊护士会评估患者病情的严重程度，然后给一个优先级代码。高优先级的患者先于低优先级的患者就医，同样优先级的患者按照先来先服务的顺序就医。

//定义患者对象 function Patient(name,code) { this.name=name; this.code=code; } //重新定义dequeue方法，code小的元素优先级高 function dequeue() { let priority=0; for(let i=0;i<this.dataStore.length;i++){ if(this.dataStore[i].code<this.dataStore[priority].code){ priority=i; } } return this.dataStore.splice(priority,1); } //重新定义toString方法 function toString(){ let retVar=""; for(let i=0;i<this.dataStore.length;i++){ retVar +=this.dataStore[i].name+" code:" +this.dataStore[i].code+"\n"; } return retVar; } let ed=new Queue(); let p=new Patient('Tom',5); 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()); while(!ed.isEmpty()) { let seen=ed.dequeue(); console.log("Patient being treated:"+seen[0].name); console.log("Patient waiting to be seen:") console.log(ed.toString()); }

队列练习

1.修改 Queue 类,形成一个Deque类。这是一个和队列类似的数据结构，允许从队列两端添加和删除元素，因此也叫双向队列。写一段测试程序测试该类

function Deque() { this.dataStore=[]; this.push_front=push_front; this.push_back=push_back; this.pop_front=pop_front; this.pop_back=pop_back; this.front=front; this.back=back; this.toString=toString; this.isEmpty=isEmpty; } //向队首添加一个元素 function push_front(ele) { this.dataStore.unshift(ele); } //向队尾添加一个元素 function push_back(ele) { this.dataStore.push(ele); } //删除队首的元素 function pop_front() { return this.dataStore.shift(); } //删除队尾的元素 function pop_back() { return this.dataStore.pop(); } function front() { return this.dataStore[0]; } function back() { return this.dataStore[this.dataStore.length-1]; } function toString() { let retStr=""; for(let i=0;i<this.dataStore.length;i++){ retStr +=this.dataStore[i]+"\n"; } return retStr; } function isEmpty() { if(this.dataStore.length<=0){ return true; }else{ return false; } } //测试 let d=new Deque(); d.push_back('Tom'); d.push_back('Jack'); d.push_front('Divid'); d.push_front('White'); console.log(d.toString()); d.pop_front(); console.log(d.toString()); d.pop_back(); console.log(d.toString()); 

2.使用前面完成的Deque类来判断一个给定单词是否为回文。

function isPalindrome(word) { let d=new Deque(); for(let i=0;i<word.length;i++){ d.push_front(word[i]); } let p=new Deque(); for(let i=0;i<word.length;i++){ p.push_back(word[i]); } if(d.dataStore.join("")==p.dataStore.join("")){ return true; }else{ return false; } } let word="aba"; let flag=isPalindrome(word.split("")); console.log(flag);