likes
comments
collection
share

在JavaScript中实现队列的教程

作者站长头像
站长
· 阅读数 30

成为一名优秀的开发人员需要有多个学科的知识。

第一个要求是了解你选择的编程语言。如果你正在阅读这篇文章，很可能你使用的是JavaScript。

然而，在了解编程语言的基础上，你还必须了解如何组织数据，以便根据任务轻松而有效地处理数据。这就是数据结构开始发挥作用的地方。

在这篇文章中，我将描述队列数据结构，它有哪些操作，以及向你介绍JavaScript中的队列实现。

1.队列数据结构

如果你喜欢旅行（像我一样），你很可能通过了机场的登记程序。如果有很多旅客愿意办理登机手续，自然就会在办理登机手续的柜台前排起队伍。

一个刚刚进入机场并想办理登机手续的旅客会排到队列中。另一个刚刚在服务台通过办理登机手续的旅客则从队列中脱队。

这就是现实世界中队列的例子--队列数据结构的工作方式也是如此。

队列是一种先输入后输出（FIFO）的数据结构。第一个排队的项目（输入）是第一个去排队的（输出）。

一个队列有2个指针：头和尾。队列中最早排队的项目在头部，而最新排队的项目在队尾。

回顾机场的例子，办理登机手续的旅客是队列的头。刚刚进入队列的旅客则在队尾。

在JavaScript中实现队列的教程

从更高的角度来看，队列是一种数据结构，它可以让你按照项目进来的顺序一个一个地处理。

2.对队列的操作

队列支持2个主要操作：enqueue和dequeue。此外，你可能会发现拥有窥视和长度操作是很有用的。

2.1 Enqueue操作

enqueue操作在队列的尾部插入了一个项目。被排队的项目成为队列的尾部。

在JavaScript中实现队列的教程

上图中的enqueue操作在队尾插入了项目8 。8 成为队尾。

queue.enqueue(8);

2.2 Dequeue操作

Dequeue操作提取了队列头部的项目。队列中的下一个项目成为头部。

在JavaScript中实现队列的教程

在上图中，dequeue操作返回并从队列中删除了项目7 。在去queue之后，项目2 成为新的头部。

javascript

queue.dequeue(); // => 7

2.3 Peek操作

peek操作读取队列的头部，不改变队列。

在JavaScript中实现队列的教程

在上图中，项目7 是队列的头部。peek操作只是返回头部--项目7 --而不修改队列。

queue.peek(); // => 7

2.4 队列长度

长度操作计算队列包含多少个项目。

在JavaScript中实现队列的教程

图中的队列有4个项目。4,6,2, 和7 。 因此，队列长度为4 。

javascript

queue.length; // => 4

2.5 队列操作的时间复杂性

关于所有的队列操作--enqueue、dequeue、peek和length，重要的是所有这些操作必须在恒定的时间内进行O(1) 。

恒定时间O(1) ，意味着无论队列的大小（可以有10个或100万个项目）：enqueue、dequeue、peek和length操作必须在相对相同的时间内执行。

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 通过一个数字索引保存队列中的项目。头部项目的索引由this.headIndex 来跟踪，尾部项目由this.tailIndex 来跟踪。

队列方法的复杂性

queue() Queue,dequeue(),peek() 和length() 类的方法只使用。

  • 属性访问器（例如：this.items[this.headIndex] ）。
  • 或者执行算术操作（例如：this.headIndex++ ）。

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

4.总结

队列数据结构是一种先入先出（FIFO）的类型：最早被排队的项目是最早被取消的。

队列有2个主要操作：enqueue和dequeue。此外，队列还可以有一些辅助性的操作，如peek和length。

所有队列操作都必须在恒定的时间内进行O(1) 。

挑战：改进dequeue() 和peek() 方法，如果在空队列上执行，则抛出错误。请在下面的评论中写出你的解决方案!

转载自:https://juejin.cn/post/7126039152797646862
评论
请登录