共计 3243 个字符，预计需要花费 9 分钟才能阅读完成。
为什么要学习数据结构
1. 语言是相通的
人们常说，编程语言是相通的，掌握一门，其他语言很容易就能掌握。
个人认为这是一个似是而非的观点，每门编程语言都离不开变量，数组，循环，条件判断这些概念，这似乎能支持上面的观点，但是每门编程语言都有自己的使用范围，都有自己擅长的事情，即便是有了 node.js 这中能够一统前后端的语言，也总有他不能胜任的工作，比如机器学习。像 python 这样近乎万能的语言，也会在高性能计算的时候无能为力。
其实，真正想通的不是语言，而是数据结构与算法。数据结构和算法是脱离编程语言而存在的，不同的语言有不同的实现版本，但是内在逻辑却不会发生变化，所提现的编程思想不会有变化
2. 业务场景
a、前端通过 websocket 获取数据，数据是具体的坐标，当获取到坐标的时候，在前端的地图上显示一个光圈。但是，后端不定期发送，可能一次推送几个，也可能几秒钟才推送一个，当数据特别频繁的时候，坐标都在地图上显示，地图会非常乱，所以对于前端来说要做一个限制，前端同一个时刻最多显示 10 个坐标，新坐标需要把最早的坐标挤掉，每个坐标最多显示 5 秒钟。
是否可以通过队列的方式，每一个节点都包括，后台传过来的数据坐标和当前的时间，当超过 10 个坐标的时候，挤掉头部出队列，前端做事件循环每一秒钟，检查一下头部是否超过 5s，如果超过，头部出队列。
b、H5 页面翻页场景业务，
可以添加页面，删除页面，移动页面，翻看页面。我猜想大多数情况应该是对数组进行操作，通过 arr, 角标 index 和 for 循环来渲染页面的.
换个思路：
是否可以用双向链表的方式完成这些操作，每一个页节点，包括本页的数据，pre 前一页的指向和 next 后一页的指向，当添加操作的时候其实是在尾节点 next 指向新页，删除页面的时候其实是把前一页的 next 指向删除页的 next，移动页面其实就是先完成删除页面，在完成添加页面操作，向后翻看页面的时候，就是一直在操作 next，向前翻看其实就是一直操作 pre。
不考虑分页情况，如果存在分页情况，也可以后端只保存一条数据，在存入的时候先读取数据在 update 数据(这样会增加服务器压力)
3. 学习数据结构的目标
a) 提高程序设计能力
b) 提高算法能力，数据结构的精髓在于总结提炼了许多储存管理和使用数据的模式，这些模式的背后是最精华的编程思想，这些思想的领悟会需要一些时间，不是学习了几种数据结构就能在工作中大展伸手，但是学会了数据结构，对自身能力的提升是很有帮助的
在没有完全参悟这些编程思想和管理方式的时候，我们只需要学习具体的工具和方法。
4. 数据结构和算法都有哪些
栈 — 羽毛球、羊肉串
队列 — 排队登机，优先队列 — vip 用户、军人、老人、排队优先进入
链表 — 猴子捞月，包括单向链表、双向链表
集合 — es6 中的 Set
字典 — es6 中的 Map
散列集 — 曾经讨论过，因为数组的长度不固定，角标用哈希表示、循环尽量采取 foreach 自动过滤调 empty 的位置输出
图 — 迷宫 : 深度搜索和广度搜索，这个请参考 https://segmentfault.com/a/11…
树 — 学习小组讨论过一个问题，可以用二叉树来解决
假设你正在爬楼梯。需要 n 阶你才能到达楼顶
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：输入：2
输出：2
解释：有两种方法可以爬到楼顶。1. 1 阶 + 1 阶
2. 2 阶
示例 2：输入：3
输出：3
解释：有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶function Node(data) {
// 二叉树节点
this.data = data;
this.left = null;
this.right = null;
}
function method(n) {let head = new Node(null);
let num = 0;
function A(node, n, num) {if (n < node.data) {return 0;} else if (n - node.data == 0) {return 1;}
n -= node.data;
if (n == 1) {node.left = new Node(1);
return num + A(node.left, n);
} else if (n >= 2) {node.left = new Node(1);
node.right = new Node(2);
return num + A(node.left, n, num) + A(node.right, n, num);
}
}
if (n == 1) {head.left = new Node(1);
return A(head.left, n, num);
} else if (n >= 2) {head.left = new Node(1);
head.right = new Node(2);
return A(head.left, n, num) + A(head.right, n, num);
}
}这样在打印 head 的情况下，会把所有方式的轨迹都打印出来，如果不考虑轨迹路径，建议使用斐波那契数列
b) 冒泡排序、选择排序、插入排序、归并排序、快速排序、顺序搜索、二分搜索
5、学习数据结构需要知道哪些知识
a) 数组
b) Class 定义类的方法
数据结构之栈
1、栈的定义
栈是一种特殊的线性表，仅能够在栈顶进行操作，有着先进后出 (后进先出) 的特性，下面展示了栈的工作特点
2. 栈的实现
从数据储存的角度看，实现栈可以用数组来实现，注意：仅可以用数组实现吗？a、栈的几个方法：*push 添加一个元素到栈顶
*pop 弹出栈顶元素
*top 返回栈顶元素
*isEmpty 判断栈是否为空
*size 返回栈里元素的个数
*clear 清空栈3、代码实现
// push pop top isEmpty size clear 用数组完成
function Stack() {var items = [];
var min = null;
// 添加一个元素到栈顶
this.push = function(item) {items.push(item);
};
// 弹出栈顶元素
this.pop = function() {return items.pop();
};
// 返回栈顶元素，不弹出
this.top = function() {return items[items.length - 1];
};
// 判断栈是否为空
this.isEmpty = function() {return items.length == 0;};
// 返回栈里元素的个数
this.size = function() {return items.length;};
// 清空栈, 不推荐使用 items.length = 0，学术派讨论，// 说法一，赋值更快，length 为 0 影响其他已用，内存
this.clear = function() {items = [];
};
}
4、练习题
判断(abc),)(bcd),(ab(cd)), 括号是否合法
例如：(abc) 合理
(bcd)(不合理)() 不合理 /**
* 栈，队列其实就是 (数组或) 操作成，只不过角度不同
* 1. 判断(abc),)(bcd),(ab(cd)), 是否合法
* 解析，用栈解决
* a. 遇到左括号，就把做括号入栈
* b. 遇到右括号，判断栈是否为空，为空说明没有左括号与之对应，不合法，* 如果栈不为空，则把栈顶元素移除，与右括号抵消，继续执行
* c.for 循环结束，如果栈为空，就说明括号相互抵消，* 如果栈不为空，说明不合法
*/
function check(str) {
let len = str.length;
let stack = new Stack();
for (let i = 0; i < len; i++) {if (str[i] == '(') {stack.push('(');
} else if (str[i] == ')') {if (stack.isEmpty()) {return false;} else {stack.pop();
}
}
}
return stack.isEmpty();}赠言: 每当你怀疑学习数据结构的必要性和作用时，如果你手里只有锤子，那么目光所及之处都是钉子
作者：易企秀——王明
