4-队列

4-队列

受限的线性结构：
我们已经学习一种受限的线性结构：栈结构。
并且已经知道这种受限的数据结构对于解决某些特定问题，会有特别的效果。
下面，我们再来学习另外一个受限的数据结构：队列。

队列（Queue），它是一种受限的线性表，先进先出（FIFO First In First Out）
受限之处在于它只允许在表的前端（fromt）进行删除操作。
而在表的后端（rear）进行插入操作。

队列示意图：

4 队列 - 图1

队列的应用

打印队列：
- 有五份文档需要打印，这些文档会按照次序放入到打印队列中。
- 打印机会依次从队列中取出文档，优先放入的文档，优先被取出，并且对该文档进行打印。
- 以此类推，直到队列中不再有新的文档。
线程队列：
- 在开发中，为了让任务可以并行处理，通常会开启多个线程。
- 但是，我们不能让大量的线程同时运行处理任务。（占用过多的资源）
- 这个时候，如果有需要开启线程处理任务的情况，我们就会使用线程队列。
- 线程队列会依照次序来启动线程，并且处理对应的任务。

队列类的创建

队列实现和栈一样，有两种：
- 基于数组实现
- 基于链表实现

队列常见操作

enqueque(element):向队列尾部添加一个（或多个）新的项。
dequeue():移除队列第一（即排在队列最前面的）项，并返回被移除的元素。
front():返回队列第一个元素—-最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息—-与Stack类的peek方法非常类似）。
isEmpty()：如果队列不包含任何元素，返回true，否则返回false。
size():返回队包含的元素个数，与数组的length属性类似。
toString():将队列中的内容，转换成字符串形式

代码示例：
class QueueClass {
constructor() {
this.items = [];
}
// 方法
//向队列尾部添加一个（或多个）新的项。
enqueue(element) {
this.items.push(element)
}
//移除队列第一（即排在队列最前面的）项，并返回被移除的元素。
dequeue() {
return this.items.shift();
}
//返回队列第一个元素—-最先被添加，也将是最先被移除的元素。队列不做任何变动。
front() {
if (this.isEmpty()) {
console.error(“items is Emoty”)
return
}
return this.items[0];
}
//如果队列不包含任何元素，返回true，否则返回false。
isEmpty() {
return this.items.length == 0;
}
//返回队包含的元素个数，与数组的length属性类似。
size() {
return this.items.length;
}
//将队列中的内容，转换成字符串形式
toString() {
return this.items.join(“ “);
}
}

案例-击鼓传花：
function passGame(elementArray, num) {
let flowerArray = new QueueClass();

        for (let i = 0; i < elementArray.length; i++) {<br />                flowerArray.enqueue(elementArray[i]);<br />            }
        while (flowerArray.size() > 1) {<br />                for (let i = 0; i < num - 1; i++) {<br />                    // console.log(i);<br />                    flowerArray.enqueue(flowerArray.dequeue());<br />                }<br />                console.log(flowerArray.dequeue())<br />            }
        console.log("长度是：", flowerArray.size())<br />            console.log("最后留下的是：", flowerArray.items)<br />        }
    let elementArray = [1, 2, 3, 4, 5, 6];<br />        passGame(elementArray, 5);

优先级队列
优先级队列特点：

我们知道，普通的队列插入一个元素，数据会被放在后端，并且需要前面所有的元素都处理完成后才会处理前面的数据。
但是优先级队列，在插入一个元素的时候会考虑该数据的优先级。
和其他数据优先级进行比较。
比较完成后，可以得出这个元素在队列中正确位置。
其他处理方式，和基本队列的处理方式一样。

优先级队列主要考虑的问题：

每个元素不再只是一个数据，而且包含数据的优先级。
在添加方式中，根据优先级放入正确的位置。

优先级队列的应用：
计算机中，我们也可以通过优先级队列来重新排序队列中的任务顺序。
比如每个线程处理的任务重要性不同，我们可以通过优先级的大小，来决定该线程在队列中被处理的次序。

优先级队列的实现
实现优先级对立相对队列主要有两方面需要考虑：

封装元素和优先级放在一起（可以封装一个新的构造函数）
添加元素时，将新插入元素的优先级和队列中已经存在的元素优先级进行比较，以获得自己正确的位置。

数字小者优先进入：
// 封装优先级队列
function PriorityQueue() {
// 在PriorityQueue 重写创建一个类：可以理解成内部类
function QueueElement(element, priority) {
this.element = element;
this.priority = priority;
}
// 封装属性
this.items = []
// 实现插入方法
PriorityQueue.prototype.enqueue = function (element, priority) {
// 1.创建QueueElement 对象
let queueElement = new QueueElement(element, priority);

            // 2.判断队列是否为空<br />                if (this.items.length == 0) {<br />                    this.items.push(queueElement)<br />                } else {<br />                    var added = false;<br />                    for (let i = 0; i < this.items.length; i++) {<br />                        if (queueElement.priority < this.items[i].priority) {<br />                            this.items.splice(i, 0, queueElement);<br />                            added = true;<br />                            break;<br />                        }<br />                    }<br />                    if (!added) {<br />                        this.items.push(queueElement)<br />                    }<br />                }<br />            }<br />        }

数字小者优先进入：
class PriorityQueueClass {
constructor() {
this.items = [];
this.QueueElementClass = class QueueElementClass {
constructor(element, priority) {
this.element = element;
this.priority = priority;
}
}
}

        enqueue(element, priority) {<br />                let queueElement = new this.QueueElementClass(element, priority);<br />                if (this.items.length == 0) {<br />                    this.items.push(queueElement);<br />                } else {<br />                    var flag = false;<br />                    for (let i = 0; i < this.items.length; i++) {<br />                        if (queueElement.priority > this.items[i].priority) {<br />                            this.items.splice(i, 0, queueElement);<br />                            flag = true;<br />                            break;<br />                        }<br />                    }<br />                    if (!flag) {<br />                        this.items.push(queueElement);<br />                    }<br />                }<br />            }<br />        }

bugBase/queryByCcAndBugname