JavaScript数据结构-队列

队列遵循FIFO先进先出原则。
用数组储存队列中的数据结构
队列类

function Queue() {
    let items = [];

    //向队列尾部添加一个或者多个的项
    this.enqueue = function (element) {
        items.push(element);
    };

    //移除队列第一项并返回
    //shift() 方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。
    this.dequeue = function () {
        return items.shift();
    };

    //返回队列的第一个元素，队列不做变动
    this.front = function () {
        return items[0];
    };

    //判断队列是否为空
    this.isEmpty = function () {
        return items.length === 0;
    };

    //返回队列包含的元素个数
    this.size = function () {
        return items.length;
    };

    //打印队列
    this.print = function () {
        console.log(items.toString());
    };
}

使用ES6进行实现
使用WeakMap保存私有属性，外层函数（闭包）来封装Queue类

let Queue = (function () {
    const items = new WeakMap();
    class Queue{
        constructor () {
            items.set(this, []);
        }
        //向队列尾部添加一个或者多个的项
        enqueue(element){
            let q = items.get(this);
            q.push(element);
        }
        //移除队列第一项并返回
        dequeue(){
            let q = items.get(this);
            let r = q.shift();
            return r;
        }
        //返回队列的第一个元素，队列不做变动
        front(){
            let q = items.get(this);
            return q[0];
        }
        //判断队列是否为空
        isEmpty(){
            let q = items.get(this);
            return q.length === 0;
        };
        //返回队列包含的元素个数
        size(){
            let q = items.get(this);
            return q.length;
        };
        //打印队列
        print(){
            let q = items.get(this);
            console.log(q.toString());
        };
    }
    return Queue;
})();

优先队列

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);
       }
   };

       //移除队列第一项并返回
   //shift() 方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。
   this.dequeue = function () {
       return items.shift();
   };

   //返回队列的第一个元素，队列不做变动
   this.front = function () {
       return items[0];
   };

   //判断队列是否为空
   this.isEmpty = function () {
       return items.length === 0;
   };

   //返回队列包含的元素个数
   this.size = function () {
       return items.length;
   };

   this.print = function () {
       for(let i = 0; i < items.length; i++){
           console.log(`${items[i].element}-${items[i].priority}`);
       }
   }
}

循环队列-击鼓传花

//循环队列-击鼓传花
function hotPotato(nameList, num) {
    let queue = new Queue();
    for(let i = 0;i < nameList.length; i++){
        queue.enqueue(nameList[i]);
    }

    let eliminated = '';
    while (queue.size() > 1){
        for(let i = 0; i <num; i++){
            queue.enqueue(queue.dequeue());
        }
        eliminated = queue.dequeue();
        console.log(eliminated + '在击鼓传花中被淘汰');
    }
    return queue.dequeue();
}

let names = ['john','tom','bob','barl','vc','dd'];
let winner = hotPotato(names, 7);
console.log('the winner is ' + winner);

有兴趣可以加入Nodejs交流群，和大佬们一起成长！！！

群号：348108867

图片.png