通过JavaScript探索堆栈和队列

以你之姓@ 2022-11-27 04:27 158阅读 0赞

Very often, a fully decked-out [doubly linked list][] may just be overkill for what you’re trying to achieve. In this article, we’re going to explore two extremely common minimalist variations to linked lists: stacks and queues.

通常，完全套叠的[双链表][doubly linked list]可能对您要实现的目标来说是过大的。 在本文中，我们将探讨链表的两个极为常见的极简主义变体： stacks和queues 。

Stacks and queues are opposite methods of treating incoming data, particularly when they need to be removed in a particular order. They are generally considered less as data structures and more as abstract data types, meaning they represent a particular usage rather than an exact structure. So they are more of a pattern that is implementable in many different ways with other data structures like arrays, linked lists, and even trees.

堆栈和队列是处理传入数据的相反方法，尤其是在需要按特定顺序删除它们时。 通常，它们不被视为数据结构，而被视为抽象数据类型，这意味着它们代表特定的用法，而不是确切的结构。 因此，它们更像是一种模式，可以与数组，链表甚至树之类的其他数据结构以多种方式实现。

## 先决条件 **(**Prerequisites**)** ##

Having a basic understanding of linked lists is essential for understand the list implementations, which you can get an overview on [here][].

对链接列表有基本的了解对于理解列表的实现至关重要，您可以在[此处][here]获得概述。

While not necessary for understanding stacks and queues, you should already have a grip on the essentials of Big O Notation, which I wrote a [short intro for here][].

尽管对于理解堆栈和队列不是必需的，但是您应该已经掌握了Big O Notation的要点，我[在这里为][short intro for here]它写了一个[简短的介绍][short intro for here] 。

## 堆栈 **(**Stacks**)** ##

Stacks are considered a LIFO structure, meaning last in first out. We add items to our stack and if some other condition is met, like a timer ran out or a task was completed, the most recently added item is the first to be removed and is the only one that we can interact with. I like to visualize this as washing and drying a stack of plates, as you add to the top of the stack you are restricted to only working with the topmost plate before you have access to the rest.

堆栈被认为是LIFO结构，意味着后进 先出 。 我们将项目添加到堆栈中，如果满足其他一些条件(例如计时器用完或任务已完成)，则最近添加的项目是第一个要删除的项目，并且是唯一可以与之交互的项目。 我喜欢将其可视化为洗涤和干燥一叠印版，当您将其添加到堆叠的顶部时，只能使用最上面的印版，然后再使用其余印版。

You’ve already been using stacks a lot, like with the recursion call stack or the standard JavaScript call stack when you make asynchronous requests. The need to strictly control the order of operations in this way is extremely common and will even help us in some less intuitive ways like traversing trees and ranking search results.

您已经使用了很多堆栈，例如在进行异步请求时使用递归调用堆栈或标准JavaScript调用堆栈。 以这种方式严格控制操作顺序的需求非常普遍，甚至会以一些不太直观的方式(例如遍历树和对搜索结果进行排名)帮助我们。

The most basic version of this would just be with a simple array. Stacks with an array implementation is only `O(1)`, same as with a linked list since we’re only manipulating the tail and nothing needs to be re-indexed. We can just use our normal `push` and `pop` methods to get this done. As long as we only used these two functions to interact with our data we would technically have a functional stack, even if a bit lackluster.

最基本的版本就是一个简单的数组。 具有数组实现的堆栈只有`O(1)` ，与链表相同，因为我们只操作尾部，不需要重新编制索引。 我们可以使用常规的`push`和`pop`方法来完成此操作。 只要我们仅使用这两个函数来与我们的数据进行交互，就技术上而言，即使有些乏味，我们也会拥有一个功能栈。

const stack = [];
    
    const add = val => stack.push(val);
    const remove = () => stack.pop();
    
    add('one');
    add('two');
    add('three');
    remove();
    console.log(stack); // ["one", "two"]

Linked lists are a bit more complicated, we have our normal nodes with only the one pointer and some `add` and `remove` methods. If there’s nothing in the list set it as the head and tail or null, else change the pointer on the item before it. It doesn’t matter if we’re adding/removing on the head or tail, as long as that’s the only one we’re interacting with.

