使用 JavaScript 的数据结构：堆栈和队列

Web 开发中最常用的两种数据结构是堆栈和队列。许多 Internet 用户，包括 Web 开发人员，都没有意识到这一惊人的事实。如果您是这些开发人员中的一员，那么请准备好两个具有启发性的示例：文本编辑器的撤消操作使用堆栈来组织数据，以及 Web 浏览器的事件循环，它处理事件（单击、悬停等） , 使用队列来处理数据。

现在暂停片刻，想象一下我们作为用户和开发人员有多少次使用堆栈和队列。这太神奇了，对吧？由于它们在设计上的普遍性和相似性，我决定使用它们来向您介绍数据结构。 

堆栈

在计算机科学中，堆栈是一种线性数据结构。如果此语句对您来说具有边际价值，就像它最初对我所做的那样，请考虑以下替代方案：堆栈将数据组织成顺序。 

这种顺序通常被描述为像自助餐厅里的一堆盘子。将盘子添加到一堆盘子中时，盘子会保留添加时间的顺序；此外，当添加一个盘子时，它会被推向堆栈的底部。每次我们添加一个新盘子时，该盘子都会被推向堆栈的底部，但它也代表了盘子堆栈的顶部。 

使用盘子表示堆栈

这个添加盘子的过程将保留每个盘子被添加到堆栈中的顺序。从堆叠中取出印版也将保留所有印版的顺序。如果从堆叠顶部移除一个盘子，则堆叠中的每个其他盘子仍将保持堆叠中的正确顺序。我所描述的（可能用太多词）是大多数自助餐厅如何添加和移除盘子！ 

为了提供一个更技术性的堆栈示例，让我们回顾一下文本编辑器的撤消操作。每次将文本添加到文本编辑器时，都会将该文本推入堆栈。文本编辑器的第一个添加代表堆栈的底部；最近的更改代表堆栈的顶部。如果用户想要撤消最近的更改，则移除堆栈的顶部。可以重复这个过程，直到堆栈中没有更多的添加，这是一个空白文件！  

堆栈的表示

堆栈的操作

既然我们现在有了一个栈的概念模型，让我们定义一个栈的两个操作：

• push(data)将数据添加到栈顶。

• pop()删除并返回最近添加的数据。

在 javascript 中实现堆栈

在我们开始之前，我应该提到 JavaScript 有一个很棒的内置堆栈（和队列）实现：Array类型。没错：每个 javaScript 数组都有push()和pop()函数。因此，如果您想在生产代码中使用堆栈（或队列），只需使用常规 JavaScript 数组即可。 

话虽如此，从头开始实现堆栈仍然是一个很好的学习练习！ 

堆栈的属性

对于我们的实现，我们将创建一个名为 Stack. 的每个实例 Stack都有两个属性：_size和_storage。

对于我们的实现，我们将创建一个名为 Stack. 的每个实例 Stack都有两个属性：_size和_storage。

class Stack {
  constructor() {
    this._size = 0;
    this._storage = {};
  }
}

this._storage使每个实例Stack 都有自己的容器来存储数据；this._size 反映数据被推送到当前版本的次数Stack。如果创建了一个新的实例Stack 并将数据推入其存储，this._size则将增加到1。如果再次将数据推入堆栈，this._size则将增加到2。如果从堆栈中删除数据，this._size则将减少到1 . 

堆栈的方法

我们需要定义可以从堆栈中添加（推送）和删除（弹出）数据的方法。让我们从推送数据开始。 

将数据推送到堆栈 push(data)

我们对这种方法有两个要求： 

1. 每次添加数据时，我们都希望增加堆栈的大小。

2. 每次添加数据时，我们都希望保留添加数据的顺序。

push(data) {
    // assigns size as a key of storage
    // assigns data as the value of this key
    this._storage[this._size] = data;
    
    // Increases the size of our storage
    this._size++;
}

我们的实现 push(data) 包括以下逻辑。声明一个名为的变量size并为其赋值this._size++。赋值size 为 的键this._storage，赋值data 为对应键的值。 

如果我们的堆栈调用push(data)了五次，那么我们的堆栈大小将为 5。第一次推送到堆栈将为该数据分配一个 1 in 的键this._storage。第五次调用push(data) 将为该数据分配一个 5 in 的键this._storage。我们刚刚为我们的数据分配了顺序！

从堆栈中弹出数据 pop()

我们现在可以将数据推送到堆栈；下一个逻辑步骤是从堆栈中弹出（删除）数据。从堆栈中弹出数据不仅仅是删除数据；它只删除最近添加的数据。 

以下是我们对这种方法的目标： 

1. 使用堆栈的当前大小来获取最近添加的数据。

2. 删除最近添加的数据。

3. 减_this._size一。

4. 返回最近删除的数据。

5. null如果堆栈为空，则返回。

pop() {
  if (this._size == 0) 
    return null;
  
  let deletedData = this._storage[this._size - 1];

  delete this._storage[this._size - 1];
  this._size--;

  return deletedData;
}

pop()满足我们五个目标中的每一个。首先，我们声明两个变量：size初始化为堆栈的大小，并deletedData 分配给最近添加到堆栈的数据。其次，我们删除了我们最近添加的数据的键值对。第三，我们将堆栈的大小减 1。第四，我们返回从堆栈中删除的数据。  

如果我们测试我们当前的实现pop()，我们会发现它适用于以下用例。如果我们push(data)将数据写入堆栈，堆栈的大小会增加 1。如果我们pop()从堆栈中获取数据，堆栈的大小会减一。 

pop()但是，如果我们在将任何数据添加到堆栈之前尝试使用push()，我们将得到null。

