队列

[funnycoderstar]

队列是遵循FIFO( First In First Out, 先进先出)原则的一组有序的项

js实现队列

class Queue {
    constructor() {
        this.items = []; 
    }
    enqueue(element) {
       this.items.push(element)
    }
    // 从队列移除元素
    dequeue() {
       return this.items.shift();
    }
    // 查看队头元素
    front() {
        return this.items[0];
    }
    isEmpty() {
        return this.items.length == 0;
    }
    size() {
        return this.items.length;
    }
    clear() {
        this.items = [];
    }
    print() {
        console.log(this.items.toString());
    }

}

优先队列

元素的添加和删除是基于优先级的.例如机场登机的顺序, 头等舱和商务舱乘客的优先级要高于经济舱.

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

let priorityQueue = new PriorityQueue();
priorityQueue.enqueue('Join', 2);
priorityQueue.enqueue('Jack', 1);
priorityQueue.enqueue('Camila', 1);
priorityQueue.print();

以上代码实现的是最小优先队列.因为优先级较小的值放在队列的最前面, 最大优先队列跟这个是相反的

循环队列-击鼓传花

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', 'Jack', 'Camia', 'Ingrid', 'Carl'];
let winner = hotPotato(names, 7);
console.log('The winner is:' + winner);