第五章队列

程序员文章站 2022-04-03 07:57:40

...

队列介绍

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（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");
}

2）使用队列对数据进行排序
使用一组队列来模拟基数排序.对于0~99的数字，基数排序将数据集扫描两次。第一次按个位上的数字进行排序，第二次按十位上的数字进行排序。每个数字根据对应位上的数值被分在不同的盒子里。假设有如下数字：

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);

3）医院急诊科(Emergency Department)的候诊室，就是一个采取优先队列的例子。

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

//定义患者对象
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);

相关标签： js 数据结构与算法js描述

上一篇： Java IO流-字符流

下一篇：卡通漫画系列,支持国货,父亲.

第五章队列

队列介绍

队列的使用

队列练习

PHP实现的memcache环形队列类实例

.NetCore利用BlockingCollection实现简易消息队列

Python的Flask框架应用调用Redis队列数据的方法

python 利用栈和队列模拟递归的过程

面试题【栈和队列:用两个栈实现队列】

python基于mysql实现的简单队列以及跨进程锁实例详解

JavaScript数据结构学习之数组、栈与队列

python实现最大优先队列

Python实现优先级队列结构的方法详解

PHP+memcache实现消息队列案例分享