数据结构

栈

概念

栈：栈是一种后进先出的数据结构。可以把栈的数据结构想象成底端封住的羽毛球桶，拿或是放都是通过桶顶（栈顶），后放进的，到使用的时候先出。

代码

// 创建一个用于存储 string | number 的栈
class Stack {
  private stack: (number | string)[] = [];
  private count: number = 0;
  push(item: number | string) {
    this.stack[this.count++] = item;
    return item;
  }
  pop() {
    if (this.isEmpty()) return;
    const delEl = this.stack[this.count - 1];
    delete this.stack[--this.count];
    return delEl;
  }
  isEmpty() {
    return this.count === 0;
  }
  top() {
    return this.stack[this.count - 1];
  }
  size() {
    return this.count;
  }
  clear() {
    this.stack = []
    this.count = 0
  }
}

LeetCode 应用

155 min栈
739 每日温度

队列

单端队列

概念

队列：队列是一种先进先出有序集合。可以把其想象为 排队作核酸（队尾入队），先排的肯定是先做完（收首出队）。

代码

// 队列，先进先出的数据结构
// 对象实现
interface typeQueque {
  [prop: number]: string | number;
}
class Queque {
  queque: typeQueque = {};
  end = 0;
  start = 0;

  enQueque(item: number | string) {
    this.queque[this.end++] = item;
  }
  deQueque() {
    if (this.isEmpty()) return;
    const departEl = this.queque[this.start];
    delete this.queque[this.start++];
    return departEl;
  }
  isEmpty() {
    return this.size() === 0;
  }
  size() {
    return this.end - this.start;
  }
  top() {
    return this.queque[this.start];
  }
  clear() {
    this.queque = {};
    this.end = 0;
    this.start = 0;
  }
}

双端队列

概念：

双端队列：双端队列是只可以在队尾队首都进行存取操做。

代码：

// 双端队列： 队首队尾都可以进行存取操作
interface typeQue {
  [prop: number]: number | string;
}
class dbQueque {
  queque: typeQue = {};
  start = 0;
  end = 0;
  enEndQue(item: number | string) {
    this.queque[this.end++] = item;
  }
  deStartQue() {
    if (this.isEmpty()) return;
    const res = this.queque[this.start];
    delete this.queque[this.start++];
    return res;
  }

  enStartQue(item: number | string) {
    this.queque[--this.start] = item;
  }
  deEndQueque() {
    if (this.isEmpty()) return;
    const res = this.queque[this.end - 1];
    delete this.queque[--this.end];
    return res;
  }
  isEmpty() {
    return this.size() === 0;
  }
  size() {
    return this.end - this.start;
  }
  clear() {
    this.queque = {};
    this.start = 0;
    this.end = 0;
  }
  topEl() {
    return this.queque[this.start];
  }
  endEl() {
    return this.queque[this.end - 1];
  }
}

LeetCode

59 队列中的最大值

链表

概念

链表是一种有序的数据结构，它可以从首尾和中间进行存取操作，链表的每一个部分称为节点。

从概念上看来链表与数组很相似，相似但不相同，他们的差异如下：

• 数组因为要维护索引与值的关系，在内存中存储空间是连续的，而链表在内存存储空间不是连续的
• 数组进行添加和删除操作（头部或中间添加删除时，后面元素在内存中存储位置需要变动）性能不如链表，链表进行添加删除操作位置不需要进行位移
• 与数组相比链表无法通过索引快速获取元素

普通链表

根据双向链表的特性，普通链表又称为 单向或是单端链表，节点与节点的关系由 next 属性进行维系，从头 head部节点开始调用 next 属性获取下一个节点，这样依此类推最终到 next 为 null为链表结束
这些由 next 属性维系节点与节点关系的链表称为普通链表

// 链表
class LinkedNode {
  value: unknown;
  next: LinkedNode | null;
  constructor(value: unknown) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  count: number; // 记录链表存储节点的长度
  head: LinkedNode | null; // 记录链表的头部节点

  constructor() {
    this.count = 0;
    this.head = null;
  }
  // 添加节点(尾部)
  addAtTail(value: unknown) {
    // 根据 value 创建 节点
    const node = new LinkedNode(value);
    if (this.count === 0) {
      this.head = node;
    } else {
      // 找到链表的尾部节点，让尾部节点的 next 属性跟 新添加的节点做关联
      let cur = this.head;
      while (cur!.next !== null) {
        cur = cur!.next as LinkedNode;
      }
      cur!.next = node;
    }
    this.count++;
  }
  // 从头部添加
  addAtHead(value: unknown) {
    const node = new LinkedNode(value);
    if (this.count === 0) {
      this.head = node;
    } else {
      node.next = this.head;
      this.head = node;
    }
    this.count++;
  }

  // 根据索引获取指定节点
  get(index: number): void | LinkedNode {
    if (this.count === 0 || index >= this.count) {
      return;
    }

    // 设定： 如果小于 0 返回头部节点
    if (index < 0) {
      return this.head as LinkedNode;
    }

    // 取指定节点
    let cur = this.head;

    // i < index, 因为 n 此循环结束，通过 next 属性可以取到下一个节点
    for (let i = 0; i < index; i++) {
      cur = cur!.next;
    }

    return cur as LinkedNode;
  }

