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

更新日期: 2022-09-01阅读: 902标签: 堆栈

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

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

堆栈

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

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


使用盘子表示堆栈

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

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


堆栈的表示

堆栈的操作

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

  • push(data)将数据添加到栈顶。
  • pop()删除并返回最近添加的数据。

在 JavaScript 中实现堆栈

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

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

堆栈的属性

对于我们的实现,我们将创建一个名为 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. 每次添加数据时,我们都希望保留添加数据的顺序。
// 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]

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

结论

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

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

来自 :https://www.toutiao.com/article/7137708642010169890

链接: https://fly63.com/article/detial/12073

如何优雅地查看 JS 错误堆栈?

在前端,我们经常会通过 window.onerror 事件来捕获未处理的异常。假设捕获了一个异常,上报的堆栈是这个:这个堆栈,你看得出问题来吗?我们发布到 CDN 的脚本文件,普遍是经过 UglifyJS 压缩的,所以堆栈可读性相当的差。

连续赋值(从堆栈角度解析) a.x = a = {n:2}

今天看到一个面试题,一直想把这个题目解析更加直观化,就跟看小人书一样,看图就能明白其中的原理,所以用PPT做了几张图。接下来我们从以下几点分析以下:

JavaScript中的执行上下文和堆栈是什么?

在这篇文章中,我将深入研究JavaScript最基本的部分之一,即执行上下文。在这篇文章的最后,您应该更清楚地了解解释器要做什么,为什么在声明一些函数/变量之前可以使用它们,以及它们的值是如何确定的。

js中的堆和栈

栈(stack):栈会自动分配内存空间,会自动释放,存放基本类型,简单的数据段,占据固定大小的空间;堆(heap):动态分配的内存,大小不定也不会自动释放

5 张图描绘Web3 堆栈全景

Web3 堆栈最令人难以置信的一点是,它们不需要任何集中协调就可以组合在一起。开发本身是去中心化的。没有主架构师。这与地球上几乎所有其他的开发堆栈项目形成了鲜明的对比。在 Linux 基金会,少数人设定整个 Linux 的方向

异步堆栈追踪:为什么 await 胜过 Promise?

与直接使用 Promise 相比,使用 async/await 不仅可以使代码更具可读性,而且还可以在 JavaScript 引擎中实现一些有趣的优化。这篇文章是关于一个这样的优化,涉及异步代码的堆栈追踪。

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!