使用 JavaScriptArray作为堆栈 

即使我们在本文中从头开始实现堆栈，也不必每次都编写逻辑来构建堆栈。堆栈已在 JavaScript 数组中实现。JavaScript 提供了两种方法，push并pop在数组中执行相同的操作。

以下是如何使用 JavaScript 的内置堆栈：

const nums = [5, 8, 1, 4];
nums.push(6);

console.log(nums); // [5, 8, 1, 4, 6]

在上面的例子中，nums是一个数字数组。6我们使用方法推入push。

操作的用法pop也类似。您在数组上调用该pop方法，它会删除数组的最后一个元素。

const nums = [5, 8, 1, 4];
const num = nums.pop();

console.log(num); // 4
console.log(nums); // [5, 8, 1]

从栈到队列

当我们想要按顺序添加数据和删除数据时，堆栈很有用。根据其定义，堆栈只能删除最近添加的数据。如果我们想删除最旧的数据会发生什么？我们想使用一个名为队列的数据结构。

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

为了帮助您概念化这将如何工作，让我们花点时间使用一个类比。想象一个队列与熟食店的售票系统非常相似。每个客户拿一张票，并在呼叫他们的号码时得到服务。拿第一张票的顾客应该先得到服务。 

让我们进一步想象这张票上显示了数字“一”。下一张票上显示数字“二”。拿第二张票的顾客将获得第二张服务。（如果我们的票务系统像栈一样运行，那么首先进入栈的客户将是最后一个被服务的客户！）

真实世界队列的示例

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

队列的操作

由于我们现在有一个队列的概念模型，让我们定义它的操作。您会注意到，队列的操作与堆栈非常相似。不同之处在于删除数据的位置。 

• enqueue(data) 将数据添加到队列中。 

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

JavaScript 中队列的实现

现在让我们编写队列的代码！同样，JavaScript 数组已经实现了这些队列操作，但我们将从头开始编写它们以供练习。

队列的属性

对于我们的实现，我们将创建一个名为Queue. 然后我们将添加三个属性：_oldestIndex、_newestIndex和_storage。_oldestIndex两者的需求 _newestIndex将在下一节中变得更加清晰。 

class Queue {
  constructor() {
    this._oldestIndex = 0;
    this._newestIndex = 0;
    this._storage = {};
  }
}

队列的方法

我们现在将创建在队列的所有实例之间共享的三个方法：size()、enqueue(data)和dequeue(data)。我将概述每种方法的目标，揭示每种方法的代码，然后解释每种方法的代码。 

获取队列的大小 size()

size() {
  return this._newestIndex - this._oldestIndex;
}

实现size()可能看起来微不足道，但它可能有点棘手。让我解释一下原因：我们必须同时跟踪队列的开头和结尾。由于我们在一端添加并从另一端移除，因此队列的大小是它们之间的差异。

再想想熟食店的例子。当客户进来并从票务系统取票时，队列的大小会增加一。当工作人员呼叫该工单时，队列的大小会减一。在此示例中，客户最近拨打的号码对应_newestIndex物业，员工最后拨打的号码对应_oldestIndex物业。他们之间的区别在于仍在等待他们的号码被呼叫的客户数量。

将数据添加到队列中 enqueue(data)

对于enqueue，我们有两个目标：

1. 将值添加到作为键this._storage的值。_newestIndex

2. 将 的值增加_newestIndex一。

基于这两个目标，我们将创建以下实现enqueue(data)：

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

如您所见，这段代码正是我们需要的。

这就是我们需要的所有代码enqueue(data)。现在让我们实施dequeue().

从队列中删除数据 dequeue() 

以下是此方法的目标： 

1. 删除队列中最旧的数据。

2. 加_oldestIndex一。

3. null如果队列为空，则返回。

dequeue() {
  if (this._oldestIndex == this._newestIndex)
    return null;

  let deletedData = this._storage[this._oldestIndex];
  delete this._storage[this._oldestIndex];
  this._oldestIndex++;
  return deletedData;
}

在 的主体中dequeue()，我们声明了两个变量。第一个变量oldestIndex为 分配队列的当前值this._oldestIndex。第二个变量deletedData被赋予 中包含的值this._storage[oldestIndex]。 

接下来，我们删除队列中最旧的索引。删除后，我们递增this._oldestIndex1。最后，我们返回刚刚删除的数据。oldestIndex当和的值newestIndex相等时，队列为空，我们返回null。 

使用内置方法的队列操作

与内置的 Stack 实现类似，队列也可以通过一些 JavaScript 方法使用。JavaScript 提供了两种方法，shift和push.

您可以将该push()方法视为将提供的数据添加到数组末尾的入队操作。 

入队操作使用push()

const nums = [5, 8, 1, 4];
nums.push(2, 3);
console.log(nums); //[5, 8, 1, 4, 2, 3 ]

出队操作使用shift

该shift()方法从索引位置 0 中删除一个元素并返回该值，就像该dequeue方法一样。实际上，它的shift()工作原理与它相同，pop()但它从数组的开头删除了元素。

const nums = [5, 8, 1, 4];
const num = nums.shift();
console.log(num); // 5
console.log(nums); // [8, 1, 4]

尽管使用内置函数可以轻松完成堆栈和队列操作，但了解这些数据结构背后的核心逻辑至关重要。它可以帮助你加强你的基础。这就是从头开始展示实现的原因。

结论

在本文中，我们探索了两种线性数据结构：堆栈和队列。堆栈按顺序存储数据并删除最近添加的数据；队列按顺序存储数据，但删除最旧的添加数据。 

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