栈(Stack) 是一种遵循 先进后出(LIFO) 的原则的有序集合。 新添加的或待删除的元素都保存在站的末尾,称为栈顶,另一端就叫栈底。 在栈里,新元素都靠近栈顶,旧元素都接近栈底。
比如:一摞书、或者餐厅里的盘子。
队列(Queue) 是一种遵循 后进先出(FIFO) 原则的有序的项。 队列在尾部添加新元素,并从顶部移除元素,最新添加的元素必须排在队列的尾部。
比如:餐厅里的排队取餐。
链表(LinkedList) 储存有序的元素集合,每个元素都有一个储蓄元素本身的节点和一个指向下一个元素的引用(也称为指针或者链接)组成。
比如:寻宝游戏或者火车的一系列车厢。
例子:
// {element: 'A', next:{element: 'B', next:{..}}}
A=>B=>C
// 在 A 和 B 之间插入 E
A=>E=>B=>C
// 删除 E
A=>B=>C
链表是双向的,一个元素链向下一个元素同时也链向上一个元素。
每个元素不仅链向下一个元素和上一个元素,而且头部和尾部的元素也相连,形成一个闭环。
head.prev = tail.next
集合是由一组无序且唯一(即不能重复)的项组成的。这个数据结构使用了有限集合相同的数学概念,在数学中,集合是一组不同的对象(的集) 你可以把集合想象成一组没有重复元素,也没有顺序的数组(其实在JS中就是对象,ES6中的Set数据结构就是是集合的实现)。 集合的一些操作:
集合是由一组无序且唯一(即不能重复)的项组成的。你也可以把集合想象成一个即没有重复元素,也没有顺序的的数组。 在 JavaScript 中就是对象,以为对象不能有两个相同的键。 EACAScript 6 中的 Set 数据结构就是集合的一种实现,它类似数组,但是成员都是唯一的。
字典和集合很相像,集合是以[值, 值]的形式储存的。字典则是以[键, 值]的形式来储存元素的,字典也称为 “映射” 字典储存的是[键, 值]对,其中键名是用来查询特定元素的。 EACAScript 6 中的 Map 数据结构就是字典的一种实现,它类似对象。
let djb2HashCode = function(key){
let hash = 5371;
for(let i = 0; i< key.length; i++){
hash = hash * 33 + key.charCodeAt(i)
}
return hash % 1013
}
树是一种非顺序数据结构,它对于储存需要快速查找的数据非常有用。 树是一种分层的抽象模型,如:家谱,公司组织架构图等。
每个树都有一个根节点以及多个子节点构成,节点分为内节点和外节点,至少有一个节点的的节点被称为内部节点,没有子元素的节点被称为外部节点。 树的高度,取决于所有节点深度的最大值。
假如在保证“左子树一定先于右子树遍历”这个前提
图是一种非线性数据结构。图是一种网络抽象模型,它是一组由边连接的节点(或顶点),任何二元关系都可以用图来表示。
参考