JavaScript 数据结构：栈：简介

引言

在讲完双向链表系列之后，我们开始学习栈。

什么是栈？

• 采用“后进先出”原则
• 例如：一叠扑克牌、一堆碗碟、浏览器历史记录
• 实现栈的方法有很多种：数组、单链表、双向链表

堆栈的大O

• 使用权：O(N)
• 搜索：O(N)
• 插入：O(1)
• 删除：O(1)

例子

我们将使用单链表来构建我们的栈。

A <== B <== C (last)

• C是我们最后压入（即添加到）栈顶的节点。
• Cnext具有指向下一个节点的指针（B）
• 如果我们弹出（=移除）一个节点C，栈顶的下一个节点应该是B

设置

我们需要以下组件来构建我们的技术栈：

• 一个节点，包含一个值和一个指向栈中下一个元素的指针。
• 一个带有长度和指向最后一个元素的指针的栈

// a Node has a value (`value`) and a pointer to the next node (`next`)
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// a Stack has a length and a last item (`last`)
class Stack {
  constructor() {
    this.length = 0;
    this.last = null;
  }
}

想法

我们已经搭建好了栈。现在栈中至少需要包含两个方法：

• 将新节点压入栈顶的方法：push
• 一种从栈顶弹出最后一个节点的方法：pop

下一部分

我们将实现栈的第一个方法。

想要收到通知，请订阅！

问题

• 你能想到使用单链表而不是数组或双向链表的一些优点或缺点吗？