个人中心
gpt4 book ai didi

用JavaScript实现队列

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 26 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章用JavaScript实现队列由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

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

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

用JavaScript实现队列

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

1. 队列数据结构

  。

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

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

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

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

用JavaScript实现队列

队列数据结构 。

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

2. 队列的操作

  。

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

2.1 入队操作 。

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

用JavaScript实现队列

入队操作 。

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

  1. queue.enqueue(8); 

2.2 出队操作 。

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

用JavaScript实现队列

出队操作 。

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

  1. queue.dequeue(); // => 7 

2.3 Peek 操作 。

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

用JavaScript实现队列

Peek 操作 。

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

  1. queue.peek(); // => 7 

2.4 length 。

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

用JavaScript实现队列

Length 操作 。

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

  1. queue.length; // => 4 

2.5 队列操作的时间复杂度 。

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

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

3. 用 JavaScript 实现队列

  。

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

  1. class Queue { 
  2.   constructor() { 
  3.     this.items = {}; 
  4.     this.headIndex = 0; 
  5.     this.tailIndex = 0; 
  6.   } 
  7.  
  8.   enqueue(item) { 
  9.     this.items[this.tailIndex] = item; 
  10.     this.tailIndex++; 
  11.   } 
  12.  
  13.   dequeue() { 
  14.     const item = this.items[this.headIndex]; 
  15.     delete this.items[this.headIndex]; 
  16.     this.headIndex++; 
  17.     return item; 
  18.   } 
  19.  
  20.   peek() { 
  21.     return this.items[this.headIndex]; 
  22.   } 
  23.  
  24.   get length() { 
  25.     return this.tailIndex - this.headIndex; 
  26.   } 
  27. } 
  28.  
  29. const queue = new Queue(); 
  30.  
  31. queue.enqueue(7); 
  32. queue.enqueue(2); 
  33. queue.enqueue(6); 
  34. queue.enqueue(4); 
  35.  
  36. queue.dequeue(); // => 7 
  37.  
  38. queue.peek();    // => 2 
  39.  
  40. 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() 方法，当在空队列上执行时会抛出错误.

原文地址：https://mp.weixin.qq.com/s?__biz=MzI3NzIzMDY0NA==&mid=2247500396&idx=1&sn=0e7dd721cca71caf3e94083e950b532b&chksm=eb6be737dc1c6e21466da237d8cf3af235a323f5d987a16370edb48266aa7865954f0e1741ad&mpshare=1&s 。

最后此篇关于用JavaScript实现队列的文章就讲到这里了,如果你想了解更多关于用JavaScript实现队列的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

26 4 0
文章推荐： 理解 ARM64 内核中对 52 位虚拟地址的支持
文章推荐： MySQL实现创建存储过程并循环添加记录的方法
文章推荐： Linux 内核维护者的真相与误解！
文章推荐： 分享101个MySQL调试与优化技巧
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com