总结前端常用数据结构之队列篇【JavaScript】

推动你的事业，不要让你的事业推动你。——爱因斯坦

目录 队列是什么？JS异步、事件循环、任务队列：队列的实现方法：‌数组实现‌ - 封装队列：对象实现（优化性能）- 封装队列： 队列应用之击鼓传花：

队列是什么？

队列是一种线性表，它只允许在表的一端进行插入操作，而在另一端进行删除操作。 其中，允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。即先进先出！【FIFO - first in first out】。队列中没有元素时，称为空队列。

JS异步、事件循环、任务队列：

点击跳转 - JS同步任务、异步任务（宏任务和微任务） 提示：上图是b站 千锋教育 课程里的图，侵权请联系删除。

队列的实现方法： ‌数组实现‌ - 封装队列：

使用 push() 和 shift() 方法实现入队和出队操作。

class Queue { #item = []; dequeue () { this.#item.shift(); } enqueue (val) { this.#item.push(val); } front () { return this.#item.at(0); } isEmpty () { return this.#item.length === 0; } size () { return this.#item.length; } clear () { this.#item = []; } toString () { return this.#item.join(""); } } let queue = new Queue(); 对象实现（优化性能）- 封装队列：

数组的 shift() 方法时间复杂度为 O(n)，通过对象存储和头尾指针优化出队性能至 O(1)‌。

class Queue { #items = {}; #count = 0; #lowcount = 0; dequeue () { if (this.isEmpty()) { return; } let res = this.#items[this.#lowcount]; delete this.#items[this.#lowcount]; this.#lowcount++; return res; } enqueue (val) { this.#items[this.#count] = val; this.#count++; } front () { return this.#items.at(0); } isEmpty () { return this.size() === 0; } size () { return this.#count - this.#lowcount; } clear () { this.#items = {}; this.#lowcount = 0; this.#count = 0; } toString () { let str = ''; for (let i = this.#lowcount; i < this.#count; i++) { str += `${this.#items[i]} ` } return str; } } let queue = new Queue(); 队列应用之击鼓传花：

击鼓传花游戏通常是指一群人围成一圈传递物品，当鼓声停止时，持有物品的人被淘汰，直到剩下最后一人。 解题思路：

队列循环逻辑‌：当队列长度大于1时，持续将队首元素移动到队尾，每轮循环次数由参数num决定‌。‌淘汰规则‌：每轮循环结束后（即完成num次移动），移除当前队首元素‌。终止条件‌：当队列仅剩一个元素时，返回该元素及其在原数组中的索引‌。

使用js代码解决：

class Queue { #items = {}; #count = 0; #lowcount = 0; dequeue () { if (this.isEmpty()) { return; } let res = this.#items[this.#lowcount]; delete this.#items[this.#lowcount]; this.#lowcount++; return res; } enqueue (val) { this.#items[this.#count] = val; this.#count++; } front () { return this.#items.at(0); } isEmpty () { return this.size() === 0; } size () { return this.#count - this.#lowcount; } clear () { this.#items = {}; this.#lowcount = 0; this.#count = 0; } toString () { let str = ''; for (let i = this.#lowcount; i < this.#count; i++) { str += `${this.#items[i]} ` } return str; } } function game (list, num) { let queue = new Queue(); for (let i = 0; i < list.length; i++) { queue.enqueue(list[i]); } while (queue.size() > 1) { for (let i = 0; i < num; i++) { queue.enqueue(queue.dequeue()) } console.log(queue.dequeue(), '淘汰了'); // queue.dequeue(); } console.log('获胜的是：', queue.dequeue()); // return queue.dequeue(); } game(['kitty', 'Alice', 'AK', 'Box', 'Whe'], 7);