总结前端开发中常见的数据结构

栈 Stack

先进后出。

// 数组实现栈
const stack = [];
stack.push(8); // 压栈
stack.pop(); // 出栈
1
2
3
4

队列 Queue

先进先出。

// JS 中数组的 unshift shift 消耗挺大的
// 不是很建议使用，当在算法题中遇到的时候
const queue = [];
queue.push(6); // 入队尾
queue.shift(); // 队头出
1
2
3
4
5

链表 Linked List

不是连续的一段存储空间。

interface IListNode {
	data: any,
	next: IListNode | null
}
1
2
3
4

树 Tree

二叉搜索树的特点：
left 及其后代的 value <= root value;
right 及其后代的 value >= root value.

平衡二叉搜索树 BBST。

二叉树的三种遍历方式：

• 前序遍历：abc
• 中序遍历：bac
• 后序遍历：bca

递归实现这三种遍历。

interface IBinaryTreeNode {
	value: any,
	left: IBinaryTreeNode | null,
	right: IBinaryTreeNode | null
}
1
2
3
4
5

为什么二叉树重要，而不是三叉树四叉树呢？
性能！
数组：查找快O(1)，增删慢O(n)
链表：查找慢O(n)，增删快O(1)
二叉搜索树：查找快O(logn)，增删快O(logn)

堆和二叉树有什么关系

JS 代码执行时，值类型变量存储在栈，引用类型变量存储在堆。
堆是一个完全二叉树。
堆的子节点要么都小于根节点（最大堆），要么都大于根节点（最小堆）。
完全二叉树就是要么先把左节点先填满，要么先把右节点先填满。
满二叉树一定是完全二叉树。
堆，逻辑结构是二叉树，物理结构是一个数组。

算法问题两个解决思路

1. 选取合适的数据结构
2. 有序数据考虑用二分法
3. 双指针可以解决嵌套循环
4. 动态规划问题，不用递归来做，用循环来做，因为递归会有重复计算的问题，很影响性能。f(n)=f(n-1)+f(n-2)。比如 fibonacci 斐波那契数列问题，青蛙跳台阶有多少种方式的问题。