# JS_DataStructure

**Repository Path**: tongyaozhang/js_-data-structure

## Basic Information

- **Project Name**: JS_DataStructure
- **Description**: JavaScript 版数据结构
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2021-03-18
- **Last Updated**: 2021-03-21

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

### JavaScript 版数据结构复习

#### 1、栈

封装方法：push()、pop()、peak()、isEmpty()、size()

应用场景：十进制转二进制、函数调用堆栈

相关题目：有效的括号（LeetCode20）、二叉树的迭代遍历（LeetCode144）

#### 2、队列

封装方法：enqueue()、dequeue()、front()、isEmpty()、size()

应用场景：食堂排队打饭、JS 异步中的任务队列

相关题目：最近的请求次数（LeetCode933）、新版击鼓传花

**扩展：优先级队列**

插入元素的时候考虑数据的优先级，其他处理方式和基本队列一样

#### 3、链表

相对于数组的优点

+ 内存空间不是必须连续的。可以充分利用计算机的内存，实现灵活的内存动态管理
+ 链表不必在创建时就确定大小，并且大小可以无限的延伸下去
+ 链表在插入和删除数据时，时间复杂度可以达到O(1)，相对数组效率高很多

相对于数组的缺点

+ 链表无法跳过一个元素访问任何一个元素，无法通过下标直接访问元素，只能从头一个个访问

封装方法：append()、insert()、get()、indexOf()、update()、removeAt()、isEmpty()、size()、toString()

应用场景：JS 中的原型链、使用链表指针获取 JSON 的节点值

相关题目：删除链表中的节点（LeetCode237）、反转链表（LeetCode206）、两数相加（LeetCode2）、删除排序链表中的重复元素（LeetCode83）、环形链表（LeetCode141）

**扩展：双向链表**

优点：更方便查找

缺点：处理四个引用更麻烦、占用内存空间更大

封装方法：append()、toString()、insert()

#### 4、集合

直接使用 ES6 中的 Set

相关题目：两个数组的交集（LeetCode349）

#### 5、字典

直接使用 ES6 中的 Map

相关题目：两个数组的交集（LeetCode349）、有效的括号（LeetCode20）、两数之和（LeetCode1）、无重复字符的最长子串（LeetCode3）、最小覆盖子串（LeetCode76）