javascript数据结构-队列

本博客参考于洛伊安妮·格罗纳编著的javascript数据结构与算法第三版及codeWay老师视频或其他博客资料，在此对此表示感谢!
github仓库：https://github.com/hzx17/

基本队列

认识队列

队列（Queue）是一种运算受限的线性表，特点：先进先出。(FIFO：First In First Out)

受限之处：

• 只允许在表的前端（front）进行删除操作。
• 只允许在表的后端（rear）进行插入操作。

生活中类似队列结构的场景：

• 排队，比如在电影院，商场，甚至是厕所排队。
• 优先排队的人，优先处理。 (买票、结账、WC)。

基本队列的封装

function Queue(){
      //属性
      this.items=[];
      /* 方法 */
      //将元素放入队列中
      Queue.prototype.enqueue=function(element){
          this.items.push(element)
      }
      //从队列中删除前端元素
      Queue.prototype.dequeue=function(){
       return this.items.shift();
    }
      //从队列中查看前端元素
      Queue.prototype.showqueue=function(){
          return this.items[0]
    }
     //从队列中删除任何位置元素
     Queue.prototype.spliceelement=function(index,count){
       return this.items.splice(index,count)
     }
      //查看队列中元素个数是否为空
      Queue.prototype.isEmpty=function(){
        return this.items.length==0
    }
      //查看队列中的元素个数
      Queue.prototype.elementnum=function(){
      return this.items.length;
      }
      //toString
      Queue.prototype.toString=function(){
        let resultString="";
        for(var i=0;i<this.items.length;i++){
             resultString +=this.items[i]+""
        }
        return resultString
    }
}

优先级队列

优先级队列使用场景

生活中类似优先队列的场景：

• 优先排队的人，优先处理。 (买票、结账、WC)。
• 排队中，有紧急情况（特殊情况）的人可优先处理。

优先级队列主要考虑的问题：

• 每个元素不再只是一个数据，还包含优先级。
• 在添加元素过程中，根据优先级放入到正确位置。

优先级队列的封装

/* 封装优先级队列 */
function PriorityQueue(){
    //保存元素和优先级
    function QueueElement(element,priority){
        this.element=element;
        this.priority=priority;
    }
    //封装属性
    this.items=[];
    //封装方法
    //实现插入方法
    PriorityQueue.prototype.enqueue=function(element,priority){
        // 1、创建QueueElement对象
        const queueElement=new QueueElement(element,priority);
        //2、判断队列是否为空
        if(this.items.length==0){
           //直接将实例化的元素与优先级对象push进来
            this.items.push(queueElement)

        }else{
            //3、for循环遍历比较队列中已有元素的优先级 
            var added=false; 
            for(let i=0;i<this.items.length;i++){
                if(this.items[i].priority>queueElement.priority){
                    this.items.splice(i,0,queueElement);
                    added=true;
                    break;  
                }
            }
            if(!added){
                this.items.push(queueElement)
            }
        }
    }
      //toString
    PriorityQueue.prototype.toString=function(){
        let resultString="";
        for(var i=0;i<this.items.length;i++){
             resultString +=this.items[i]+""
        }
        return resultString
    }

}
//实例化类
var priorityQueue=new PriorityQueue();

//向其添加元素
priorityQueue.enqueue("何治兴",153);
priorityQueue.enqueue("李玉成",323);
priorityQueue.enqueue("李阳",223);
priorityQueue.enqueue("zhangsan",310);

console.log(priorityQueue)