【JS数据结构】优先级队列 PriorityQueue
程序员文章站
2022-06-05 09:15:06
...
目录
与队列相比：优先级队列的每个元素都有一个优先权。
1、创建内部类。
首先，这里需要封装一个内部类。表示可以通过此类来创建一个带权值的元素。
// 在PriorityQueue重新创建一个类，可以理解为内部类
function QueueElement(element,priority){
this.element = element;
this.priority = priority;
}2、定义属性
以数组的形式存储数据。
// 属性
this.items = [];dequeue()、front()、isEmpty()、size()、toString()方法与队列一样，可查看【JS数据结构】队列（Queue）、队列的封装及其应用
3、优先级队列中插入元素的封装。
// 封装enqueue函数，将带权值的元素加入到队列中。
PriorityQueue.prototype.enqueue = function(element, priority){
// 定义一个队列对象
var qE = new QueueElement(element, priority);
// 判断队列是否为空
if(this.items.length == 0){
this.items.push(qE);
}else{
var flag = false; //flag作为旗子
for (var i = 0; i < this.items.length; i++) {
if(qE.priority < this.items[i].priority){
this.items.splice(i, 0, qE);
flag = true;
break;
}
}
if(!flag){
this.items.push(qE);
}
}
};封装enqueue函数，将带权值的元素加入到队列中。需要传入两个参数，一个是要插入的元素（qE），另一个是该元素带的权值（priority）
有三种情况：
1.当队列的长度为0时，直接使用push方法将元素加入队列中。
2.当队列的长度不为0时，又分两种，一种是根据优先级插入到队列之中
3.另一种是根据优先级插入到队列的尾部。
4、代码检验
var pq = new PriorityQueue();
pq.enqueue('abc',111);
pq.enqueue('cba',200);
pq.enqueue('nba',50);
pq.enqueue('nj',66);
alert(pq); //nba nj abc cba
5、完整代码
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>优先级队列</title>
</head>
<body>
<script type="text/javascript">
//优先级队列封装
function PriorityQueue(){
// 在PriorityQueue重新创建一个类，可以理解为内部类
function QueueElement(element,priority){
this.element = element;
this.priority = priority;
}
// 属性
this.items = [];
// 队列的相关操作，与队列不同的是，考虑优先级的先后顺序
// 1、封装enqueue函数，将元素加入到队列中。
PriorityQueue.prototype.enqueue = function(element, priority){
// 定义一个队列对象
var queueElement = new QueueElement(element, priority);
// 判断队列是否为空
if(this.items.length == 0){
this.items.push(queueElement);
}else{
var flag = false;
for (var i = 0; i < this.items.length; i++) {
if(queueElement.priority < this.items[i].priority){
this.items.splice(i, 0, queueElement);
flag = true;
break;
}
}
if(!flag){
this.items.push(queueElement);
}
}
};
// 2、从队列中删除前端的元素
PriorityQueue.prototype.dequeue = function(){
return this.items.shift();
};
// 3、查看前端的元素
PriorityQueue.prototype.front = function(){
return this.items[0];
};
// 4、判断队列是否为空
PriorityQueue.prototype.isEmpty = function(){
return this.items.length === 0;
};
// 5、获取队列中的元素个数
PriorityQueue.prototype.size = function(){
return this.items.length;
};
// 6、toString 方法
PriorityQueue.prototype.toString = function(){
var resultString = '';
for (var i = 0; i < this.items.length; i++) {
resultString += this.items[i].element + ' ';
}
return resultString;
};
}
var pq = new PriorityQueue();
pq.enqueue('abc',111);
pq.enqueue('cba',200);
pq.enqueue('nba',50);
pq.enqueue('nj',66);
alert(pq); //nba nj abc cba
</script>
</body>
</html>