学习算法必须要了解的数据结构

什么是数据结构？

简而言之，数据结构是一个以特定形式存储数据的容器。这种“形式”允许数据结构在某些操作中更加高效。

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

由于数据结构用于以有组织的形式存储数据，并且由于数据是计算机科学中最重要的实体，因此数据结构的重要性是显而易见的。无论你解决什么问题，你都必须以某种方式处理数据 - 无论是员工的工资，股票价格，购物清单，还是简单的电话簿。根据不同的场景，数据需要以特定格式存储。我们有一些数据结构可以满足我们以不同格式存储数据的需求。

常用的数据结构

常用的数据结构包括数组、堆栈、队列、链表、树、图表和哈希表等等，下面我们就简要介绍一下：

数组

数组是最简单和最广泛使用的数据结构。其他数据结构（如堆栈和队列）都是从数组派生的。下例是一个大小为4的简单数组：

每个数据元素都会分配一个称为索引值，该值对应于该项目在数组中的位置。大多数语言将数组的起始索引定义为0。

数组主要有两种类型：

• 一维数组
• 多维数组

数组的基本操作

• 插入 - 在给定索引处插入元素
• Get - 返回给定索引处的元素
• 删除 - 删除给定索引处的元素
• 大小 - 获取数组中元素的总数

常见的数组面试问题

• 找到数组的第二个最小元素
• 数组中的第一个非重复整数
• 合并两个排序的数组
• 重新排列数组中的正负值

堆栈

堆栈是一种只允许在表的一端进行插入操作和删除操作的线性表。其工作原理是后进先出。下图是包含三个数据元素（1,2和3）的堆栈示例：

堆栈的基本操作：

• Push - 在顶部插入元素
• Pop - 从堆栈中删除后返回顶部元素
• isEmpty - 如果堆栈为空，则返回true
• Top - 返回顶部元素而不从堆栈中删除

常见的Stack面试问题

• 使用堆栈评估后缀表达式
• 对堆栈中的值进行排序
• 检查表达式中的平衡括号

队列

与堆栈类似，队列是另一种线性数据结构，以顺序方式存储元素。Stack和Queue之间唯一的显着区别是，Queue不使用LIFO方法，而是实现先进先出方法。

Queue的一个现实生活例子是一排人在售票亭排队买票。如果再来一个人，那么他将从最后加入队列，而不是从头开始 - 站在前面的人将是第一个获得票离开。

下图是一个包含四个数据元素（1,2,3和4）的队列：

队列的基本操作

• Enqueue() - 将元素插入队列的末尾
• Dequeue() - 从队列的开头删除一个元素
• isEmpty() - 如果queue为空，则返回true
• Top() - 返回队列的第一个元素

常见的Queue面试问题

• 使用队列实现堆栈
• 反转队列的前k个元素
• 使用队列生成从1到n的二进制数

链表

链表是另一个重要的线性数据结构，它最初可能看起来类似于数组，但在内存分配，内部结构以及如何执行插入和删除的基本操作方面有所不同。

链表就像一个节点链，每个节点包含数据和指向链中后续节点的指针等信息。有一个头指针，它指向链表的第一个元素，如果列表是空的，那么它只是指向null或什么都没有。链表用于实现文件系统，哈希表和邻接列表。下面是链表的内部结构的直观表示：

链表的两种类型：

• 单链表（单向）
• 双向链表（双向）

链表的基本操作：

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

常见的链表面试问题

• 反转链表
• 检测链表中的循环
• 从链接列表中的末尾返回第N个节点
• 从链表中删除重复项

图

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

图的类型：

• 无向图
• 有向图

在编程语言中，图形可以使用两种形式表示：

• 邻接矩阵
• 邻接表

常见的图遍历算法：

• 广度优先搜索
• 深度优先搜索

常见的Graph采访问题

• 实现广度和深度优先搜索
• 检查图形是否为树
• 计算图表中的边数
• 找到两个顶点之间的最短路径

树

树是一种分层数据结构，由顶点（节点）和连接它们的边组成。树类似于图形，但区分树和图形的关键点是树中不存在循环。树结构广泛用于人工智能和复杂算法，以提供解决问题的有效存储机制。这是一个简单树的图像，以及树数据结构中使用的基本术语：

以下是树木的类型：

• N-ary树
• 平衡树
• 二叉树
• 二叉搜索树
• AVL树
• 红黑树
• 2-3树

常见的Tree面试问题

• 找到二叉树的深度
• 在二叉搜索树中查找第k个最大值
• 查找距离根“k”距离的节点
• 在二叉树中查找给定节点的根节点

哈希表

哈希是一个用于唯一标识对象并将每个对象存储在一些预先计算的唯一索引（称为“密钥”）的过程。因此，该对象以“键值”对的形式存储，并且这些项的集合被称为“字典”。可以使用该键搜索每个对象。基于哈希有不同的数据结构，但最常用的数据结构是哈希表。哈希表通常使用数组实现。哈希数据结构的性能取决于以下三个因素：

• 哈希函数
• 哈希表的大小
• 碰撞处理方法

这是一个如何在数组中映射哈希的说明。该数组的索引是通过哈希函数计算的。

常见的哈希面试问题

• 在数组中查找对称对
• 追踪完整的旅程路径
• 查找数组是否是另一个数组的子集
• 检查给定的数组是否不相交