The front-end ES6 implements priority queues

0. Priority queue: it means that there is a priority when joining the queue. It is not directly inserted into the queue, but inserted into the appropriate position according to the priority number.

1. Code implementation

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(",")}}// Priority queue
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(",")}}Copy the code

2. Sample code (including test code)

Code link

3. The complexity

• Join the team: The time complexity isO(N), the space complexity isO(1)
• Outbound: The time complexity isO(N), the space complexity isO(1)

4. Thoughts

• Each item in the queue has another array (tuple), the first value of the tuple is the content, the second value is the priority series, with the priority series, when joining the queue, the insertion position is judged first, so as to realize queue jumping
• After cutting in line, the first person in line is still the priority

5. Application scenarios

• For example, when boarding a plane (bank affairs), VIP customers go through the VIP channel

6. Related articles

• Es6 Implements queue data Structures (Array-based)
• Unidirectional Linked Lists (not yet updated)

7. Corrections are welcome