  // 往指定位置进行添加
  addByIdx(index: number, value: unknown) {
    if (this.count === 0 || index <= 0) {
      this.addAtHead(value);
      return;
    } else if (index >= this.count) {
      this.addAtTail(value);
      return;
    }
    const node = new LinkedNode(value);
    const prev = this.get(index - 1) as LinkedNode;
    const next = prev.next;
    prev.next = node;
    node.next = next;
    this.count++;
  }

  // 根据 idx 删除指定节点
  removeByIdx(index: number) {
    if (this.count === 0 || index < 0 || index >= this.count) {
      return;
    } else if (index === 0) {
      this.head = null;
      this.count--;
      return;
    }

    // index >= 1
    const prev = this.get(index - 1) as LinkedNode;
    const next = prev!.next?.next;

    prev.next = next || null;
    this.count--;
  }
}

双向链表

相比于普通链表，双向链表节点与节点的关系由 prev 与 next 来维系，节点的 prev 用于获取上一个节点，一直链式调用到头部为 null，节点的 next 用于获取下一个节点，一直链式调用到尾部 null，这些节点构成双向链表

由 prev 与 next 进行维系节点关系的链表称为双向链表

循环链表

循环链表又称为环形链表，链表的尾部的 next 属性指向链表的头部或是链表的除尾部节点的其他节点，这样就可以一直链式调用 next 属性，会产生循环，这种链表称为循环链表

leetcode 环路检测

树

树数据结构需要了解的概念：

• 非线性数据结构
• 树中的每个部分称为结点，结点存在分支结构与层次关系
• 每个树都存在一个根结点，根结点也是父节点
• 根据结点的关系，会存在父子，兄弟 结点 的概念
• 叶子结点意思是没有子结点
• 子树是对某个结点和其后代结点的称呼
• 树中存在层级关系，其中根结点为层级 1 ，后续依此递增
• 树的高度 = 层级的最深处

二叉树

二叉树为树形结构的一种，其特殊性在于每个结点最多只能存在 2 个子结点。如上图： 就是一个二叉树的树形结构

满二叉树

满二叉树为二叉树树形结构的一种，其特点是：除了最后一层的结点以外，其他结点的子节点都达到最大值拥有 2 个子节点

完全二叉树

满二叉树属于完全二叉树
除了最后一层的结点以外，每层结点都达到最大值，且最后一层的结点位于左侧，如图

分治

堆

堆他是一种特殊的完全二叉树

堆的类型

堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
最大堆：所有的子节点都小于等于自己的根节点
最小堆：所有的子节点都大于等于自己的根节点

堆的应用

这种数据格式的好处是 可以在 O1 的时间复杂度中找到最大或是最小值(取决于堆的类型)

堆的代码
小顶堆

 class MinHeap {
  constructor() {
    this.heap = []
  }

  getParentIdx(idx) {
    /*
      根据 完全二叉树图得 当前元素的根节点应该是 (索引 - 1) / 2 的 整数部分
      求除 2 的整数可以用 >> 1
      求除 4 的整数可以用 >> 2
    */
    return (idx - 1) >> 1
  }
  // 求当前节点的左子节点
  getLeftIdx(idx) {
    return idx * 2 + 1
  }

  // 求当前节点的右子节点
  getRightIdx(idx) {
    return idx * 2 + 2
  }

  // 交换值
  swap(parentIdx, curIdx) {
    const temp = this.heap[parentIdx]
    this.heap[parentIdx] = this.heap[curIdx]
    this.heap[curIdx] = temp
  }

  shiftDown(idx) {
    const leftIdx = this.getLeftIdx(idx)
    const rightIdx = this.getRightIdx(idx)



    if (this.heap[idx] > this.heap[leftIdx]) {
      this.swap(idx, leftIdx)
      this.shiftDown(leftIdx)
    }

    if (this.heap[idx] > this.heap[rightIdx]) {
      this.swap(idx, rightIdx)
      this.shiftDown(rightIdx)
    }

  }

  shiftUp(idx) {
    // 第一个存入的元素不用作处理
    if (idx === 0) return

    const parentIdx = this.getParentIdx(idx)
    const parentVal = this.heap[parentIdx]
    const curVal = this.heap[idx]

    // 因是 最小堆，所以子节点要大于其父节点, 如果当前子节点小于了 父节点要交换位置
    if (curVal < parentVal) {
      this.swap(parentIdx, idx)
      // 交换之后尝试继续进行上移，递归一直到符合最小堆的要求
      this.shiftUp(parentIdx)
    }
  }

  // 插入节点
  insert(value) {
    this.heap.push(value)
    // 插入的元素需要符合最小堆的结构
    this.shiftUp(this.heap.length - 1)
  }

  // 堆的删除节点，其实是删除 根节点
  pop() {
    this.heap[0] = this.heap.pop()
    // 需要下移节点
    this.shiftDown(0)
  }

  // 获取堆顶

  peek() {
    return this.heap[0]
  }

  // 获取堆的存储数据长度
  size() {
    return this.heap.length
  }

}

const h = new MinHeap();

大顶堆
差异点只在这里