JS实现循环队列 - 击鼓传花

队列是遵循先进先出服务的一组有序的项，队列在尾部添加新元素，并从顶部移除元素，最新添加的元素必须排在队列的末尾。
让我们用JS实现一个队列:

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

队列大量应用在计算机科学以及我们的生活中，如我们需要排队进入电影院，在医院需要排号。但有时候也需要设置优先级，比如医院的急诊科，医生会优先处理病情比较严重的患者，我们来实现个优先队列，根据元素的优先级添加。

function PriorityQueue() {
    let items = []
    function QueueElement(element, priority) {
        this.element = element
        this.priority = priority
    }
    this.isEmpty = function () {
        return items.length == 0
    }
    this.print = function () {
        let str = ''
        for (let i = 0; i < items.length; i++) {
           str += items[i].element + ' '
        }
        console.log(str)
    }
    this.enqueue = function (element, priority) {
        let queueElement = new QueueElement(element, priority)
        if (this.isEmpty()) {
            items.push(queueElement)
        } else {
            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)
            }
        }
    }
}
let priorityQueue = new PriorityQueue()
priorityQueue.enqueue('yiyou', 10)
priorityQueue.enqueue('world', 2)
priorityQueue.enqueue('hello', 1)
console.log(priorityQueue.print()) // hello world yiyou

还有一个修改版的队列实现，是循环队列。循环队列的一个例子就是击鼓传花游戏。在这个游戏中，孩子们围成一个圆圈，把花尽快地传递给旁边的人，某一时刻传花停止，这个时候花在谁手里，谁就退出圆圈结束游戏，重复这个过程，直到只剩一个孩子。

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 = ['snow', 'john', 'alia', 'sansa', 'blue']
let winner = hotPotato(names, 7)
console.log('胜利者' + winner)
// alia在击鼓传花游戏中被淘汰
// john在击鼓传花游戏中被淘汰
// blue在击鼓传花游戏中被淘汰
// sansa在击鼓传花游戏中被淘汰
// 胜利者snow

最后编辑于：2019.05.14 11:02:06