用JavaScript实现队列

作为一个优秀的程序猿需要具有知识的广度。首先是要了解你选择的编程语言。

站在用户的角度思考问题，与客户深入沟通，找到滦州网站设计与滦州网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：网站建设、做网站、企业官网、英文网站、手机端网站、网站推广、域名注册、网站空间、企业邮箱。业务覆盖滦州地区。

然而在熟悉了编程语言之后，你还必须了解如何根据任务轻松且有效地操纵数据。这就是数据结构的用武之地。

在本文中，我将描述队列数据这个结构：它都有哪些操作以及在 JavaScript 中怎样实现。

1. 队列数据结构

如果你喜欢四处旅行，肯定在火车站经历过检票这道手续。如果有很多人要坐火车，那么很自然地会形成一个队列。刚进入车站的人加入队列。另一边刚刚通过检票的人从队列中走出。这就是队列的一个例子，与队列数据结构的操作方式相同。

队列是一种遵循先入先出(FIFO)规则的数据结构。第一个进入队列中的项目(输入)是第一个出队(输出)的。

队列有2个指针：队首和队尾。最先进入队列进行排队的项目位于队首，而最后进入队列的项目位于队尾。

回顾车站的例子，第一个检票的是在队列的队首。刚进入队列的人在队尾。

队列数据结构

从更高的层面来看，队列是一种允许你按照先后顺序处理项目的数据结构。

2. 队列的操作

队列支持 2 个主要操作：入队(enqueue)和出队(dequeue)，另外还有 peek 和 length 操作。

2.1 入队操作

入队操作在队列的尾部插入项目，使其成为队列的队尾。

入队操作

上图中的入队操作在队尾插入了 8，之后 8 成为队列的队尾。

 
 
 
 
  
  
  
  queue.enqueue(8);

2.2 出队操作

出队操作取出队列中第一个项目，此时队列中的下一个项目成为队首。

出队操作

在上图中，出队操作返回项目7并从队列中删除。出队之后之后，项目 2 成为新的队首。

 
 
 
 
  
  
  
  queue.dequeue(); // => 7

2.3 Peek 操作

Peek 操作读取队首的项目，但是不改变队列。

Peek 操作

上图中 7 是队首。peek 操作只需返回队首 7 但是不修改队列。

 
 
 
 
  
  
  
  queue.peek(); // => 7

2.4 length

length 操作返回队列中包含项目的数量。

Length 操作

上图中的队列有 4 项：4、6、2 和。7。结果队列长度为 4。

 
 
 
 
  
  
  
  queue.length; // => 4

2.5 队列操作的时间复杂度

关于队列所有操作的重点：enqueue，dequeue，peek 和 length 必须以常数时间复杂度 O(1) 执行。

常数时间复杂度 O(1) 意味着无论队列大小如何(不管是有 10 个还是 100 万个项目)，这些操作都必须在相对一致的时间内执行。

3. 用 JavaScript 实现队列

来看一下怎样在保证所有操作必须以常数时间复杂度O(1) 要求实现队列这种数据结构。

 
 
 
 
  
  
  
  class Queue {
  
  
  
    constructor() {
  
  
  
      this.items = {};
  
  
  
      this.headIndex = 0;
  
  
  
      this.tailIndex = 0;
  
  
  
    }
  
  
  
  
  
  
  
    enqueue(item) {
  
  
  
      this.items[this.tailIndex] = item;
  
  
  
      this.tailIndex++;
  
  
  
    }
  
  
  
  
  
  
  
    dequeue() {
  
  
  
      const item = this.items[this.headIndex];
  
  
  
      delete this.items[this.headIndex];
  
  
  
      this.headIndex++;
  
  
  
      return item;
  
  
  
    }
  
  
  
  
  
  
  
    peek() {
  
  
  
      return this.items[this.headIndex];
  
  
  
    }
  
  
  
  
  
  
  
    get length() {
  
  
  
      return this.tailIndex - this.headIndex;
  
  
  
    }
  
  
  
  }
  
  
  
  
  
  
  
  const queue = new Queue();
  
  
  
  
  
  
  
  queue.enqueue(7);
  
  
  
  queue.enqueue(2);
  
  
  
  queue.enqueue(6);
  
  
  
  queue.enqueue(4);
  
  
  
  
  
  
  
  queue.dequeue(); // => 7
  
  
  
  
  
  
  
  queue.peek();    // => 2
  
  
  
  
  
  
  
  queue.length;    // => 3

const queue = new Queue() 是创建队列的实例。

queue.enqueue(7) 方法将 7 存入队列中。

queue.dequeue() 从队列中取出一个头部项目，而 queue.peek() 只读队首项。

最后的 Queue.Length 显示队列中还有多少个项目。

关于实现：在 Queue 类中，普通对象 this.Items 将队列的项目通过数值索引保持。队首项的索引由 Where.HeadInex 跟踪，队尾项由 this.tailIndex 跟踪。

队列方法的复杂度

在 Queue 的 queue()、 dequeue()、 peek() 和 length() 方法中存在：

属性访问器(如:this.items[this.headIndex])，
执行算数操作(如:this.headidex++)

这些方法的时间复杂度是恒定的时间 O(1)。

4. 总结

队列是一种遵循先入先出(FIFO)规则的的数据结构。

队列有 2 个主要操作：入队和出队。另外，队列可以有辅助操作，例如 peek 和 length。

所有队列操作都必须以常数时间 O(1) 执行。

挑战一下：改进 dequeue() 和 peek() 方法，当在空队列上执行时会抛出错误。

当前标题：用JavaScript实现队列
当前链接：http://www.mswzjz.cn/qtweb/news22/249972.html

攀枝花网站建设、攀枝花网站运维推广公司-贝锐智能，是专注品牌与效果的网络营销公司；服务项目有等

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：贝锐智能

贝锐智能技术为您推荐以下文章