链接列表稍微复杂一点，我们的普通节点只有一个指针以及一些`add`和`remove`方法。 如果列表中没有任何内容，则将其设置为head和tail或为null，否则更改其前面的指针。 只要在头或尾上进行添加/移除，都没有关系，只要这是我们与之交互的唯一对象即可。

This method would be preferred if you were hooked up to a database that contained a lot of nodes. Since arrays are loaded in at a fixed size, linked lists would be better to load-in only necessary chunks of data.

如果您连接到包含许多节点的数据库，则首选此方法。 由于数组以固定大小加载，因此链表最好只加载必要的数据块。

class Node {
      constructor(val) {
        this.val = val;
        this.next = null;
      }
    };
    
    class Stack {
      constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
      }
      add(val) {
        const newNode = new Node(val);
    
        if (!this.head) {
          this.head = newNode;
          this.tail = newNode;
        } else {
          const temp = this.head;
          this.head = newNode;
          this.head.next = temp;
        };
    
        this.length++;
        return this;
      }
      remove() {
        if (!this.head) return null;
    
        let temp = this.head;
        this.head = this.head.next;
    
        this.length--;
        return temp.val;
      }
    };
    
    let stack = new Stack()
    stack.add('one')
    stack.add('two')
    stack.add('three')
    stack.remove()
    console.log(stack) // two -> one

## Queue列 **(**Queues**)** ##

Queues are the reverse of stacks with a FIFO structure, meaning first in first out. This is exactly like standing in line, you showed up first so you get to go first.

队列是具有FIFO结构堆叠的逆过程， 在第一出第一意思。 这就像排队一样，您首先出现，所以您可以先走。

Likewise we can still do an array implementation, but this time it’s different. Since we’re working from the beginning when we remove something, every removal means our computer needs to loop through the rest of the array and re-index everything, giving us `O(n)`.

同样，我们仍然可以执行数组实现，但是这次有所不同。 由于我们从删除某项内容开始就开始工作，因此每次删除均意味着我们的计算机需要遍历数组的其余部分并重新索引所有内容，从而给我们`O(n)` 。

const queue = [];
    
    const add = val => queue.push(val);
    const remove = () => queue.shift();
    
    add('one');
    add('two');
    add('three');
    remove();
    console.log(queue); // ["two", "three"]

In this case linked lists are almost always superior for dealing with larger amounts of data since it avoids the re-indexing problem.

在这种情况下，链表几乎总是在处理大量数据方面具有优越性，因为它避免了重新编制索引的问题。

It doesn’t matter which end we add to as long as we remove from the other, in this case we’ll add to the tail and remove the head.

只要我们从另一端移除，添加到哪一端都没有关系，在这种情况下，我们将添加到尾部并移除头。

class Queue {
      constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
      }
      enqueue(val) {
        const newNode = new Node(val);
    
        if (!this.head) {
          this.head = newNode;
          this.tail = newNode;
        } else {
          this.tail.next = newNode;
          this.tail = newNode;
        };
    
        this.length++;
        return this;
      }
      dequeue() {
        if (!this.head) return null;
        if (this.head === this.tail) this.last = null;
        let temp = this.head;
        this.head = this.head.next;
    
        this.length--;
        return temp.val;
      }
    }
    
    let queue = new Queue();
    queue.enqueue('one');
    queue.enqueue('two');
    queue.enqueue('three');
    queue.dequeue();
    console.log(queue); // two -> three

## 总结思想 **(**Closing Thoughts**)** ##

This may seem like making splitting hairs from our normal linked lists and arrays, but as we progress to increasingly sophisticated structures, stacks and queues will become an essential component to how we structure and traverse data.

这看起来像是从正常的链表和数组中分裂头发，但是随着我们逐步发展出越来越复杂的结构，堆栈和队列将成为我们构造和遍历数据的重要组成部分。

> 翻译自: [https://www.digitalocean.com/community/tutorials/js-stacks-queues][https_www.digitalocean.com_community_tutorials_js-stacks-queues]

[doubly linked list]: https://www.digitalocean.com/community/tutorials/js-linked-lists-implementation
[here]: https://www.digitalocean.com/community/tutorials/js-linked-lists-overview
[short intro for here]: https://www.digitalocean.com/community/tutorials/js-big-o-notation
[https_www.digitalocean.com_community_tutorials_js-stacks-queues]: https://www.digitalocean.com/community/tutorials/js-stacks-queues