队列的应用

什么是队列？

        队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表

进队和出队图示

进队和出队

队列的基本操作

enqueue(element)：向队列尾部添加一个或多个元素
dequeue()：移除队列的第一项，并返回该元素
front()：返回队列中第一个元素(不移除)
isEmpty()：查看队列是否为空，返回为布尔值
size()：返回队列包含胡元素个数
toString()：将队列中的内容转化成字符串

队列的封装

        //封装队列
        function Queue() {
            //属性
            this.items = []


            //添加元素到队尾
            Queue.prototype.enqueue = function (ele) {
                this.items.push(ele)
            }

            //移除对头元素，删除
            Queue.prototype.dequeue = function () {
                return this.items.shift()
            }


            //返回队列中的第一个元素,不删除
            Queue.prototype.front = function () {
                return this.items[0]
            }


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


            //返回队列长度
            Queue.prototype.size = function () {
                return this.items.length
            }


            //toString方法
            Queue.prototype.toString = function () {
                var res = ''
                for (var i in this.items) {
                    res += this.items[i] + ' '
                }
                return res
            }
        }

例题：击鼓传花

总共n个人围城一圈，编号从1开始。从第一个人开始传递一朵花，当传到第m次时，持花者出局，下一个人重新计数传递，重复直到剩下最后一人，求出他原来的下标和值

代码实现

        function passGame(List, num) {
            //创建一个队列
            var queue = new Queue()
            //所有人加入队列
            for (var i in List) {
                queue.enqueue(List[i])
            }
            while (queue.size() > 1) {
                //开始数数字，达到某值(num)，删除元素，否则放到队列末尾
                for (var i = 0; i < num - 1; i++) {
                    queue.enqueue(queue.dequeue())
                }
                queue.dequeue()
            }
            console.log(`原始队列为${List},num为${num}`)
            console.log(`队列最后剩下的人是:${queue.front()},原始下标为${List.indexOf(queue.front())}`)
        }

        passGame([1, 2, 3, 4, 5], 2)

击鼓传花

优先级队列

定义

如果我们给每个元素都分配一个数字来标记其优先级，不妨设较小的数字具有较高的优先级，这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样，我们就引入了优先级队列(priority queue)这种数据结构。对于优先权相同的元素，可按先进先出次序处理或按任意优先权进行。

优先级队列的封装

        //封装优先级队列
        function PriorityQueue() {
            /* priority:元素的优先级,priority越小,排在队列越前 */
            function QueueuElement(element, priority) {
                this.element = element
                this.priority = priority
            }
            this.items = []

            //插入方法
            PriorityQueue.prototype.enqueue = function (element, priority) {
                //创建QueueElement对象
                var queueuElement = new QueueuElement(element, priority)
                //判断队列是否为空
                if (this.items.length == 0) {
                    this.items.push(queueuElement)
                } else {
                    //判断元素是否已加入队列
                    var added = false
                    for (var i in this.items) {
                        if (queueuElement.priority < this.items[i].priority) {
                            this.items.splice(i, 0, queueuElement)
                            added = true
                            break
                        }
                    }
                    //元素没有加入队列
                    if (!added) {
                        this.items.push(queueuElement)
                    }
                }
            }


            //移除对头元素，删除
            PriorityQueue.prototype.dequeue = function () {
                return this.items.shift()
            }


            //返回队列中的第一个元素,不删除
            PriorityQueue.prototype.front = function () {
                return this.items[0]
            }


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


            //返回队列长度
            PriorityQueue.prototype.size = function () {
                return this.items.length
            }


            //toString方法
            PriorityQueue.prototype.toString = function () {
                var res = ''
                for (var i in this.items) {
                    res += this.items[i].element + '---' + this.items[i].priority + '\n'
                }
                return res
            }
        }


        var p = new PriorityQueue()
        p.enqueue(3, 333)
        p.enqueue(5, 33333)
        p.enqueue(2, 33)
        p.enqueue(1, 3)
        p.enqueue(4, 3333)
        alert(p)

优先级队列
END