首页私人日誌JavaScript队列数据结构详解

JavaScript队列数据结构详解

admin 10-17 17:37 388次浏览

  今天我们讲讲JavaScript队列数据结构详解。

什么是队列?

  队列是一种先进先出的数据结构,队列有两种操作:插入删除入队出队。简单来说就是允许插入的一端称为队尾、允许删除的一端称为队头

  如下图展示了栈这个数据结构:

  JavaScript中的队列

  要知道JavaScript中没有有关队列的数据模型,因此我们需要通过数组进行模拟,当数组中提供的push()和shift()选项,正好实现先入后出的的操作,

  示例代码如下:

  const queue = []
  // 入队
  stack.push(1)
  stack.push(2)
  // 出队
  const v1 = stack.shift() // 1
  const v2 = stack.shift() // 2

  JavaScript中的应用场景

  队列和栈一样,是算法和程序中最常用的辅助结构,其的应用十分广泛,比如以下场景:

  一般都是先进先出,在队列中也是如此。JavaScript中的异步任务队列,异步任务队列是一个典型的应用队列的例子。

  最近的请求次数

  现在我们就来运用实际,就是933. 最近的请求次数,我们现在要用一个 **** 类来计算特定时间范围内最近的请求。

  解题思路如下:

  在类中创建一个队列,用于保存最近请求;就可以让ping时保存请求;判断队头请求时间是否比t-3000的时间少,如果是则出队,并继续判断,如果不是则返回队列长度。

  实现代码如下:

  var RecentCounter = function() {
  this.q = []
  };
  /**
  * @param {number} t
  * @return {number}
  */
  RecentCounter.prototype.ping = function(t) {
  this.q.push(t)
  while(this.q[0] < t - 3000) {
  this.q.shift()
  }
  return this.q.length
  };

  补充

  概念和结构:

  队列是一种先进先出(FIFO)的数据结构。

  队列的第一个元素所在位置称为队头,最后一个元素所在位置称为队尾

  不包含任何元素的队列称为空队列

  队列的操作:队列有五种常用操作,分别为:

  入队 enqueue(element)

  出队 dequeue()

  检查队头元素 front()

  检查队列是否为空 isEmpty()

  获取队列的长度 size()

  JS实现:

  JS里面的队列结构也是通过数组(Array)来实现的。

  function Queue(){
  //私有变量不被外界获取
  let queue = [];
  //入队
  this.enqueue = function(element){
  queue.push(element);
  }
  //出队
  this.dequeue = function(){
  return queue.shift();
  }
  //检查队头元素
  this.front = function(){
  return queue[0];
  }
  //检查队列是否为空
  this.isEmpty = function(){
  return queue.length === 0;
  }
  //获取队列长度
  this.size = function(){
  return queue.length;
  }
  }

JavaScript队列数据结构详解相关都已讲述完。

  

JavaScript队列数据结构详解
一分快三赚钱平台推荐_分分快三中奖查询 大小单双稳赢技巧_红牛快三免费计划
相关内容