极速快3_快3信誉网_极速快3信誉网 - 极速快3,快3信誉网,极速快3信誉网是一个基于本地城市资讯管理的应用,里面汇集了所在城市最热门的民生资讯和便民服务功能,想知道你的家乡发生了什么,打开极速快3,快3信誉网,极速快3信誉网尽在掌握!

JavaScript数据结构——队列的实现与应用

  • 时间:
  • 浏览:0

  队列与栈不同,它遵从先进先出(FIFO——First In First Out)原则,新加上的元素排在队列的尾部,元素只能从队列头部移除。

  大伙儿儿儿在前一篇文章中描述了如可用JavaScript来实现栈其他数据价值形式,这里大伙儿儿儿对应地来实现队列。

function Queue() {
    let items = [];

    // 向队列加上元素(另一个多多或多个)
    this.enqueue = function (element) {
        if (element instanceof Array) items = items.concat(element);
        else items.push(element);
    };

    // 从队列移除元素
    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.clear = function () {
        items = [];
    };

    // 打印队列内的所有元素
    this.print = function () {
        console.log(items.toString());
    };
}

  与栈的实现法子相似,唯一不同的是从队列移除元素时取的是队列头部的元素(最先加上的),而栈则是取的顶部元素(最后加上的)。下面是其他测试用例及返回结果:

let queue = new Queue();
console.log(queue.isEmpty()); // true

queue.enqueue('John');
queue.enqueue(['Jack', 'Camila']);
queue.print(); // John,Jack,Camila
console.log(queue.size()); // 3
console.log(queue.isEmpty()); // false
console.log(queue.front()); // John

console.log(queue.dequeue()); // John
queue.print(); // Jack,Camila

queue.clear();
queue.print(); // 

  注意,大伙儿儿儿允许批量向队列中加上元素,为此大伙儿儿儿前要判断enqueue法子的参数类型,但会 参数是数组,则用concat()函数连接另一个多多数组,但会 参数都不 数组,则直接用push()函数将元素加上到队列中。

  与栈的实现法子一样,这里大伙儿儿儿也同样给出用ES6的WeakMap类来实现的队列版本。

let Queue = (function () {
    const items = new WeakMap();

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

        enqueue (element) {
            let q = items.get(this);
            if (element instanceof Array) items.set(this, q.concat(element));
            else q.push(element);
        };

        dequeue () {
            let q = items.get(this);
            return q.shift();
        };

        front () {
            return items.get(this)[0];
        };

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

        size () {
            return items.get(this).length;
        };

        clear () {
            items.set(this, []);
        };

        print () {
            console.log(items.get(this).toString());
        };
    }

    return Queue;
})();

  这另一个多多版本的执行结果是一样的,它们的区别大伙儿儿儿在前一篇文章中但会 提及过了,这里不再赘述。

优先队列

  所谓优先队列,顾名思义,但会 说插入到队列中的元素还可以 根据优先级设置先后顺序。优先级越高位置越靠前,优先级越低位置越靠后。假设优先级用数字来表示,但会 数字越小表示的优先级越高,形成的队列就称之为最小优先队列,反之则称之为最大优先队列。下面是实现的代码:

function PriorityQueue() {
    let items = [];

    // 向队列加上元素(另一个多多或多个)
    // 参数obj的数据格式:{element, priority}
    this.enqueue = function (obj) {
        if (obj instanceof Array) {
            for (let i = 0, ci; ci = obj[i]; i++) {
                this.enqueue(ci);
            }
        }
        else {
            let added = false;
            for (let i = 0, ci; ci = items[i]; i++) {
                // 最小优先级,即将priority值小的元素插入到队列的前面
                if (obj.priority < ci.priority) {
                    items.splice(i, 0, obj);
                    added = true;
                    break;
                }
            }

            // 但会


元素这么插入到队列中,则默认加到队列的尾部
            if (!added) items.push(obj);
        }
    };

    // 从队列移除元素
    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.clear = function () {
        items = [];
    };

    // 打印队列内的所有元素
    this.print = function () {
        items.forEach(function (item) {
            console.log(`${item.element} - ${item.priority}`);
        });
    };
}

  还可以 看多,唯一有区别的只能enqueue法子。大伙儿儿儿规定所有加上到优先队列的元素都前要满足{element, priority}其他JSON格式,以保证队列中的每另一个多多元素都不 另一个多多priority属性来表示优先级。但会 要加上的元素的优先级和队列中已有元素的优先级相同,仍然遵循队列的先进先出原则。但会 队列中所有元素的优先级比要加上的元素的优先级都高,则将元素加上到队列的末尾。大伙儿儿儿将print()法子也做了其他调整,以方便查看输出结果。

let queue = new PriorityQueue();
console.log(queue.isEmpty()); // true

queue.enqueue({element: 'John', priority: 2});
queue.enqueue([{element: 'Jack', priority: 1}, {element: 'Camila', priority: 1}]);
queue.print(); // Jack,Camila,John

  但会 John的优先级比其它另一个多多低,什么都它被排在了最上方。真是Jack和Camila的优先级相同,但会 Jack是在Camila时候先插入到队列中的,什么都Jack排在了Camila时候,这也符合了大伙儿儿儿的预期。

循环队列

   大伙儿儿儿用另一个多多小游戏“击鼓传花”来说明循环队列在实际中的应用。

function hotPotato(nameList, num) {
    let queue = new Queue();

    for (let i = 0, ci; ci = nameList[i]; i++) {
        queue.enqueue(ci);
    }

    let eliminated = '';
    while(queue.size() > 1) {
        for (let i = 0; i < num; i ++) {
            queue.enqueue(queue.dequeue());
        }
        eliminated = queue.dequeue();
        console.log(`${eliminated} has been eliminated.`);
    }

    return queue.dequeue();
}

let names = ['John', 'Jack', 'Camila', 'Ingrid', "Carl"];
let winner = hotPotato(names, 7);
console.log(`The winner is: ${winner}`);

  在其他游戏中,大伙儿儿儿传入由八个名字组成的数组,用来表示参加游戏的五每所有人 ,数字7表示每一轮要传递的次数。在每另一个多多过程中,大伙儿儿儿从队列头部取出另一个多多元素加到队列的尾部,当次数用完的时候,将队列头部的元素取出来,作为其他轮中被淘汰的人。我不想们来看一下具体的执行过程,一开使队列中的顺序是John, Jack, Camila, Ingrid, Carl,但会 传递7次:

  1. Jack, Camila, Ingrid, Carl, John

  2. Camila, Ingrid, Carl, John, Jack

  3. Ingrid, Carl, John, Jack, Camila

  4. Carl, John, Jack, Camila, Ingrid

  5. John, Jack, Camila, Ingrid, Carl

  6. Jack, Camila, Ingrid, Carl, John

  7. Camila, Ingrid, Carl, John, Jack

  时候从队列中取出的是Camila。反复执行上述过程,直到队列中的元素只剩另一个多多,其他但会 最后的赢家!

  下面是全部的执行结果:

Camila has been eliminated.
Jack has been eliminated.
Carl has been eliminated.
Ingrid has been eliminated.
The winner is: John

   下一章大伙儿儿儿继续来看看如可用JavaScript来实现链表。