JS数据结构及算法(二) 队列

队列是遵循先进先出的一种数据结构,在尾部添加新元素,并从顶部移除元素。

1.普通队列

function Queue() {
    this.items = [];
}

Queue.prototype = {
    enqueue: function (element) {
        this.items.push(element);
    },
    dequeue: function () {
        return this.items.shift();
    },
    front: function () {
        return items[0];
    },
    isEmpty: function () {
        return this.items.length === 0;
    },
    clear: function () {
        this.items = [];
    },
    size: function () {
        return this.items.length;
    },
    print: function () {
        console.log(this.items.toString());
    }
};

2.优先队列:元素的添加基于优先级

//继承Queue
function PriorityQueue() {
    Queue.call(this);
}
PriorityQueue.prototype = Object.create(Queue.prototype);
PriorityQueue.prototype.constructor = PriorityQueue;
PriorityQueue.prototype.enqueue = function (element,priority) {
    function QueueElement (element, priority){
        this.element = element;
        this.priority = priority;
    }
    let queueElement = new QueueElement(element, priority);

    let added = false;
    for (let i=0; i<this.items.length; i++){
        if (queueElement.priority < this.items[i].priority){ 
            this.items.splice(i,0,queueElement);             
            added = true;
            break; 
        }
    }
    if (!added){
        this.items.push(queueElement);
    }
};
PriorityQueue.prototype.print=function () {
    for(let i=0;i<this.items.length;i++){
        console.log(`${this.items[i].element}  - ${this.items[i].priority}`);
    }
};

 3.循环队列(击鼓传花模拟)

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 + ' was eliminated from the Hot Potato game.');
    }

    return queue.dequeue(); //最后剩下的人是胜者
}

let names = ['John','Jack','Camila','Ingrid','Carl'];
let winner = hotPotato(names, 7);
console.log('The winner is: ' + winner);

参考:《学习JavaScript数据结构与算法(第二版)》

原文地址:https://www.cnblogs.com/jingmi-coding/p/9284824.html