应对程序员面试，你必须知道的八大数据结构

瑞士计算机科学家Niklaus Wirth在1976年写了一本书，名为《算法+=编程》。

40多年后，这个等式仍被奉为真理。这就是为什么在面试过程中，需要考察软件工程师对的理解。

几乎所有的问题都需要面试者对有深刻的理解。无论你是初入职场的新兵(刚从大学或者编程培训班毕业)，还是拥有几十年经验的职场老鸟。

有些面试题会明确提及某种数据结构，例如，“给定一个二叉树。”而另一些则隐含在面试题中，例如，“我们希望记录每个作者相关的书籍数量。”

即便是对于一些非常基础的工作来说，学习数据结构也是必须的。那么，就让我们先从一些基本概念开始入手。

什么是数据结构?

简单地说，数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的，而对于其他操作则是低效的。首先我们需要理解各种数据结构，才能在处理实际问题时选取最合适的数据结构。

为什么我们需要数据结构?

数据是计算机科学当中最关键的实体，而数据结构则可以将数据以某种组织形式存储，因此，数据结构的价值不言而喻。

无论你以何种方式解决何种问题，你都需要处理数据——无论是涉及员工薪水、股票价格、购物清单，还是只是简单的电话簿问题。

数据需要根据不同的场景，按照特定的格式进行存储。有很多数据结构能够满足以不同格式存储数据的需求。

常见的数据结构

首先列出一些最常见的数据结构，我们将逐一说明：

•   数组
•   栈
•   队列
•   链表
•   树
•   图
•   字典树(这是一种高效的树形结构，但值得单独说明)
•   散列表(哈希表)

数组

数组是最简单、也是使用最广泛的数据结构。栈、队列等其他数据结构均由数组演变而来。下图是一个包含元素(1，2，3和4)的简单数组，数组长度为4。

每个数据元素都关联一个正数值，我们称之为索引，它表明数组中每个元素所在的位置。大部分语言将初始索引定义为零。

以下是数组的两种类型：

• 一维数组(如上所示)
• 多维数组(数组的数组)

数组的基本操作

•   Insert——在指定索引位置插入一个元素
•   Get——返回指定索引位置的元素
•   Delete——删除指定索引位置的元素
•   Size——得到数组所有元素的数量

面试中关于数组的常见问题

•   寻找数组中第二小的元素
•   找到数组中第一个不重复出现的整数
•   合并两个有序数组
•   重新排列数组中的正值和负值

栈

著名的撤销操作几乎遍布任意一个应用。但你有没有思考过它是如何工作的呢?这个问题的解决思路是按照将最后的状态排列在先的顺序，在内存中存储历史工作状态(当然，它会受限于一定的数量)。这没办法用数组实现。但有了栈，这就变得非常方便了。

可以把栈想象成一列垂直堆放的书。为了拿到中间的书，你需要移除放置在这上面的所有书。这就是LIFO(后进先出)的工作原理。

下图是包含三个数据元素(1，2和3)的栈，其中顶部的3将被最先移除：

栈的基本操作

•   Push——在顶部插入一个元素
•   Pop——返回并移除栈顶元素
•   isEmpty——如果栈为空，则返回true
•   Top——返回顶部元素，但并不移除它

面试中关于栈的常见问题

•   使用栈计算后缀表达式
•   对栈的元素进行排序
•   判断表达式是否括号平衡

队列

与栈相似，队列是另一种顺序存储元素的线性数据结构。栈与队列的最大差别在于栈是LIFO(后进先出)，而队列是FIFO，即先进先出。

一个完美的队列现实例子：售票亭排队队伍。如果有新人加入，他需要到队尾去排队，而非队首——排在前面的人会先拿到票，然后离开队伍。

下图是包含四个元素(1，2，3和4)的队列，其中在顶部的1将被最先移除：

移除先入队的元素、插入新元素

队列的基本操作

•   Enqueue() —— 在队列尾部插入元素
•   Dequeue() ——移除队列头部的元素
•   isEmpty()——如果队列为空，则返回true
•   Top() ——返回队列的第一个元素

面试中关于队列的常见问题

•   使用队列表示栈
•   对队列的前k个元素倒序
•   使用队列生成从1到n的二进制数

链表

链表是另一个重要的线性数据结构，乍一看可能有点像数组，但在内存分配、内部结构以及数据插入和删除的基本操作方面均有所不同。

链表就像一个节点链，其中每个节点包含着数据和指向后续节点的指针。链表还包含一个头指针，它指向链表的第一个元素，但当列表为空时，它指向null或无具体内容。

链表一般用于实现文件系统、哈希表和邻接表。

这是链表内部结构的展示：

链表包括以下类型：

• 单链表(单向)
• 双向链表(双向)

链表的基本操作：

•   InsertAtEnd - 在链表的末尾插入指定元素
•   InsertAtHead - 在链接列表的开头/头部插入指定元素
•   Delete - 从链接列表中删除指定元素
•   DeleteAtHead - 删除链接列表的第一个元素
•   Search - 从链表中返回指定元素
•   isEmpty - 如果链表为空，则返回true

面试中关于链表的常见问题

•   反转链表
•   检测链表中的循环
•   返回链表倒数第N个节点
•   删除链表中的重复项

图

图是一组以网络形式相互连接的节点。节点也称为顶点。一对节点(x，y)称为边(edge)，表示顶点x连接到顶点y。边可以包含权重/成本，显示从顶点x到y所需的成本。