JavaScript 数据结构与算法(五)优先队列

场景

生活中类似优先队列的场景:

  • 优先排队的人,优先处理。 (买票、结账、WC)。
  • 排队中,有紧急情况(特殊情况)的人可优先处理。

优先队列

优先级队列主要考虑的问题:

  • 每个元素不再只是一个数据,还包含优先级。
  • 在添加元素过程中,根据优先级放入到正确位置。

优先队列的实现

代码实现

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// 优先队列内部的元素类
class QueueElement {
constructor(element, priority) {
this.element = element;
this.priority = priority;
}
}

// 优先队列类(继承 Queue 类)
export class PriorityQueue extends Queue {
constructor() {
super();
}

// enqueue(element, priority) 入队,将元素按优先级加入到队列中
// 重写 enqueue()
enqueue(element, priority) {
// 根据传入的元素,创建 QueueElement 对象
const queueElement = new QueueElement(element, priority);

// 判断队列是否为空
if (this.isEmpty()) {
// 如果为空,不用判断优先级,直接添加
this.items.push(queueElement);
} else {
// 定义一个变量记录是否成功添加了新元素
let added = false;

for (let i = 0; i < this.items.length; i++) {
// 让新插入的元素进行优先级比较,priority 值越小,优先级越大
if (queueElement.priority < this.items[i].priority) {
// 在指定的位置插入元素
this.items.splice(i, 0, queueElement);
added = true;
break;
}
}

// 如果遍历完所有元素,优先级都大于新插入的元素,就将新插入的元素插入到最后
if (!added) {
this.items.push(queueElement);
}
}
}

// dequeue() 出队,从队列中删除前端元素,返回删除的元素
// 继承 Queue 类的 dequeue()
dequeue() {
return super.dequeue();
}

// front() 查看队列的前端元素
// 继承 Queue 类的 front()
front() {
return super.front();
}

// isEmpty() 查看队列是否为空
// 继承 Queue 类的 isEmpty()
isEmpty() {
return super.isEmpty();
}

// size() 查看队列中元素的个数
// 继承 Queue 类的 size()
size() {
return super.size();
}

// toString() 将队列中元素以字符串形式返回
// 重写 toString()
toString() {
let result = "";
for (let item of this.items) {
result += item.element + "-" + item.priority + " ";
}
return result;
}
}

测试代码

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
31
32
33
const priorityQueue = new PriorityQueue();

// 入队 enqueue() 测试
priorityQueue.enqueue("A", 10);
priorityQueue.enqueue("B", 15);
priorityQueue.enqueue("C", 11);
priorityQueue.enqueue("D", 20);
priorityQueue.enqueue("E", 18);
console.log(priorityQueue.items);
//--> output:
// QueueElement {element: "A", priority: 10}
// QueueElement {element: "C", priority: 11}
// QueueElement {element: "B", priority: 15}
// QueueElement {element: "E", priority: 18}
// QueueElement {element: "D", priority: 20}

// 出队 dequeue() 测试
priorityQueue.dequeue();
priorityQueue.dequeue();
console.log(priorityQueue.items);
//--> output:
// QueueElement {element: "B", priority: 15}
// QueueElement {element: "E", priority: 18}
// QueueElement {element: "D", priority: 20}

// isEmpty() 测试
console.log(priorityQueue.isEmpty()); //--> false

// size() 测试
console.log(priorityQueue.size()); //--> 3

// toString() 测试
console.log(priorityQueue.toString()); //--> B-15 E-18 D-20

数组、栈和队列图解

数组、栈和队列图解