JavaScript 数据结构（2-2）：栈与队列-队列篇

翻译：疯狂的技术宅 说明：本文翻译自系列文章《Data Structures With JavaScript》，总共为四篇，原作者是在美国硅谷工作的工程师 Cho S. Kim 。由京程一灯老编 疯狂的技术宅 翻译。今天为大家奉上本系列第二篇下半部分——队列。 英文：https://code.tutsplus.com/articles/data-structures-with-javascript-stack-and-queue--cms-23348

接上文：JavaScript 数据结构（2-1）：栈与队列-栈篇

从栈到队列

当我们想要按顺序添加数据或删除数据时，可以使用栈结构。根据它的定义，栈可以只删除最近添加的数据。如果想要删除最早的数据该怎么办呢?这时我们希望使用名为queue的数据结构。

队列

与栈类似，队列也是一个线性数据结构。与栈不同的是，队列只删除最先添加的数据。

为了帮助你明白队列这是如何工作的，让我们花点时间举个例子。我们可以把队列想象成为熟食店的售票系统。每个顾客拿一张票，当他们的号码被呼叫时送达。持第一张票的顾客首先接受服务。

再进一步想象一下，这张票上有一个数字“1”。下一张票上有数字“2”。得到二张票的顾客将会第二个接受服务。（如果我们的售票系统像栈一样运行，最先进入堆栈的客户将会最后一个接受服务！）

队列的一个更实际的例子是Web浏览器的事件循环。当触发不同事件时，例如单击某个按钮，点击事件将被添加到事件循环队列中，并按照它们进入队列的顺序进行处理。

现在我们有了队列的概念模型，接下来就定义它的操作。你会注意到，队列的操作和栈非常相似。区别就在被删除的数据在什么地方。

• enqueue(data) 将数据添加到队列中。
• dequeue 删除最早加入队列的数据。

队列的实现

现在让我们开始写队列的代码吧！

队列的属性

在实现队列的代码中，我们将会创建一个名为 Queue 的构造方法。接下来添加三个属性：_oldestIndex, _newestIndex, 和 _storage。在下一小节中，_oldestIndex 和 _newestIndex 的作用将变得更加清晰。

function Queue() {    this._oldestIndex = 1;    this._newestIndex = 1;    this._storage = {};}

队列的方法

现在我们将创建队列会用到的三个方法：size(), enqueue(data), 和 dequeue(data)。我将描述每个方法的作用，写出每个方法的代码，然后解释这些代码。

方法1/3：size( )

这个方法有两个作用：

1. 返回当前队列的长度。
2. 保持队列中键的正确范围。

Queue.prototype.size = function() {    return this._newestIndex - this._oldestIndex;};

实现 size() 可能显得微不足道，但你会很快发现并不是这样的。为了理解其原因，我们必须快速重新审视 size() 在栈结构中的实现。

回想一下栈的概念模型，假设我们把5个盘子添加到一个栈上。我们的栈的大小是5，每个盘子都有一个数字，从1(第一个添加的盘子)到5(最后一个添加的盘子)。如果我们取走三个盘子，就只剩下两个盘子。我们可以简单地用5减去3，得到正确的大小，也就是2。这里是关于栈大小最重要的一点：当前大小相当于从栈顶部的盘子（2）到栈中其他盘子（1）的计数。换句话说，键的范围总是从当前大小到1之间。

现在，让我们将栈大小的实现应用到队列中。假设有五个顾客从我们的售票系统中取到了票。第一个顾客有一张显示数字1的票，第五个客户有一张显示数字5的票。现在有了一个队列，拿着第一张票的第一位顾客。

假设第一个客户接受了服务，这张票会从队列中被移除。与栈类似，我们可以通过从5减去1来获得队列的正确大小。那么服务队列中还有4张票。现在出现了一个问题：队列的大小不能对应正确的票号。如果我们从五减去一个，得到大小是4，但是不能使用4来确定当前队列中剩余票的编号范围。我们并不能确定队列中票号的顺序到底是1到4还是2到5。

这就是 oldestIndex 和 newestIndex 这两个属性 在队列中的用途。所有这一切似乎令人困惑——到现在我仍然会偶尔觉得困惑。下面的例子可以帮助我门理顺所有的逻辑。

假设我们的熟食店有两个售票系统：

1. _newestindex 代表顾客售票系统的票。
2. _oldestindex 代表员工售票系统的票。

对于两个售票系统来说，这是最难掌握的概念：当两个系统中的数字相同时，队列中的每个客户都被处理了，队列是空的。我们将使用下面的场景来加强这种逻辑：

