乐趣区

关于javascript:在JavaScript中实现队列

作为一个优良的程序猿须要具备常识的广度。首先是要理解你抉择的编程语言。如果你正在浏览这篇文章,最有可能应用 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 操作读取队首的我的项目,然而不扭转队列。

上图中 7 是队首。peek 操作只需返回队首 7 然而不批改队列。

queue.peek(); // => 7

2.4 length

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

上图中的队列有 4 项:462 和。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 跟踪。

队列办法的复杂度

Queuequeue()dequeue()peek()length() 办法中存在:

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

这些办法的工夫复杂度是恒定的工夫 O(1)

4. 总结

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

队列有 2 个次要操作:入队和出队。另外,队列能够有辅助操作,例如 peek 和 length。

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

挑战一下:改良 dequeue()peek() 办法,当在空队列上执行时会抛出谬误。


本文首发微信公众号:前端先锋

欢送扫描二维码关注公众号,每天都给你推送陈腐的前端技术文章


欢送持续浏览本专栏其它高赞文章:

  • 深刻了解 Shadow DOM v1
  • 一步步教你用 WebVR 实现虚拟现实游戏
  • 13 个帮你进步开发效率的古代 CSS 框架
  • 疾速上手 BootstrapVue
  • JavaScript 引擎是如何工作的?从调用栈到 Promise 你须要晓得的所有
  • WebSocket 实战:在 Node 和 React 之间进行实时通信
  • 对于 Git 的 20 个面试题
  • 深刻解析 Node.js 的 console.log
  • Node.js 到底是什么?
  • 30 分钟用 Node.js 构建一个 API 服务器
  • Javascript 的对象拷贝
  • 程序员 30 岁前月薪达不到 30K,该何去何从
  • 14 个最好的 JavaScript 数据可视化库
  • 8 个给前端的顶级 VS Code 扩大插件
  • Node.js 多线程齐全指南
  • 把 HTML 转成 PDF 的 4 个计划及实现

  • 更多文章 …
退出移动版