在 JavaScript 中用 1 个数组创建 3 个堆栈

什么是堆栈？

班级分类

整合起来

这道题出自《Cracking The Coding Interview》这本书。练习内容是：“描述如何使用一个数组实现三个堆栈。”

什么是堆栈？

栈是一种基于“后进先出”（LIFO）概念的数据结构。你可以把它想象成一摞书，必须先把最上面的书取出来，才能取出最下面的书。JavaScript 没有原生的栈数据结构，所以我们今天要创建一个。

我们的数组将包含三个大小固定的不同堆栈。堆栈顶部位于右侧，堆栈底部位于左侧。您可以将其绘制成如下图所示。如果此堆栈已满，则底部元素将位于stack[0]，顶部元素将位于stack[stack.length-1]。

班级分类

我们的堆栈将具有固定大小，该大小等于实例化时传入的参数。

特性

以下属性将在构造函数中初始化：

• _stackCapacity：一个堆栈可容纳的最大元素数量。这是一个只读属性，因此在其前面添加了下划线。
• values：包含三个堆栈中所有元素的数组
• sizes：具有三个索引的数组，每个索引代表相应堆栈中的当前元素数。
• numberOfStacks：一个常量，表示数组可容纳的堆栈总数。我们将其初始化为 3，但 MultiStack 类的未来迭代可以接受第二个参数，以自定义数组可容纳的堆栈数量。

方法

我们的 MultiStack 类将包含以下方法：

• get stackCapacity()：返回每个堆栈的总容量（这只是我检查一切是否按预期工作的方法，我们实际上不会使用它。）
• push(stackNumber, value)：将值推送到相应堆栈号的顶部。
• pop(stackNumber)：从相应的堆栈编号中弹出顶部项目。
• peek(stackNumber)：返回相应堆栈编号的栈顶元素。这只是让我们“窥视”一下栈顶元素的一种方式；不会发生堆栈突变。
• isEmpty(stackNumber)：返回一个布尔值，指示相应的堆栈是否有值。
• isFull(stackNumber)：返回一个布尔值，指示相应的堆栈是否已满。
• indexOfTop(stackNumber)：一种辅助方法，它返回值数组中相应堆栈顶部元素的索引。

构造函数

我们要做的第一件事是创建构造函数。它接受一个参数，即堆栈大小。因此，值数组的总长度将是堆栈大小的 3 * （因为我们将其初始化numberOfStacks为 3）。

我们将初始化 size 数组，使其包含三个索引，值为零。为了便于说明，我们假设压入堆栈的值是正整数。您可以根据需要更改此逻辑。

获取堆栈容量

此方法返回每个堆栈的总容量（这只是我检查一切是否按预期工作的方法，我们实际上不会使用它。）

您可以在MDN上阅读有关 JavaScript getter 的更多信息。

已满

此方法返回一个布尔值，指示相应堆栈是否已满。它将检查相应堆栈上当前有多少个元素，并将其与堆栈容量进行比较。

为空

此方法返回一个布尔值，指示相应的堆栈是否有值。

顶部索引

这是一个辅助方法，它返回值数组中相应堆栈顶部元素的索引。

这个解释可能有点难懂，所以坚持下去！我附上了图表，以便更好地直观地展示这个过程。

首先，我们需要获取堆栈在值数组中的偏移量。为此，我们将所需的堆栈编号乘以每个堆栈的容量。

例如，假设每个堆栈的值为 5，让我们找到堆栈 2 中顶部项目的索引。_stackCapacity堆栈包含以下元素：

• 堆栈 0：[1, 12]
• 堆栈 1：[18, 8, 2]
• 堆栈 2：[5, 9, 66, 15]

以下是值数组的直观表示：

步骤 1：计算偏移量；找到堆栈二底部项目的索引

假设我们的堆栈从零开始（即堆栈 0、堆栈 1、堆栈 2），我们可以通过将我们要查找的堆栈大小（2）乘以堆栈容量（即实例化时传入的值）来找到堆栈 2 的底部在 values 数组中的起始位置。如果我们的堆栈容量为 5，我们就知道堆栈 2 的底部元素在 values 数组中的索引 10 处开始。

堆栈 2 中底部元素的索引 = 我们正在寻找的堆栈 * 每个堆栈的容量。

堆栈 2 底部元素的索引 = 2 * 5（从中找到_stackCapacity）

堆栈 2 底部元素的索引 = 10

步骤 2：计算当前堆栈二中的值总数

我们已经知道栈 2 中有多少个值；它们保存在 size 数组中。因此，通过获取 的值，sizes[2]我们就能知道栈 2 中有多少个元素：4

步骤 3：将偏移量与堆栈中的值总数相加，再减一

我们必须从堆栈中的项目数中减一，因为我们的数组从索引零开始。

当我们把所有这些加起来时，我们得到：

堆栈 2 顶部元素的索引 = 偏移量 + 堆栈 2 中的值的数量 — 1

堆栈 2 顶部元素的索引 = 10 + 4 — 1

堆栈 2 顶部元素的索引 = 13

代码如下：

推

push 方法将一个值推送到相应堆栈的顶部。它接受两个参数：

• 将值推送到堆栈
• 价值

1. 我们要做的第一件事是检查堆栈是否已满。如果已满，则发送console.log消息Stack number ${stackNumber} is full。
2. 如果堆栈未满，则增加堆栈中的项目数，该数量可以在 size 数组中找到。
3. 然后将新值添加到栈顶。我们将使用indexOfTop上面解释的方法获取栈顶，并在其上添加一个值。
4. 如果添加成功，我们会给您发送console.log一条友好消息。

流行音乐

此方法弹出相应堆栈编号的顶部项目。它接受一个参数：

• 弹出值的堆栈

1. 首先，我们必须使用该方法检查堆栈是否为空isEmpty。如果是空的，我们将返回一条console.log消息。
2. 如果堆栈不为空，我们将使用方法获取堆栈顶部元素的索引indexOfTop并将其保存到名为的变量中topIndex。
3. 现在让我们获取该元素的值。我们可以使用 来实现this.values[topIndex]。我们将返回这个元素，因此我们需要将其保存到变量中。
4. 我们还需要告诉 values 数组，此索引处的值已不存在。我们将它显式设置为零（如果你的堆栈可以接受零作为值，这可能会引起问题，但为了方便起见，我们假设堆栈只接受正整数）。
5. 我们还必须减少sizes数组中堆栈的大小。我们可以使用 来实现this.sizes[stackNumber]--。
6. 最后，让我们返回刚刚弹出的值。

窥视

此方法返回相应堆栈编号的栈顶元素。它不会改变堆栈，只是让你查看栈顶的元素。它接受一个参数：

• 我们想要查看栈顶值的堆栈

1. 首先，我们必须检查堆栈是否为空。我们可以使用 isEmpty 方法来检查。如果为空，则会显示console.log一条友好的消息。
2. 如果堆栈不为空，我们需要找到堆栈顶部元素的索引。我们可以使用此indexOfTop方法来实现。
3. 最后，我们可以用返回在该索引处找到的值this.values[topIndex]。

整合起来

最终的课程如下：

现在，您已经创建了一个表示三个固定大小堆栈的数组！您可以在这里查看此类的 CodePen 。