翻译—The top data structures you s
Niklaus Wirth，一个瑞士的计算机科学家，写下过一个公式：算法+数据结构=程序
四十多年后，这个公式仍然成立。这就是软件工程师的候选人必须结合他们的应用展示出他们对数据结构的理解。
无论你是刚毕业或者你有几十年的工作经验。大多数的问题需要你展示出他们对数据结构深层的了解。
有时候面试会明确提及数据结构，例如"给定一个二进制数"。其他时候也会隐约提到的，"我们想要记录每个作者出的书的数量"。
数据结构是什么呢？
简单的说，数据结构是以特定格式存储数据的一个容器。这个"格式"使得数据结构在某些场景下是很高效的，在另一些场景下是低效的。而你的目的是去了解数据结构并可以选择用哪一种数据机构最适合解决手头的问题。
我们为什么需要数据机构呢？
因为数据结构是以有组织的形式存储数据的，在计算机科学中数据是很重要的实体，数据结构的特点是很显然的。
无论你正在解决什么问题，它都会以某种方式要求你处理数据。—例如雇佣者的薪水，股票价格，购物清单或者很简单的电话簿。
都是基于不同的形式，数据也需要以特定格式存储。我们有很多数据结构，我们可以根据不同的格式来选择存储结构。
基本数据结构有哪些呢？
1.数组
2.栈
3.队列
4.列表
5.树
6.图表
7.字典树(很高效的树，把它独立分出来比较好)
8.哈希表
数组
数组是最简单的也是使用最广泛的数据结构。其他一些像栈和队列都起源于数组。
下面是简单的4个长度的数组，包含元素1，2，3，4.
每个元素由一个确切的数字去标记，我们把它叫做"索引"，也就是说，这个数字是这个元素对应于该数组的位置。大多数语言定义索引的起始位置从0开始。
数组由2中类型：
· 一维数组(也就是上面的图片展示的)
· 二维数组(一维数组里面又存放着一维数组)
数组中的基本操作
· Insert—在指定索引处插入一个元素
· Get—返回指定索引的元素
· Delete—删除指定索引的元素
· Size—获取数组的大小
最经常会被问到的面试题
· 找出数组中倒数第二小的元素
· 找出数组中的不重复的整数
· 合并两个排序的数组
· 重新排列数组中的正负值
栈
我们都知道"撤销"选项，几乎每个应用都有。你曾经有想知道它是怎么做的吗？这里有个主意：你可以存储之前你的应用状态(限制一下存储多少次之前版本)在内存中按照顺序排列，最后一次版本放在第一个内存上。这个通过数组做不了，这就是栈派上的用场。
现实生活中栈的例子是一堆书竖摞起来。为了拿到排在中间的书，你需要把它上面的书都放到一边。这就是"后进先出"。
下面有一个栈的图片：
栈的基本操作
· Push—在顶部插入一个元素
· Pop—移除栈顶元素并返回
· isEmpty—返回栈中是否为空
· Top—不移除栈顶元素并返回
最经常被问到的面试题
· 使用堆栈评估前缀表达式
· 给一个栈排序
· 检查表达式中的括号是否平衡对应
队列
和栈类似，队列是另一种线性数据结构用有序方式存储数据。栈和队列唯一的不同就是它使用"先进先出"原则。
现实生活中有个极佳的例子：一排人在售票厅等候。如果新来了一个人，他必须排在队伍的最后面，而不是最前面。站在最前面的人拿到票因此会最先离开。
下面是队列的图：
队列的基本操作
· Enqueue()—在队尾插入一个新元素
· Dequeue()—从队首删除一个元素
· IsEmpty()—返回这个队列是否为空
· Top()—返回队列的第一个元素
最经常会被问到的关于队列的面试题
· 使用队列来实现栈操作
· 反转队列中的前k个元素
· 使用队列生成从1到n的二进制数
链表
链表也是一个重要的线性数据结构，可能第一眼看着和数组差不多，但其实是不同的。比如在内存分配上，内部结构和插入和删除的基本操作都是不同的。
一个链表就像节点链，每个节点都包含数据和指向后续节点的指针。有一个头指针，它指向链表的第一个元素，如果列表是空的，那么它只是指向null或什么都没有。
链表被用来实现文件系统，hash表和邻接表。
下面是内部示例图：
链表的结构类型有单链表和双链表
链表的基本操作
· InsertAtEnd—在链表的尾部插入给定元素
· InsertAtHead—在链表的头部插入给定元素
· Delete—从链表尾部中删除指定元素
· DeleteAtHead—删除链表头部第一个元素
· Search—返回给定元素
· isEmpty—返回链表是否为空
最经常会被问到的面试题
· 反转链表
· 检测链表中的循环
· 返回倒数第n个链表中的元素
· 移除链表中重复的元素
图结构
图是一个很多节点互相连接的网络形式。节点也被称作顶点。一对(x,y)称为边，表示顶点x连接到顶点y。这条边可以包含权重/路径长度，显示从顶点x到顶点y所需要的权重/路径长度。
图结构有2种类型：无向图和有向图
在编程语言中，图结构以2种形式存在：邻接矩阵、邻接链表。
最常见的图结构的算法：
· 广度优先搜索
· 深度优先搜索
最经常会被问到的面试题
· 实现广度优先和深度优先搜索
· 判断一个图是否是一个树
· 计算图中有多少个边
· 找出两个顶点之间的最短路径
树
树是一个又节点连接他们的边组成的分层数据结构。树与图相似，主要的不同点是树中不存在闭环。
树被广泛用在了人工智能和复杂算法中，为解决问题提供了一种高效的存储机制。
树又下面几种类型：
· N叉树
· 平衡树
· 二叉树
· 二叉搜索树
· 二叉平衡树
· 红黑树
· 2—3树
以上二叉树和二叉搜索树用到的最多。
最经常会被问到的面试题
· 计算二叉树的高度
· 找出二叉搜索树中第K最大的值
· 找出第K个节点到根结点的距离
· 在一个二叉树中找到给定节点的祖先
字典树
字典树也被叫做"前缀树"，是类似树形的数据结构，对解决关联的字符串的问题非常高效。它可以实现快速搜索，主要用于搜索字典中的单词，在搜索引擎中提供"推荐功能"，甚至还被用在IP路由上。
下面是存储在字典树中"top"、"thus"、"their"的说明：
这些字母由顶部到底部的方式存储，其中绿色节点"p"、"s"、"r"分别表示"top"、"thus"、"their"。
最经常会问到的面试题
· 计算在字典树中字母的总和
· 打印字典树中存储的所有字母
· 使用字典树给一个数组元素排序
· 使用字典树从字典中形成单词
· 构建一个T9字典
哈希表
散列是一个用于唯一标识对象并将每个对象存储在一些预先计算的唯一索引(key)的过程。这些对象以"键—值"对的格式存储的，像这样的形式被叫做"字典"。每个对象可以通过他们的key来搜索。基于hash可以有很多不同的数据结构，最常用的是散列表。
散列表通常又数组来实现。
散列表数据结构的性能取决于下面3个元素：
· 散列函数
· 散列表的大小
· 碰撞处理方法
下面是散列映射在一个数组中的说明。数组的索引通过hash函数计算来得到。
最经常会被问到的面试题
· 在数组中查找对称对
· 追踪完成的旅行路径
· 判断数组是否是另一数组的子集
· 检查给定的数组是否不相交
至此，以上就是你在面试之前应该熟悉的八大数据结构。
如果你像找关于数据结构的面试技巧，你可以看这篇课程：Data Structures for Coding Interviews(Python, Java).
