Web开发中最常用的两种数据结构是栈和队列。许多Internet用户，包括Web开发人员，都没有意识到这个惊人的事实。如果您是这些开发人员中的一员，请准备好接受两个有启发性的示例：文本编辑器的撤消操作使用堆栈来组织数据，以及处理事件（单击、悬停等）的Web浏览器的事件循环使用队列处理数据。现在暂停一下，想象一下我们作为用户和开发人员有多少次使用堆栈和队列。太棒了，对吧？由于它们在设计上的普遍性和相似性，我决定使用它们来向您介绍数据结构。堆栈在计算机科学中，堆栈是一种线性数据结构。如果这个陈述对你来说没有价值，就像最初对我一样，请考虑以下备选方案：堆栈按顺序组织数据。这种顺序通常被描述为自助餐厅中的一堆盘子。将板添加到堆栈时，板会保留它们添加的顺序；此外，当添加一个盘子时，它会被推向堆栈的底部。每次我们添加一个新盘子时，该盘子都会被推向堆栈的底部，但它也代表了盘子堆栈的顶部。使用板来表示堆栈添加板的过程将保留每个板添加到堆栈的顺序。从堆栈中取出盘子也将保留所有盘子的顺序。如果从堆叠顶部移除一个盘子，则堆叠中的每个其他盘子将以正确的顺序保留在堆叠中。我所描述的（可能用词太多）是大多数自助餐厅如何添加和移除盘子！为了提供堆栈的更多技术示例，让我们回顾一下文本编辑器的撤消操作。每次将文本添加到文本编辑器时，该文本都会被推入堆栈。文本编辑器的第一个添加代表堆栈的底部；最近的更改代表堆栈的顶部。如果用户想要撤消最近的更改，则堆栈的顶部将被删除。可以重复这个过程，直到堆栈中没有更多的添加，这就是一个空白文件！表示堆栈操作现在我们有了堆栈的概念模型，让我们在堆栈上定义两个操作：push(data)将数据添加到堆栈的顶部。pop()删除并返回最近添加的数据。在JavaScript中实现堆栈在我们开始之前，我应该提到JavaScript有一个很棒的堆栈（和队列）内置实现：Array类型。没错：每个JavaScript数组都有push()和pop()函数。因此，如果您想在生产代码中使用堆栈（或队列），只需使用常规的JavaScript数组即可。话虽如此，从头开始实现堆栈仍然是一个很好的学习练习！Stack的属性对于我们的实现，我们将创建一个名为Stack的实例。Stack的每个实例都有两个属性：_size和_storage。classStack{constructor(){this._size=0;this._storage={};}}this._storage使得每个Stack实例都有自己的容器来存储数据；this._size反映了数据推送到当前版本Stacks的数量。如果创建了一个新的Stack实例并将数据压入其存储，则this._size将增加到1。如果再次将数据压入堆栈，则this._size将增加到2。如果从堆栈中移除数据，this._size将减少到1。堆栈方法我们需要定义可以从堆栈中添加（压入）和删除（弹出）数据的方法。让我们从推送数据开始。向栈中推送数据push(data)我们对这个方法有两个要求：每次添加数据时，我们都希望增加栈的大小。每次添加数据时，我们都希望保留添加数据的顺序。//assignssizeasakeyofstorage//assignsdataasthevalueofthiskeythis._storage[this._size]=data;//增加我们存储的大小this._size++;}我们的push(data)实现包括以下逻辑。声明一个名为size的变量并将其分配给this._size++。给大小为的keythis._storage赋值，给data赋值对应key的值。如果我们的堆栈调用push(data)五次，那么我们的堆栈大小将为5。第一次推送到堆栈将在this._storage中为该数据分配一个键1。第五次调用push(data)将在this._storage中为该数据分配一个键5。我们刚刚为我们的数据分配了顺序！使用pop()从堆栈中弹出数据我们现在可以将数据压入堆栈；下一个合乎逻辑的步骤是从堆栈中弹出（删除）数据。从堆栈中弹出数据不只是删除数据；它只删除最近添加的数据。这是我们使用此方法的目标：使用堆栈的当前大小来获取最近添加的数据。删除最近添加的数据。将_this._size减一。返回最近删除的数据。如果堆栈为空，则返回null。pop(){if(this._size==0)returnnull;letdeletedData=this._storage[this._size-1];deletethis._storage[this._size-1];this._size--;returndeletedData;}pop()满足我们的五个目标中的每一个。首先，我们声明了两个变量：size被初始化为栈的大小，deletedData被赋值为最近加入栈的数据。其次，我们删除了最近添加的数据的键值对。第三，我们将栈的大小减1。第四，我们返回从栈中移除的数据。如果我们测试当前的pop()实现，我们会发现它适用于以下用例。如果我们push(data)将数据写入堆栈，则堆栈的大小将增加1。如果我们从堆栈中pop()数据，则堆栈的大小将减少一。pop()但是，如果我们在将任何数据添加到堆栈之前尝试使用push()，我们将得到null。使用JavaScriptArray作为堆栈即使我们在本文中从头开始实现堆栈，我们也不必每次都编写构建堆栈的逻辑。堆栈在JavaScript数组中实现。JavaScript提供了两种方法，push和pop，在数组中执行相同的操作。以下是如何使用JavaScript的内置堆栈：constnums=[5,8,1,4];nums.push(6);控制台日志（数字）；//[5,8,1,4,6]at在上面的例子中，nums是一个数字数组。6我们使用push方法进行推送。pop操作的用法也类似。您在数组上调用pop方法，它会删除数组的最后一个元素。constnums=[5,8,1,4];constnum=nums.pop();控制台日志（数量）；//4console.log(nums);//[5,8,1]fromstacktoQueues当我们想要按顺序添加数据和删除数据时，堆栈很有用。根据其定义，堆栈只能删除最近添加的数据。如果我们想删除最旧的数据会怎样？我们想使用一种称为队列的数据结构。和栈一样，队列也是一种线性数据结构。与堆栈不同，队列仅删除最早添加的数据。为了帮助您概念化这是如何工作的，让我们花点时间打个比方。想象一下与熟食店售票系统非常相似的队列。每个客户都会得到一张票，并在呼叫他们的号码时得到服务。应首先为拿第一张票的顾客服务。让我们再想象一下，这张票上显示的是数字“一”。下一张票显示数字“二”。拿第二张票的客户将获得第二项服务。（如果我们的票务系统像堆栈一样运行，第一个进入堆栈的顾客将是最后一个得到服务的！）真实世界队列的示例队列一个更现实的队列示例是Web浏览器的事件循环。当不同的事件被触发时，例如按钮点击，它们被添加到事件循环的队列中并按照它们排队的顺序进行处理。队列操作现在我们有了队列的概念模型，让我们定义它的操作。您会注意到队列的运行方式与堆栈非常相似。不同之处在于删除数据的位置。enqueue(data)将数据添加到队列中。dequeue()将最早添加的数据移除到队列中。在JavaScript中实现队列现在让我们编写队列代码！同样，JavaScript数组已经实现了这些队列操作，但我们将从头开始编写它们作为练习。队列属性对于我们的实现，我们将创建一个名为Queue的队列。然后我们将添加三个属性：_oldestIndex、_newestIndex和_storage。_oldestIndex和_newestIndex的必要性将在下一节中变得更加清晰。类队列{constructor(){this._oldestIndex=0;这个._newestIndex=0;这个._storage={};}}队列的方法我们现在将创建三个队列的所有实例共享的方法：size()、enqueue(data)和dequeue(data)。我将概述每种方法的目标，揭示每种方法的代码，然后解释每种方法的代码。获取队列的大小size()size(){returnthis._newestIndex-this._oldestIndex;实现size()可能看起来微不足道，但它可能有点棘手。让我解释一下原因：我们必须跟踪队列的开头和结尾。由于我们在一端添加并从另一端删除，队列的大小就是它们之间的差异。再次考虑熟食店的例子。当一位顾客进来并从票务系统取票时，队列的大小会增加一个。当工作人员调用工单时，队列的大小减一。在此示例中，客户最后拨打的号码对应于_newestIndex属性，员工最后拨打的号码对应于_oldestIndex属性。它们之间的区别在于仍在等待呼叫其号码的客户数量。将数据添加到队列enqueue(data)对于enqueue，我们有两个目标：将值添加到作为键this._storage的值。_newestIndex将_newestIndex的值增加一。基于这两个目标，我们将创建enqueue(data)的以下实现：enqueue(data){this._storage[this._newestIndex]=data;this._newestIndex++;}如您所见，这段代码正是我们需要。这就是我们需要的所有代码enqueue(data)。现在让我们实现dequeue()。从队列中删除数据dequeue()这个方法的目的是：删除队列中最早的数据。添加_oldestIndex一个。如果队列为空，则返回null。dequeue(){if(this._oldestIndex==this._newestIndex)returnnull;letdeletedData=this._storage[this._oldestIndex];deletethis._storage[this._oldestIndex];this._oldestIndex++;returndeletedData;}在体内在dequeue()中，我们声明了两个变量。第一个变量oldestIndex是分配队列的当前值this._oldestIndex。第二个变量deletedData被赋予包含在this._storage[oldestIndex]中的值。接下来，我们删除队列中最旧的索引。删除后，我们增加this._oldestIndex1。最后，我们返回刚刚删除的数据。当oldestIndex和newestIndex相等时，队列为空，我们返回null。使用内置方法的队列操作类似于内置的Stack实现，也可以通过一些JavaScript方法来使用队列。JavaScript提供了两种方法，shift和push。您可以将push()方法视为将提供的数据添加到数组末尾的入队操作。入队操作使用push()constnums=[5,8,1,4];nums.push(2,3);控制台日志（数字）；//[5,8,1,4,2,3]出队操作使用shift。shift()方法从索引位置0移除一个元素并返回该值，就像dequeue方法一样。实际上，它的shift()与pop()的工作原理相同，但它从数组的开头删除元素。constnums=[5,8,1,4];constnum=nums.shift();控制台日志（数量）；//5console.log(nums);//[8,1,4]尽管使用内置函数可以轻松地进行堆栈和队列操作，但了解这些数据结构背后的核心逻辑至关重要。它可以帮助您加强基础。这就是为什么从头开始显示实现的原因。结论在本文中，我们探索了两种线性数据结构：堆栈和队列。堆栈按顺序存储数据并删除最近添加的数据；队列按顺序存储数据，但删除最早添加的数据。如果这些数据结构的实现看起来微不足道，请提醒自己这些数据结构的用途。他们的设计并不过分复杂。它们旨在帮助我们组织数据。在这种情况下，如果您发现自己需要按顺序组织数据，请考虑使用堆栈或队列。
