前端 《学习JavaScript数据结构与算法》笔记

lixin1182905103 · March 01, 2020 · 6 hits

概念

1.优先队列和队列的主要区别就是,队列中每个元素不仅含有自身的元素,还有一个代表该元素优先级的标识。
2.在插入新的元素到队列时,根据该元素的优先级来决定它插入的正确位置。
3.优先队列具有最高级先出队列的行为特征

封装优先级队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function () {

this.items = [];
// 创建一个包含元素内容和优先级的类
function QueueElement(element, priority) {
this.element = element;
this.priority = priority;
};
// 实现插入方法
PriorityQueue.prototype.enqueue = function (element, priority) {
// 创建QueueElement
let queueElement = new QueueElement(element, priority);
// 判断队列是否为空?直接插入:和已有元素对比优先级后插入
if (this.items.length===0) {
this.items.push(queueElement);
} else {
let added=false;
for(let i in this.items){
if(queueElement.priority<this.items[i].priority){
this.items.splice(i,0,queueElement);
added=true;
break;
}
};
if (!added) {
this.items.push(queueElement);
};
}
}
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
let pq = new PriorityQueue();
pq.enqueue('a',1);
pq.enqueue('b',20);
pq.enqueue('taotao',19);
console.log(pq.items);
/* 控制台打印内容
(3) [QueueElement, QueueElement, QueueElement]
0: QueueElement {element: "a", priority: 1}
1: QueueElement {element: "taotao", priority: 19}
2: QueueElement {element: "b", priority: 20}
length: 3
proto: Array(0)
*/
No Reply at the moment.
You need to Sign in before reply, if you don't have an account, please Sign up first.