byFahimulHaq
瑞士计算机科学家NiklausWirth在年写了一本书，名为《算法+数据结构=程序》。
40多年后，这个等式仍然成立。这就是为什么软件工程候选人必须证明他们对数据结构及其应用程序的理解。
几乎所有问题都要求考生表现出对数据结构的深刻理解。无论您刚毕业（从大学还是编程训练营）毕业，还是有数十年的经验都没关系。
有时访谈问题明确提到数据结构，例如“给定二叉树”。其他时候它是隐式的，例如“我们要跟踪与每个作者关联的书籍数量”。
即使您只是想在当前工作中变得更好，学习数据结构也是必不可少的。让我们从了解基础开始。
什么是数据结构？简而言之，数据结构是一个以特定布局存储数据的容器。这种“布局”使数据结构在某些操作中有效，而在另一些操作中效率低下。您的目标是了解数据结构，以便选择最适合当前问题的数据结构。
为什么我们需要数据结构？由于数据结构用于以有组织的形式存储数据，并且由于数据是计算机科学中最重要的实体，因此数据结构的真正价值显而易见。
无论您要解决什么问题，都必须以一种或另一种方式处理数据-无论是员工的薪水，股票价格，购物清单还是简单的电话簿。
根据不同的场景，数据需要以特定的格式存储。我们有一些数据结构可以满足我们以不同格式存储数据的需求。
常用数据结构让我们首先列出最常用的数据结构，然后逐一介绍它们：
数组
堆栈
队列
链表
树
图
前缀树
哈希表
数组数组是最简单，使用最广泛的数据结构。其他数据结构（如堆栈和队列）是从数组派生的。
这是大小为4的简单数组的图像，其中包含元素（1、2、3和4）。
每个数据元素都被分配一个称为Index的正数值，它对应于该项在数组中的位置。大多数语言将数组的起始索引定义为0。
以下是两种类型的数组：
一维数组（如上所示）
多维数组（数组中的数组）
阵列的基本操作插入—在给定索引处插入元素
Get—返回给定索引处的元素
删除-删除给定索引处的元素
Size—获取数组中元素的总数
Array面试常见问题查找数组的第二个最小元素
数组中的第一个非重复整数
合并两个排序的数组
重新排列数组中的正值和负值
堆栈我们都熟悉著名的“撤消”选项，该选项几乎存在于每个应用程序中。有没有想过它是如何工作的？想法是：您将工作的先前状态（限于特定数量）存储在内存中，顺序是最后一个出现在最前面。这不能仅仅通过使用数组来完成。这就是堆栈派上用场的地方。
堆叠的真实示例可能是一堆以垂直顺序放置的书。为了获得位于中间位置的书，您需要删除所有放在其顶部的书。这就是LIFO（后进先出）方法的工作方式。
这是包含三个数据元素（1、2和3）的堆栈图像，其中3在顶部，并且将首先删除：
堆栈的基本操作：
推入—在顶部插入一个元素
Pop—从堆栈中移除后返回顶部元素
isEmpty—如果堆栈为空，则返回true
Top—返回顶部元素，而不从堆栈中移除
堆栈采访常见问题使用堆栈评估后缀表达式
对堆栈中的值进行排序
检查表达式中的平衡括号
队列与Stack类似，Queue是另一个线性数据结构，该结构以顺序方式存储元素。堆栈和队列之间唯一的显着区别是，队列使用FIFO方法代替了LIFO方法，该方法是先进先出的缩写。
排队的一个完美的现实例子：排队的人在售票亭等车。如果有新人来，他们将从头开始而不是从一开始就加入队伍—站在最前面的人将是第一个获得票证并因此离开队伍的人。
这是包含四个数据元素（1、2、3和4）的Queue图像，其中1在顶部，并且将首先删除：
队列的基本操作Enqueue（）—将元素插入队列的末尾
Dequeue（）-从队列的开头删除一个元素
isEmpty（）—如果队列为空，则返回true
Top（）—返回队列的第一个元素
排队面试常见问题使用队列实现堆栈
反转队列的前k个元素
使用队列生成从1到n的二进制数
链表链表是另一种重要的线性数据结构，乍一看可能与数组相似，但在内存分配，内部结构以及插入和删除的基本操作上有所不同。
链表就像一个节点链，其中每个节点都包含诸如数据之类的信息以及指向链中后续节点的指针。有一个头指针，它指向链接列表的第一个元素，如果列表为空，则仅指向null或不指向任何内容。
链接列表用于实现文件系统，哈希表和邻接列表。
这是链表内部结构的直观表示：
以下是链接列表的类型：
单链表（单向）
双链表（双向）
链表的基本操作：InsertAtEnd—在链表的末尾插入给定元素
InsertAtHead—在链接列表的开头/开头插入给定元素
删除-从链接列表中删除给定元素
DeleteAtHead—删除链接列表的第一个元素
搜索-从链接列表中返回给定的元素
isEmpty—如果链接列表为空，则返回true
常见问题链表面试问题反向链接列表
检测链表中的循环
从链表的末尾返回第N个节点
从链接列表中删除重复项
图（Graph）图是一组以网络形式相互连接的节点。节点也称为顶点。阿对（x，y）的被称为边缘，这表明顶点X被连接到顶点?。一条边可能包含权重/成本，表示从顶点x到y遍历需要多少成本。
图的类型：
无向图
有向图
在编程语言中，图形可以使用两种形式表示：
邻接矩阵
邻接表
常见的图遍历算法：
广度优先搜索
深度优先搜索
Graph面试常见问题实施广度和深度优先搜索
检查图是否为树
计算图中的边数
查找两个顶点之间的最短路径
树（Tree）树是由顶点（节点）和连接它们的边组成的分层数据结构。树类似于图，但是区别图与树的关键是树中不能存在循环。
树在人工智能和复杂算法中被广泛使用，以提供有效的存储机制来解决问题。
这是一棵简单的树的图像，以及树数据结构中使用的基本术语：
以下是树的类型：
一元树
平衡树
二叉树
二进制搜索树
AVL树
红黑树
2–3树
其中，二叉树和二叉搜索树是最常用的树。
树面试常见问题查找二叉树的高度
在二叉搜索树中找到第k个最大值
查找距根“k”距离的节点
在二叉树中查找给定节点的祖先
前缀树（Trie）Trie，也称为“前缀树”，是一种类似树的数据结构，被证明对于解决与字符串有关的问题非常有效。它提供了快速的检索功能，主要用于在字典中搜索单词，在搜索引擎中提供自动建议，甚至用于IP路由。
这是Trie中三个单词“top”，“thus”和“their”的存储方式的说明：
单词以从上到下的方式存储，其中绿色节点“p”，“s”和“r”分别表示“top”，“thus”和“their”的结尾。
特里采访常见问题：
计算Trie中的单词总数
打印所有存储在Trie中的单词
使用Trie排序数组的元素
使用Trie从字典中套用单词
建立T9字典
哈希表散列是用于唯一标识对象并将每个对象存储在一些预先计算的唯一索引（称为“键”）的过程。因此，对象以“键值”对的形式存储，此类项目的集合称为“字典”。可以使用该键搜索每个对象。基于哈希的数据结构不同，但是最常用的数据结构是哈希表。
哈希表通常使用数组来实现。
哈希数据结构的性能取决于以下三个因素：
散列函数
哈希表的大小
碰撞处理方法
这是散列如何在数组中映射的说明。该数组的索引是通过哈希函数计算的。
散列面试常见问题在数组中查找对称对
追踪完整的旅程
查找一个数组是否是另一个数组的子集
检查给定数组是否不相交
以上是进入编码面试之前您绝对应该知道的前八个数据结构。
英文原文：
NiklausWirth,aSwiss