js数据结构--队列(queue)_数据结构与算法_weixin_33716154-开放原子开发者工作坊

队列

队列遵循先进先出的原则的一种有序的项。

enqueue(): 向队列尾部添加一个(或多个)新的项
dequeue(): 移除队列的第一(即排在队列最前面的)项,并返回被移除的元素
front(): 返回队列中第一个元素--最先被添加,也将是最先被移除的元素。队列不做任何变动(不移除元素,只返回元素信息--与Stack类的peek方法非常相似)。
isEmpty(): 如果队列中不包含任何元素,返回true,否则返回false
size(): 返回队列包含的元素个数,与数组的length属性相似

index.html

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
    <script src="./queue.js"></script>
</head>

<body>

</body>

</html>
复制代码

queue.js

var Queue = function() {
    var items = [];
    //入队
    this.enqueue = function(el) {
            items.push(el)
        }
        //出队
    this.dequeue = function() {
            return items.shift();
        }
        // 队头
    this.front = function() {
            return items[0]
        }
        //队是否为空
    this.isEmpty = function() {
            return items.length === 0;
        }
        //队的长度
    this.size = function() {
        return items.length;
    }
}

复制代码

实例化

queue-es6.js

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

    enqueue = function(el) {
            this.items.push(el)
        }
        //出队
    dequeue = function() {
            return this.items.shift();
        }
        // 队头
    front = function() {
            return this.items[0]
        }
        //队是否为空
    isEmpty = function() {
            return this.items.length === 0;
        }
        //队的长度
    size = function() {
        return this.items.length;
    }
}
复制代码

队列实现击鼓传花

玩家列表 ['a', 'b', 'c', 'd', 'e', 'f'];,每第三个出队，最后只留下一个

var Queue = function() {
    var items = [];
    //入队
    this.enqueue = function(el) {
            items.push(el)
        }
        //出队
    this.dequeue = function() {
            return items.shift();
        }
        // 队头
    this.front = function() {
            return items[0]
        }
        //队是否为空
    this.isEmpty = function() {
            return items.length === 0;
        }
        //队的长度
    this.size = function() {
        return items.length;
    }
}

var chuanhua = function(names, number) {
        var q = new Queue();
        for (var i = 0; i < names.length; i++) {
            q.enqueue(names[i])
        }

        var taotal;
        while (q.size() > 1) { //q.size() == 1 时，停止
            for (var i = 0; i < number - 1; i++) { //number=3,只循环2次
                q.enqueue(q.dequeue())  //1.先把a出队，然后入队, 2.把b出队，然后入队
            }
            taotal = q.dequeue(); //c
            console.log('淘汰玩家是:' + taotal)
        }
    }
//玩家列表
var names = ['a', 'b', 'c', 'd', 'e', 'f'];
//游戏规则
var number = 3;

chuanhua(names, number)
复制代码

优先队列

常景: 银行vip办理业务要优先于普通客户

priorityQueue.js

var PriorityQueue = function() {
    var items = [];

    //辅助类
    var QueueItem = function(el, priority) {
        this.el = el;
        this.priority = priority
    }

    this.enqueue = function(el, priority) {
        var queueItem = new QueueItem(el, priority);

        var added = false;
        for (var i = 0; i < items.length; i++) {
            if (queueItem.priority > items[i].priority) {
                items.splice(i, 0, queueItem);
                added = true;
                break;
            }
        }
        if (!added) {
            items.push(queueItem);
        }
    }
    this.getItems = function() {
        return items;
    }
}
复制代码