什么是数据结构？

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

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

常见的数据结构包括：

• l 数组
• l 栈
• l 队列
• l 链表
• l 树
• l 图
• l 字典树
• l 散列表（哈希表）

一、数组

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

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

以下是数组的两种类型：

• 一维数组
• 多维数组（数组的数组）

二、栈

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

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

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

栈的基本操作：

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

三、队列

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

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

例如四个元素（1，2，3和4）的队列，其中在顶部的1将被最先移除：移除先入队的元素、插入新元素。

队列的基本操作

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

四、链表

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

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

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

链表包括以下类型：

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

链表的基本操作：

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

五、图

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

图的类型：

• 无向图
• 有向图

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

• 邻接矩阵
• 邻接表

常见图遍历算法

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

六、树

树形结构是一种层级式的数据结构，由顶点（节点）和连接它们的边组成。 树类似于图，但区分树和图的重要特征是树中不存在环路。

树形结构被广泛应用于人工智能和复杂算法，它可以提供解决问题的有效存储机制。

l 树的数据结构中使用的基本术语：

• Root - 根节点
• Parent - 父节点
• Child - 子节点
• Leaf - 叶子节点
• Sibling - 兄弟节点

l 是树形结构的主要类型：

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

其中，二叉树和二叉搜索树是最常用的树。

七、字典树（Trie）

字典树，也称为“前缀树”，是一种特殊的树状数据结构，对于解决字符串相关问题非常有效。它能够提供快速检索，主要用于搜索字典中的单词，在搜索引擎中自动提供建议，甚至被用于IP的路由。

以下是在字典树中存储三个单词“top”，“so”和“their”的例子：

这些单词以顶部到底部的方式存储，其中绿色节点“p”，“s”和“r”分别表示“top”，“thus”和“theirs”的底部。

八、哈希表

哈希法（Hashing）是一个用于唯一标识对象并将每个对象存储在一些预先计算的唯一索引（称为“键（key）”）中的过程。因此，对象以键值对的形式存储，这些键值对的集合被称为“字典”。可以使用键搜索每个对象。基于哈希法有很多不同的数据结构，但最常用的数据结构是哈希表。

哈希表通常使用数组实现。

l 散列数据结构的性能取决于以下三个因素：

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

下图为如何在数组中映射哈希键值对的说明。该数组的索引是通过哈希函数计算的。