原文：Complete Introduction to the 30 Most Essential Data Structures & Algorithms
内容
数据结构
- 数组
- 链表
- 栈
- 队列
- map和哈希表
- 图
- 树
- 二叉树和二叉搜索树
- 自平衡树（AVL树，红黑树，splay树）
- 堆
- Tries
- Segment trees
- Fenwick trees
- Disjoint Set Union
-
算法
Divide和Conquer
- 排序算法(冒泡排序，计数排序，快速排序，合并排序，基数排序)
- 搜索算法(线性搜索，二维搜索)
- Sieve of Eratosthenes
- Knuth-Morris-Pratt
- 贪婪算法1（轴线上不重叠间隔的最大数目）
- 贪婪算法2（部分背包问题）
- 动态编程1
- 动态编程2
- 动态编程3
- 凸包
- 图遍历（深度优先，深度优先）
- Floyd-Warshall / Roy-Floyd Algorithm
- Dijkstra’s Algorithm & Bellman-Ford Algorithm
- 拓扑排序
数据结构
1、数组
数组是最简单和最常用的数据结构。他们的特点是通过索引（位置）方便的访问元素。
他们是用来做什么的？
想像一下，在剧院里有一排椅子。每一把椅子都被分配了一个位置（从左到右），所以每一个观众会拿着分配的数字做到对应的椅子上。这就是数组。把问题扩展到整个剧院（一排排和一列列的一直），你就得到了一个二维数组。
属性
- 元素的值是按照顺序排列的并且通过索引从0开始到数据的长度 -1 的长度进行访问。
- 一个数组是一个连续的内存块
- 通常是有同类型的元素组成（取决于编程语言）
-
有用的链接
- LeetCode Problem Set
- Top 40 problems on arrays
2、链表
链表是线性数据结构，和数组类似。数组和链表最大的不同是链表的元素没有存储在一个连续的内存空间。它有一个节点-实体组成，存储了当前元素的值和地址指针指向了下一个元素。元素通过指针相连。
它们是用来做什么的？
一个链表相关的应用就是浏览器页面的前进和后退。双向链表是完美的数据结构，用于存储用户查询的时候页面的显示记录。
属性
- 链表用三种类型：单项链表、双向链表和循环链表
- 元素并不是存储在一个连续的内存块
- 完美的适用于优秀的内存管理（使用指针意味着动态的内存使用）
-
有用的链接
-
3、栈(Stacks)
栈是一种抽象的数据类型，形式化了受限访问集合的概念。遵循了LIFO(后进先出)的限制规则。最后一个添加到栈里的元素会是第一个删除的元素。栈可以用数组或者链表实现。可用于做什么？
最贴近现实生活的例子是在餐厅里把碟子一个个的叠起来。叠在最上面的碟子是第一个被拿走的。最下面的碟子是在栈里面保留时间最长的。
栈最有用的一种情况就是要获取已知元素的倒序。仅仅把他们全部放进栈里然后一个个的(pop)拿出来就可以。
另一个有趣的应用就是合法的括号的问题。给一个括号字符串，用栈来检查他们是不是匹配。属性
一次只能访问最后一个元素（最顶部的那个元素）；
- 一个缺点就是一旦你为了访问其他元素，从顶部pop了第一个元素，他们的值就会在栈内存中丢失。
- 访问其他的元素是在线性时间内，其他的操作都是O(1)；
4、队列（queue）
队列是一种数据类型，也是受限的访问集合，与栈类似。最大的不同是队列的组织是先进先出的模型：第一个插入到队列的元素是第一个被删除的。队列可以用固定长度的数组实现，一个循环数组或者链表。
可用于做什么？
这种抽象数据类型最大的用处，就是现实中队列的模仿。例如，在一个呼叫中心应用中，一个队列是用于保存客户等待来自咨询者的帮助，并且按照他们呼叫的顺序。
一个非常特殊并且重要的队列类型就是优先队列。队列中插入的元素基于优先的原则：最高优先级的元素是是第一个放入队列的元素。这种抽象数据类型对于很多图算法是非常重要的。用堆来实现。
另一个特殊的堆类型就是双端队列(deque)。元素删除和添加是通过队列的两端。
属性
- 可以直接访问引入的’最老‘的元素
- 查询元素将会从队列内存中删除所有已访问过的元素
- pop或者push元素或者获取最前面的元素是常量时间。查询是线性的。
5、Map和哈希字典
若有收获，就点个赞吧
0 人点赞