1. 当顾客买票时，顾客的票号从_newestIndex 得到，票的编号是1。顾客售票系统的下一张票号码是2。
2. 员工不买票，员工售票系统中当前票的编号是1。
3. 我们在顾客系统中得到当前的票号2，减去员工系统中的号码1，得到的结果是1。这个数字1表示仍然在队列中没有被删除的票的数量
4. 员工从它们的售票系统中取票，这张票代表正在被服务的顾客的票号，从_oldestIndex中得到，数字为1。
5. 重复第4步，现在差为0，队列中没有其他的票了。

现在属性 _newestindex可以告诉我们被分配在队列中票号的最大值（键），属性 _oldestindex 可以告诉我们最先进入队列中票号（键）。

探讨完了size()，接下来看enqueue(data)方法。

方法2/3：enqueue(data)

对于 enqueue 方法，有两个功能：

1. 使用_newestIndex 的值作为 this._storage 的键，并使用要添加的数据作为该键的值。
2. 将_newestIndex 的值增加1。

基于这两个功能，我们将编写 enqueue(data) 方法的代码：

Queue.prototype.enqueue = function(data) {    this._storage[this._newestIndex] = data;    this._newestIndex++;};

该方法的主体只有两行代码。 在第一行，用 this._newestIndex 为this._storage 创建一个新的键，并为其分配数据。 this._newestIndex 始终从1开始。在第二行代码中，我们将 this._newestIndex 的值增加1，将其更新为2。

以上是方法 enqueue(data) 的所有代码。下面我们来实现方法 dequeue( )。

方法2/3：dequeue( )

以下是此方法的两个功能点：

1. 删除队列中最旧的数据。
2. 属性 _oldestIndex 加1。

Queue.prototype.dequeue = function() {    var oldestIndex = this._oldestIndex,        deletedData = this._storage[oldestIndex];    delete this._storage[oldestIndex];    this._oldestIndex++;    return deletedData;};

在 dequeue( )的代码中，我们声明两个变量。 第一个变量 oldestIndex 给 this._oldestIndex 赋值。第二个变量 deletedData 被赋予 this._storage[oldestIndex] 的值。

下一步，删除队列中最早的索引。之后将 this._oldestIndex 的值加1。最后返回刚刚被删除的数据。

与栈的 pop() 方法第一次实现中出现的问题类似，dequeue() 在队列中没有数据的情况下不应该被执行。我们需要一些代码来处理这种情况。

Queue.prototype.dequeue = function() {    var oldestIndex = this._oldestIndex,        newestIndex = this._newestIndex,        deletedData;    if (oldestIndex !== newestIndex) {        deletedData = this._storage[oldestIndex];        delete this._storage[oldestIndex];        this._oldestIndex++;        return deletedData;    }};

每当 oldestIndex 和 newestIndex 的值不相等时，我们就执行前面的逻辑。

队列的完整实现代码

到此为止，我们实现了一个完整的队列结构的逻辑。下面是全部代码。

function Queue() {    this._oldestIndex = 1;    this._newestIndex = 1;    this._storage = {};}Queue.prototype.size = function() {    return this._newestIndex - this._oldestIndex;};Queue.prototype.enqueue = function(data) {    this._storage[this._newestIndex] = data;    this._newestIndex++;};Queue.prototype.dequeue = function() {    var oldestIndex = this._oldestIndex,        newestIndex = this._newestIndex,        deletedData;    if (oldestIndex !== newestIndex) {        deletedData = this._storage[oldestIndex];        delete this._storage[oldestIndex];        this._oldestIndex++;        return deletedData;    }};

结束语

在本文中，我们探讨了两个线性数据结构：栈和队列。栈按照顺序存储数据，并删除最后添加的数据；队列按顺序存储数据，但删除最先的添加数据。

如果这些数据结构的实现看起来微不足道，请提醒自己数据结构的用途。它们并没有被设计得过于复杂，它们是用来帮助我们组织数据的。在这种情况下，如果您发现有需要按顺序组织数据的场合，请考虑使用栈或队列。

老编总结

第二篇文章用生活中的例子为大家讲解了栈和队列的原理和实现细节，在这里我还要BB两句： 1. 栈的性质是后进先出，英文是 LIFO (Last In First Out)。 2. 队列的性质是先进先出，FIFO (First In First Out)。

嗯，英语还是很有用的。

请等待本系列的第三篇文章：《JavaScript 数据结构（3）：单向链表与双向链表》