评论

前端es6实现优先级队列

用es6实现优先级队列【数据结构与算法系列】

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. 欢迎指正

最后一次编辑于  2021-09-17  
点赞 1
收藏
评论
登录 后发表内容