学习js数据结构与算法2—队列

队列遵循先进先出原则——如同排队

4.1 创建队列

    function Queue() {
        // 使用数据结构为数组来存储队列中的元素
        var items = [];
        /*
            队列可用方法
            enqueue(ele): 向队尾添加一个新的项
            dequeue(): 移除队列的第一项，并返回被移除的元素
            front(): 返回队列中的第一项
            isEmpty(): 如果队列不含任何元素返回true,否则false
            size(): 返回队列包含的元素个数
        */
        this.enqueue = function (ele) {
            items.push(ele);
        };
    
        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;
        };
    
        this.print = function () {
            console.log(items.toString());
        }
    }
    
    使用Queue类
    var queue = new Queue();
    console.log(queue.isEmpty());   // true
    
    queue.enqueue('John');
    queue.enqueue('Jack');
    queue.enqueue('Camel');
    
    queue.print();      // ['John', 'Jack', 'Camel']
    console.log(queue.size());      // 3
    console.log(queue.isEmpty());   // false
    
    queue.dequeue();
    queue.dequeue();
    queue.print();      // ['Camel']

4.2 优先队列

    function PriorityQueue() {
        var items = [];

        this.isEmpty = function () {
            return items.length === 0;
        };

        function QueueElement(element, priority) {
            this.element = element;
            this.priority = priority;
        }

        this.enqueue = function (element, priority) {
            var queue = new QueueElement(element, priority);

            if (this.isEmpty()) {
                items.push(queue);
            } else {
                var added = false;
                for (var i = 0; i < items.length; i++) {
                    if (queue.priority < items[i].priority) {
                        items.splice(i, 0, queue);  // 优先级小的会被插入到队列前面
                        added = true;
                        break;
                    }
                }
                if (!added) {
                    items.push(queue);
                }
            }
        }; 

        this.print = function() {
            console.log(items);  
        };
    }

    var queue = new PriorityQueue();
    queue.enqueue('John', 2);
    queue.enqueue('Backham', 1);
    queue.enqueue('Jack', 1);
    queue.print();

4.3 循环队列——击鼓传花

    function hotPotato(list, num) {
        var queue = new Queue();
        
        for (var i = 0; i < list.length; i++) {
            queue.enqueue(list[i]);
        }
        
        var player = '';
        while (queue.size() > 1) {
            for (var i = 0; i < num; i++) {
                queue.enqueue(queue.dequeue());
            }
            player = queue.dequeue();
            console.log(player + '在击鼓传花游戏中被淘汰！')
        }
        
        return player;
    }
    
    var names = ['周杰伦', '陈奕迅', '王力宏', '蔡依林', 'TFBoys', '容祖儿', '韩红', '郑爽'];
    var winner = hotPotato(names, 4);
    console.log('胜利者是' + winner);