【JavaScript】JS数据结构与算法之优先队列

谁借莪１个温暖的怀抱￠ 2022-05-13 03:12 334阅读 0赞

说到队列，简单来理解就是排队嘛。排在最前面的肯定最先处理。  
先不说在数据结构与算法中的优先队列，在现实生活中，比如说我们排队取车票的时候，“**不好意思，我的车马上到点了，先让我取一下**”如此情况屡见不鲜。  
这就叫做优先队列。

# 实现思路 #

**方法一**：设置优先级，然后在正确的位置添加元素；  
**方法二**：用入列操作添加元素，然后按照优先级处理。

# Talk is Cheap , Show Me the Code #

/* *Author : ljccccccccccc@163.com */
    function priorityQueue() { 
        let items = [];
        function QueueElement(element, priority) { 
            this.element = element;
            this.priority = priority;
        }
    
        this.enqueue = function (element, priority) { 
            let queueElement = new QueueElement(element, priority);
    
            let added = false;
            for (let i = 0; i < items.length; i++) {
                if (queueElement.priority < items[i].priority) {
                    items.splice(i, 0, queueElement);
                    added = true;
                    break;
                }
            }
            if (!added) {
                items.push(queueElement);
            }
        }
        this.print = function () { 
            for(let i = 0; i < items.length; i ++){
            //两种方法输出都可以
                // console.log(`${items[i].element} - ${items[i].priority}`);
                console.log(items[i].element +" - "+items[i].priority);
            }
        }
        //其他实现与队列相同
            //删除
            this.dequeue = function (el) { 
                return items.shift();
            }
            //查看队列头元素
            this.front = function () { 
                return items[0];
            }
            //检查是否为空
            this.isEmpty = function () { 
                return items.length === 0;
            }
    
    }
    
    let pri = new priorityQueue();
    
    pri.enqueue('Hilleny',1);
    pri.enqueue('Funny',3);
    pri.enqueue('Hilleny',1);
    pri.enqueue('Hilleny',1);
    pri.enqueue('Hilleny',1);
    pri.enqueue('Jhon',2);
    pri.enqueue('Hilleny',1);
    pri.print();

第一个添加的Hilleny优先级为1，是队列中第一个元素，后面的Funny优先级为3，是第二个元素。当添加到第三个元素时，它的优先级为1，所以插入到优先级为3的前面。后同。当遇到优先级为2的Jhon时，splice（i ,0，Jhon），把Jhon插入到优先级为3的前面。  
这就是优先队列。  
看一下输出结果，再回味一下代码吧！

//结果输出
    Hilleny  -  1
    Hilleny  -  1
    Hilleny  -  1
    Hilleny  -  1
    Hilleny  -  1
    Jhon  -  2
    Funny  -  3

这就是优先队列的实现。其中涉及到队列的知识，请前往  
[【JavaScript】JS数据结构与算法之队列][JavaScript_JS]

挚谢阅读。  
wx：jc\_960823 注明来意  
163 : ljccccccccccc@163.com

[JavaScript_JS]: https://blog.csdn.net/liu_jiachen/article/details/82469977