Skip to main content

队列

  • 队列是一种线性数据结构，用于存储一组有序的元素。
  • 队列的元素遵循 FIFO（先进先出）的原则，即最先进入的元素最先出队列。
  • 队列有两个基本操作：enqueue（入队）和 dequeue（出队）。
  • 队列还有一个常用的操作：peek（查看队首元素）/front、 size(队列长度) 、isEmpty()、toString()。

队列的实现​

 function Queue() {
   this.items = [];
 ​
   // 1.将元素加入队列
   Queue.prototype.enqueue = function (element) {
     return this.items.push(element);
   };
 ​
   // 2.从队列中删除元素
   Queue.prototype.dequeue = function () {
     return this.items.shift();
   };
 ​
   // 3.查看前端的元素
   Queue.prototype.peek = function () {
     return this.items[0];
   };
 ​
   // 4.查看队列是否为空
   Queue.prototype.isEmpty = function () {
     return this.items.length === 0;
   };
 ​
   // 5.查看队列元素个数
   Queue.prototype.size = function () {
     return this.items.length;
   };
 ​
   // 6.toString方法
   Queue.prototype.toString = function () {
     // 返回格式如： 10 20 30 等
     let resString = this.items.join(" ");
     return resString;
   };
 }
// test
const queue = new Queue();
queue.enqueue('10', '20', '30');
queue.size();  // 3
queue.dequeue(); //  ['20', '30']
queue.peek();  // 20

常用算法：击鼓传花​

 const Queue = require("./queue");
 ​
 /**
  * 击鼓传花游戏规则：
  * 几个朋友一起玩一个游戏，围成一圈，开始数数，数到某个数字的人自动淘汰
  * 最后剩下的这个人会获得胜利，请问：最后胜利者原来在哪一个位置上
  */
 let names = ["小明", "小红", "小亮"];
 function passGame(nameList, stopNum = 1) {
   let q = new Queue();
   for (const item of nameList) {
     q.enqueue(item);
   }
 ​
   while (q.size() > 1) {
     for (let i = 0; i < stopNum - 1; i++) {
       q.enqueue(q.dequeue());
     }
     q.dequeue();
   }
   console.log("最后剩下的人是:", q.front()); // 最后剩下的人是: 小红
   return nameList.indexOf(q.front()); //返回对应的位置
 }
 ​
 console.log(passGame(names, 3)); // 1

常用算法-最近请求次数​

 var RecentCounter = function () {
   this.queue = [];
 };
 ​
 /**
  * @param {number} t
  * @return {number}
  */
 RecentCounter.prototype.ping = function (t) {
   this.queue.push(t)
   // 将3000ms之前的数据，踢出队列
   while (this.queue[0] < t - 3000) {
     this.queue.shift()
   }
   // 队列中剩下的元素个数就是最近的请求次数
   return this.queue.length
 };