队列和双端队列

队列数据结构

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

创建队列

通过双指针标明队列的头尾

class Queue {
    constructor() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};
    }
    enqueue(element) {
        this.items[this.count] = element;
        this.count++;
    }
    dequeue() {
        if (this.isEmpty()) {
            return undefined;
        }
        const result = this.items[this.lowestCount];
        delete this.items[this.lowestCount];
        this.lowestCount++;
        return result; 
    }
    peek() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.lowestCount];
    }
    isEmpty() {
        return this.count - this.lowestCount === 0;
    }
    size() {
        return this.count - this.lowestCount;
    }
    clear() {
        this.items = {};
        this.count = 0;
        this.lowestCount = 0;
    }
    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;
    }
}

双端队列数据结构

双端队列（deque，或称double-ended queue）是一种允许我们同时从前端和后端添加和移除元素的特殊队列。

双端队列的一个常见应用是存储一系列的撤销操作

在头部插入的时候为了保证头部索引为0，类似数组的性质，也可以把所有的元素都向后移动一位

class Deque {
    constructor() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};
    }
    addFront(element) {
        this.lowestCount--;
        this.items[this.lowestCount] = element;
    }
    addBack(element) {
        this.items[this.count] = element;
        this.count++;
    }
    removeFront() {
        if (this.isEmpty()) return;
        const ele = this.items[this.lowestCount];
        delete this.items[this.lowestCount];
        this.lowestCount++;
        return ele;
    }
    removeBack() {
        if (this.isEmpty()) return;
        const ele = this.items[this.count];
        delete this.items[this.count];
        this.lowestCount--;
        return ele;
    }
    peekFront() {
        return this.items[this.lowestCount];
    }
    peekBack() {
        return this.items[this.count - 1];
    }
    isEmpty() {
        return this.count === this.lowestCount
    }
    size() {
        return this.count - this.lowestCount
    }
    clear() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};
    }
}

循环队列

队列模拟循环队列，击鼓传花问题

规则：有五位玩家，从第一位开始游戏，每轮游戏传7次，结束后花在谁手里，谁就被淘汰，从下一个人继续开始

• 把玩家加入到上面创建好的队列中

const player = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
const queue = new Queue();

for (let p of player) {
    queue.enqueue(p);
}

• game函数执行，表示游戏开始，输入每轮传花次数7，最终返回获胜玩家

  每次传花经过的人，添加到队列尾部，形成一个循环队列，循环停止时，队列头部的就是拿到花的人，被淘汰即从头部移除

function game(queue, nums) {
    while (queue.size() > 1) {
        for (let i = 0; i < nums; i++) {
            queue.enqueue(queue.dequeue());
        }
        console.log("淘汰==" + queue.dequeue())
    }
    console.log('获胜==' + queue.peek());
}
game(queue, 7)

解决回文数

可以通过栈这种数据结构解决

本章也可以使用双端队列解决，先把字符串插入到双端队列中，通过while循环检查头部元素和尾部元素是否相同，不同则跳出

JavaScript 任务队列

在浏览器中打开新标签时，就会创建一个任务队列。这是因为每个标签都是单线程处理所有的任务，称为事件循环。

浏览器要负责多个任务，如渲染HTML、执行JavaScript 代码、处理用户交互（用户输入、鼠标点击等）、执行和处理异步请求

打赏