javascript数据结构与算法笔记（三）：优先队列

一：简介

优先队列是元素的添加和移除是基于优先级的。一个现实的例子就是机场登机的顺序。头等舱和商务舱乘客的优先级要高于经济舱乘客。在有些国家，老年人和孕妇（或带小孩的妇女）登机时也享有高于其他乘客的优先级。

二：ES6版PriorityQueue类

1.使用WeakMap类声明PriorityQueue类 具体原因可以参照：

let PriorityQueue=(function(){
          
   
    const items=new WeakMap();
    class PriorityQueue{
          
   
        constructor(){
          
   
            items.set(this,[]);
        }
        QueueElement(element,priority){
          
   
            let queueElement={
          
   
                element:element,
                priority:priority
            }
            return queueElement;
        }
    }
    return PriorityQueue;
})();

2.向优先队列添加元素

enqueue(element,priority){
          
   
    let queueElement=this.QueueElement(element,priority);
    let added=false;
    let q=items.get(this);
    for(let i=0;i<q.length;i++){
          
   
        if(queueElement.priority<q[i].priority){
          
   //新元素的等级比源里面的高
            q.splice(i,0,queueElement);//插入元素
            added=true;
            break;
        }
    }
    if(!added){
          
   //如果新元素都比源的优先级低，只需直接push
        q.push(queueElement);
    }
}

3.从优先队列移除元素

dequeue(){
          
   
   let q=items.get(this);
   let r=q.shift();
   return r;
}

4.查看优先队列头元素

front(){
          
   //查看优先队列头元素
    let q=items.get(this);
    return q[0];
}

5.检查优先队列是否为空 isEmpty，如果优先队列为空的话将返回true，否则就返回false：

isEmpty(){
          
   
    let q=items.get(this);
    return q.length==0;
}
size(){
          
   
    let q=items.get(this);
    return q.length;
}

6.打印优先队列元素

print(){
          
   
   let q=items.get(this);
    for(let i=0;i<q.length;i++){
          
   
        console.log(`内容：${
            
     q[i].element}-优先级：${
            
     q[i].priority}`);
    }
}

7.使用优先队列

let priorityQueue = new PriorityQueue();
priorityQueue.enqueue("John", 3);
priorityQueue.enqueue("Jack", 1);
priorityQueue.enqueue("Camila", 2);
priorityQueue.print();