0. 优先级队列:
- 指入队时有了优先级,入队不是直接插入,而是根据优先数,插入到合适的位置。队列每一项存着内容和优先级数。
1. 代码实现
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(",")
}
}
2. 示例代码(含测试代码)
代码链接
3. 复杂度
- 入队:时间复杂度为
O(N)
、空间复杂度为O(1)
- 出队:时间复杂度为
O(N)
、空间复杂度为O(1)
4. 思想
- 队列每一项存在另一个数组(元组),元组第一个值为内容,第二个值为优先级数,有了优先级数,入队时先判断插入位置,从而实现插队
- 插完队伍后,排在前面还是优先处理
5. 使用场景
- 比如登机(银行办事)排队时,VIP客户走VIP通道
6. 相关文章
7. 欢迎指正