JavaScript数据结构与算法Item3--队列

た入场券 2022-07-16 01:23 168阅读 0赞

队列是遵循FIFO（First In First Out，先进先出，也称为先来先服务）原则的一组有序的项。  
队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。  
在现实中，最常见的队列的例子就是排队：

![qZcNi6R.png][]

## 1 创建队列 ##

需要声明一些队列可用的方法。

 inQueue(element(s))：向队列尾部添加一个（或多个）新的项。

 outQueue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。

 front()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不  
做任何变动（不移除元素，只返回元素信息——与Stack类的peek方法非常类似）。

 isEmpty()：如果队列中不包含任何元素，返回true，否则返回false。

 size()：返回队列包含的元素个数，与数组的length属性类似。

## 2 优先队列 ##

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

另一个现实中的例子是医院的（急诊科）候诊室。医生会优先处理病情比较严重的患者。通  
常，护士会鉴别分类，根据患者病情的严重程度放号。

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

默认的Queue类和PriorityQueue类实现上的区别是，要向PriorityQueue添加元素，需  
要创建一个特殊的元素。这个元素包含了要添加到队列的元素（它可以是任意类型）及其在队列中的优先级。

如果队列为空，可以直接将元素入列。否则，就需要比较该元素与其他元素的优先级。当找到一个比要添加的元素的priority值更大（优先级更低）的项时，就把新元素插入  
到它之前（根据这个逻辑，对于其他优先级相同，但是先添加到队列的元素，我们同样遵循先进  
先出的原则）。要做到这一点，我们可以用array类的splice方法。

一旦找到priority值更大的元素，就插入新元素并终止队列循环。这样，队列也就根据优先级排序了。  
如果要添加元素的priority值大于任何已有的元素，把它添加到队列的末尾就行了.

var priorityQueue = new PriorityQueue();
    priorityQueue.enqueue("John", 2);
    priorityQueue.enqueue("Jack", 1);
    priorityQueue.enqueue("Camila", 1);
    priorityQueue.print();

以上代码是一个使用PriorityQueue类的示例。在下图中可以看到每条命令的结果

![aSoLItt.png][]

## 3 循环队列 ##

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

[qZcNi6R.png]: http://i.imgur.com/qZcNi6R.png
[aSoLItt.png]: http://i.imgur.com/aSoLItt.png