js数据结构（队列Queue）

队列数据结构

什么是队列？

队列是遵从FIFO（First IN First Out，先进先出，也称为先来服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

在现实中，最常见的例子就是排队。在电影院、自助餐厅、杂货店收银台，我们也都会排队。排在第一位的人会先接受服务。
在计算机科学中，一个常见的例子就是打印队列。比如说我们需要打印五份文档。我们会打
开每个文档，然后点击打印按钮。每个文档都会被发送至打印队列。第一个发送到打印队列的文
档会首先被打印，以此类推，直到打印完所有文档。

队列 Queue类和栈Stack类非常类似。唯一的区别是dequeue方法和front方法， 这是由于先进先出和后进先出原则的不同所造成的。

创建队列

我们需要创建一个自己的类来表示一个队列。先从最基本的声明类开始。

1. enque(elemet(s)),向队列尾添加一个（或多个）新的项。
2. dequeue(): 移除队列的第一个（即排在队列最前面的）项，并返回被移除的元素。
3. front(): 返回队列中第一个元素-- 最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息，与栈的peek方法类似）；
4. isEmpty():如果队列中不包含任何元素，返回true，否则返回false.
5. size():返回队列包含的元素个数，与数组的length属性相似
6. print():打印队列元素。

function Queue() {
    let items = [];
    this.enqueue = function (element) {
        items.push(element);
    }
    this.dequeue = function () {
        return items.shift();
    }
    this.isEmpty = function () {
        return items.length == 0;
    }
    this.size = function () {
        return items.length;
    }
    this.print = function(){
        console.log(items.toString());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

向队列添加元素

向队列添加元素，首先要实现的是enqueue方法。这个方法负责向队列添加新元素，这里有一个非常重要的细节，新的项目只能添加到队列末尾：使用数组来存储队列的元素，可以使用js中的push方法。

this.enqueue =function(element){
    items.push(element);
}

1
2
3
4

移除队列中的元素

接下来要实现dequeue方法。
这个方法负责从队列移除项。由于队列遵循新进先出原则，最先添加的项也是最先被移除的。可以用JavaScript的数组方法shift方法。
只有enqueue方法和dequeue方法可以添加和移除元素，这样就确保了Queue类遵循先进先出原则。

this.dequeue = function () {
    return items.shift();
}
1
2
3

查看队列头元素

现在来为我们的类实现一些额外的辅助方法。如果想知道队列最前面的项是什么可以用 front 方法，这个方法会返回队列最前面的项。

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

1
2
3
4

检查队列是否为空

isEmpty方法，如果队列为空，它会返回true，否则返回false(跟Stack类里的一样)；
对于isEmpty方法，可以简单地验证 内部数组的length 是否为0

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

我们也可以为Queue类 实现类似于数组的length方法size方法跟Stack类里的一样。

this.size = function () {
    return items.length;
}
1
2
3

打印队列元素

我们的queue类实现好了，也可以像Stack类一样增加一个print 方法。

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

1
2
3
4

使用列表

使用Queue类
首先要做的是 实例化我们刚刚创建的Queue类，然后就可以验证它为空（输出为true，因为我们还没有向队列添加任何元素）

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

 接下来添加一些元素（添加John和jack两个元素）
 queue.enqueue("John");
 queue.enqueue("Jack");
// queue.enqueue("Camila");

// 然后执行一些其他的命令
// queue.dequeue();
// queue.dequeue();
 queue.print();
// 如果打印队列的内容，就会得到John、Jack、Camila 这三个元素。 因为我们向队列添加了三个元素，所以队列的大小为3。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

es6的声明队列类

let Queue2 = (function () {
    const items = new WeakMap();
    class Queue2 {
        constructor() {
            items.set(this, [])
        }
        enqueue(element) {
            let q = items.get(this);
            q.push(element);
        }
        dequeue() {
            let q = items.get(this);
            let r = q.shift();
            return r;
        }
    }
    return Queue2
})()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

优先队列

// 优先队列 ：
// 元素的添加和移除是基于优先级的。一个现实的例子就是机场登机的顺序。头等舱和商务舱乘客的优先级要高于经济舱乘客。在有些国家，老年人和孕妇（或 带小孩的妇女）登机时也享有高于其他乘客的优先级。

// 实现一个优先队列，有两种选项：设置优先级，然后在正确的位置添加元素；或者用入列操
// 作添加元素，然后按照优先级移除它们。在这个示例中，我们将会在正确的位置添加元素，因此
// 可以对它们使用默认的出列操作：

function PriorityQueue() {
    let items = [];
    //传入"John", 2
    function QueueElement(element, priority) {
        //这个函数有两个参数
        this.element = element;
        this.priority = priority;
    }
    // "John", 2
    this.enqueue = function (element, priority) {
        //实例化 QueueElement 函数 并且 把 element "John" 跟priority 2传递进去
        let queueElement = new QueueElement(element, priority);
        // 声明一个添加变量
        let added = false;
        console.log(items.length);
        // 因为这个最开始 没有itmes.length 没有值 直接走下面 if (!added)
        // 开始循环 itmes 
        for (let i = 0; i < items.length; i++) {
            if (queueElement.priority < items[i].priority) {
                items.splice(1, 0, queueElement);
                added = true;
                break;
            }
        }
        if (!added) {
            // 直接push进队列。
            items.push(queueElement)
            console.log(queueElement);
        }
    }
    this.print = function () {
        for (let i = 0; i < items.length; i++) {
            console.log(`${items[i].element}-${items[i].priority}`);
        }
    }
}
let priorityQueue = new PriorityQueue();
priorityQueue.enqueue("John", 2);
priorityQueue.enqueue("Jack", 1);
priorityQueue.enqueue("Camila", 1);
priorityQueue.print();

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

击鼓传花

循环队列击鼓传花
// 。在这个游戏中，孩子们围成一个圆圈，把花尽快地传递给旁边的人。某一时刻传花停止，
// 这个时候花在谁手里，谁就退出圆圈结束游戏。重复这个过程，直到只剩一个孩子（胜者）。
// 我们来实现一个模拟击鼓传花的游戏

function hotPotato(nameList, num) {
    let queue = new Queue();
    // namelist =['John', 'Jack', 'Camila', 'Ingrid', 'Carl']
    for (let i = 0; i < nameList.length; i++) {
        // 把这5个元素添加到队列中
        queue.enqueue(nameList[i]);
    }
    let eliminated = "";
    // 如果队列中还剩下1个停止循环
    while (queue.size() > 1) {
        // num = 7 循环7次
        for (let i = 0; i < num; i++) {
            // 把开头的删除重新加入到队列尾部
            queue.enqueue(queue.dequeue());
        }
        eliminated = queue.dequeue();
        console.log(eliminated + "在击鼓传花游戏中被淘汰");
    }
    return queue.dequeue();
}
let names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
let winner = hotPotato(names, 7);
console.log('The winner is: ' + winner);/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23