优先级队列(基于数组)
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
class Queue {
constructor() {
this.list = []
}
push(value) {
this.list.push(value)
}
pop() {
return this.list.shift()
}
peek() {
return this.list[0]
}
isEmpty() {
return this.list.length === 0
}
clear() {
this.list = []
}
size() {
return this.list.length
}
toString() {
return this.list.join(",")
}
}
// 优先级队列
class PriorityQueue extends Queue {
push(value, priority = 0) {
let insertIndex = this.list.length;
for (let i = 0; i < this.list.length; i++) {
if (priority <= this.list[i][1]) {
insertIndex = i;
break;
}
}
this.list.splice(insertIndex, 0, [value, priority])
}
pop() {
let item = this.list.shift();
return item ? item[0] : undefined;
}
peek() {
let item = this.list[0];
return item ? item[0] : undefined;
}
toString() {
let resArr = [];
this.list.forEach((item) => {
resArr.push(item[0])
})
return resArr.join(",")
}
}
// 测试代码
const queue = new PriorityQueue();
queue.push("C", 3)
queue.push("B", 2)
queue.push("A", 1)
queue.push("BB", 2)
queue.pop();
queue.push("D", 5)
console.log(queue.toString())
console.log(queue.peek())
console.log(queue.size())
console.log(queue.isEmpty())
queue.clear();
console.log(queue.pop())
console.log(queue.peek())
console.log(queue.toString())
console.log(queue.isEmpty())
JavaScript
INFO