JavaScript实现数据结构--队列、优先队列

队列：一种受限的线性表，先进先出。它只允许在表的前端(front)进行删除操作，表的后端(rear)进行插入操作

队列封装

function Queue() {

    this.items = []

    //方法
    //1.将元素加入到队列中
    Queue.prototype.enqueue = function(element) {
        this.items.push(element)
    }

    //2.从队列中删除前端元素
    Queue.prototype.dequeue = function() {
        return this.items.shift()
    }

    //3.查看前端的元素
    Queue.prototype.front = function() {
        return this.items[0]
    }

    //4.查看队列是否为空
    Queue.prototype.isEmpty = function() {
        return this.items.length == 0
    }

    //5.查看队列中元素的个数
    Queue.prototype.size = function() {
        return this.items.length
    }

    //6.toString方法
    Queue.prototype.toString = function() {
        var queueString = ''
        for (let i = 0; i < this.items.length; i++) {
            queueString += this.items[i]
        }

        return queueString
    }

}

队列使用

var queue = new Queue()

queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('e')
queue.enqueue('d')

queue.dequeue()
queue.dequeue()


console.log(queue.front());//e
console.log(queue.toString());//ed

队列的应用题

面试题：击鼓传花

几个人开始数数，数到某个数字的人自动淘汰。最后剩下的人获得胜利，问最后剩下的是在哪一个位置上的人

function passGame(nameList, num) {
    var queue = new Queue()

    for (var i = 0; i < nameList.length; i++) {
        queue.enqueue(nameList[i])
    }

    while (queue.size() > 1) {
        for (let i = 0; i < num - 1; i++) {
            queue.enqueue(queue.dequeue())
        }
        queue.dequeue()

    }

    var endName = queue.front()
    console.log('最后剩下的人：' + endName);

    return nameList.indexOf(endName)
}
var nameList = ['lili', 'cat', 'tweb', 'adas', 'nanna']


console.log(passGame(nameList, 3));
//最后剩下的人：adas
//3

优先队列封装

普通的队列具有先进先出的特性，元素追加在队尾，如果删除的话，从队头删除。而在优先队列中，队列中的数据被赋予了优先级。当访问元素时，优先级最高的会先被删除。所以说优先队列是最高级数据先出。

优先队列支持下面两种操作的数据结构

1.删除最小（最大）元素

2.插入一个元素

function PriorityQueue() {
    //在PriorityPriorityQueue重新创建了一个类，理解为内部类
    function PriorityQueueElement(element, priority) {
        this.element = element
        this.priority = priority
    }

    //封装属性
    this.items = []

    //实现插入方法
    PriorityQueue.prototype.enqueue = function(element, priority) {
        //1.创建QueueElement对象
        var queueElement = new PriorityQueueElement(element, priority)


        //2.判断队列是否为空
        if (this.items.length == 0) {
            this.items.push(queueElement)
        } else {
            var 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)
        }
    }

    //2.从队列中删除前端元素
    PriorityQueue.prototype.dequeue = function() {
        return this.items.shift()
    }

    //3.查看前端的元素
    PriorityQueue.prototype.front = function() {
        return this.items[0]
    }

    //4.查看队列是否为空
    PriorityQueue.prototype.isEmpty = function() {
        return this.items.length == 0
    }

    //5.查看队列中元素的个数
    PriorityQueue.prototype.size = function() {
        return this.items.length
    }

    //6.toString方法
    PriorityQueue.prototype.toString = function() {
        var queueString = ''
        for (let i = 0; i < this.items.length; i++) {
            queueString += this.items[i].element + '-' + this.items[i].priority + ' '
        }

        return queueString
    }

}

优先队列的使用

var pg = new PriorityQueue()
pg.enqueue('小米', 20)
pg.enqueue('华为', 250)
pg.enqueue('苹果', 10)

console.log(pg.toString()); //苹果-10 小米-20 华为-250 

pg.dequeue()
console.log(pg.toString()); //小米-20 华为-250