简单数据结构

1. 栈

一种线性结构，遵循后进先出，只允许在一端进行数据添加和移除操作。

JavaScript 中使用数组能够很方便地实现该结构，实际上数组原生提供了 pop 和 push 方法来实现。

也可以简单封装如下：

class Stack {
  constructor() {
    this.data = [];
  }

  push(val) {
    this.data.push(val);
  }

  pop() {
    return this.data.pop();
  }

  peek() {
    if (this.isEmpty()) return null;
    return this.data[this.data.length - 1];
  }

  isEmpty() {
    return this.data.length === 0;
  }
}

2. 队列

队列和栈一样，是一种线性结构，它遵循先进先出的原则。

使用数组简单封装如下：

class Queue {
  constructor() {
    this.data = [];
  }

  add(item) {
    this.data.push(item);
  }

  delete() {
    return this.data.shift();
  }

  isEmpty() {
    return this.data.length === 0;
  }
}

3. 链表

与数组中靠物理内存把数据集存储在一起不同，链表是通过指针连接一个数据集，各元素散落在内存中。链表就是一系列节点的连接：

使用对象来模拟链表行为，其中元素节点包含当前值和下一个元素节点的指针：

class ListNode{
  constructor(val) {
    this.val = val
    this.next = null
  }
}

根据元素节点指针的类型，链表又分为单向链表、单向循环链表、双向循环链表。

• 单向链表
  • 所有元素节点都只有下一个元素的指针
• 单向循环链表
  • 单向链表中的尾元素的 next 指针指向头元素节点，构成循环
• 双向循环链表
  • 所有元素节点都有 next 和 pre 指针
  • 头元素和尾元素互相连接