数据结构--队列的实现和实际运用

队列数据结构

队列是遵循先进先出（FIFO）原则的一组有序的项。队列在尾部添加元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

在实生活中，排队就是队列，在计算机科学中，一个常见的例子就是打印队列。后面添加的打印任务会在后面排队，前面的打印任务完了才会执行后面的打印任务，直到所有任务完成。

创建队列

创建一个自己的类来表示一个队列。

class Queue {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }
}

首先，为了更高效的获取数据，使用对象 items 来存储元素，使用 count 属性来控制队列的大小。由于需要从队列顶部移除元素，还需要一个变量 LowestCount 来追踪顶部元素。

创建一些队列可用的方法：

1.向队列添加元素

实现 enqueue 方法。主要向队列末尾添加新元素。

enqueue(el) {
    this.items[this.count] = el;
    this.count++;
}

因为 items 是一个对象，所以把count 变量作为 items 中的健，对应的元素作为它的值。将元素加入队列后，把 count 值加1。

2.从队列中移除元素

实现 dequeue 方法，从队列顶部移除元素

dequeue(){
    if(this.isEmpty()){
        return undefined;
    }
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
}

首先，检查队列是否为空，如果是空，返回 undefined，如果不为空，把队列顶部元素保存起来，然后把顶部元素删除，最后把 lowestCount 属性值加1，返回保存的顶部元素。

3.查看队列顶部元素

peek(){
    if(this.isEmpty()){
        return undefined;
    }
    return this.items[this.lowestCount];
}

4.检查队列是否为空，获取它的长度

isEmpty() {
    return this.count - this.lowestCount == 0;
}
size() {
    return this.count - this.lowestCount;
}

计算队列中有多少元素，只需计算 count 和 lowestCount 之间的差值即可，如果等于0，就说明队列为空。

5.清空队列

要清空队列的所有元素，可以调用 dequeue 方法直到它返回 undefined，也可以直接将队列的属性重设初始值

clear(){
    this.items = {};
    this.lowestCount = 0;
    this.count = 0;
}

6.创建 toString方法

toString() {
    if (this.isEmpty()) {
        return "";
    }
    let objString = `${this.items[this.lowestCount]}`;
    for(let i = this.lowestCount + 1; i < this.count; i++) {
        objString = `${objString},${this.items[i]}`;
    }
    return objString;
}

items 对象的第一个元素key应该是 lowestCount，所以应该从 lowestCount 的位置开始迭代。

使用 Queue类

const queue = new Queue();
console.log(queue.isEmpty()); //true
//向队列中添加一些元素
queue.enqueue("jiaji");
queue.enqueue("jack");
//执行其它方法
console.log(queue.toString()); //jiaji,jack
console.log(queue.size()); //2
queue.dequeue(); //移除jiaji
console.log(queue.size()); //1
queue.dequeue(); //移除jack
console.log(queue.isEmpty()); //true

循环队列——击鼓传花游戏

队列有很多实际的运用，使用循环队列实现击鼓传花游戏。在这个游戏中，孩子们围成一个圆圈，把花尽快的传递给旁边的人。某一时刻，传花停止，这个时候花在谁手里，谁就退出圆圈，重复这个过程，直到只剩最后一个孩子。

//循环队列，击鼓传花游戏
function hotPotato(elementsList, num) {
    //创建队列实列
    const queue = new Queue();
    //结束游戏的玩家数组
    const elimitatedList = [];
    for (let i = 0; i < elementsList.length; i++) {
        //将所有玩家添加到队列中
        queue.enqueue(elementsList[i]);
    }
    //循环直到队列中只剩一人
    while (queue.size() > 1) {
        //将第num个人移动到队顶
        for (let i = 0; i < num; i++) {
            //每从队顶移除一人就将他添加到队尾
            queue.enqueue(queue.dequeue());
        }
        //移除队顶结束游戏的玩家，添加到结束游戏的玩家数组中
        elimitatedList.push(queue.dequeue());
    }
    return {
        eliminated: elimitatedList,
        winner: queue.dequeue(),
    };
}
​
const names = ["jiaji", "jack", "tom", "mary", "lisa", "tom"];
const result = hotPotato(names, 4);
console.log(result);