1.2 数据结构的分类与应用

1.2 数据结构的分类与应用

• 数据结构，就是字面意思，一门用来研究数据如何高效的在计算机中进行存储和查询的学科。
• 几乎所有的数据结构，也都是从生活中和数学理论中，衍生而来。
  下表列出了常见的数据结构，我们先来熟悉一下他们的名字。

请注意，不同地区的翻译可能存在差异，但这里列出的是较为通用的翻译。

数组（Array）

• 中国大陆将 Array 翻译为了数组，我认为在某种程度上会误导初学者。其实在更广义的场景中， Array 我们通常翻译为阵列或者队列。
  你可以把他理解成就是一个一个的数据紧挨着排好队的样子。当然数据可以是具体的数字也可以是一段话或者图片等。

链表（Linked List）

数组需要紧挨着的连续的存储空间，比如6个朋友去住酒店，他们要求房间都挨在一起，但不巧已经没有6个都挨在一起的房间了。不如他们妥协一下，分开住，7楼住2个房间，8楼住3个房间，10楼住1个房间，这就是链表。

链表中的每个元素，不需要挨在一起，只需要记住自己的后一个元素在哪里。

上面的链表我们通常称为单向链表，每个元素只记录自己的后继元素。
如果每个元素同时也记录了自己的前驱元素，称为双向链表。

栈（Stack）

栈，在中国大陆有些书籍教材也翻译为堆栈。字面意思为整齐的叠放。类似盘子或者书籍（平放）的常见摆放方式。栈这种数据结构，主要体现数据存入和取出的特殊顺序，为先进后出（FILO:First In Last Out），或者叫后进先出（LIFO:Last In First Out）。
我们比较熟悉的场景是，文件管理器和浏览器中通常都带有页面回退的功能，我们点击不同的链接进行页面跳转的时候，浏览器会将访问过的页面链接依次记录在栈中，而当点击返回按钮时，会依次取出栈中保存的页面链接，这个过程是后进先出的。

队列（Queue）

队列刚好与上面的栈相反，专门用来处理先来后到的事情。所以队列体现出的数据存入和取出的顺序为先进先出（FIFO:First In First Out）。比如我们将多首歌曲加入播放器的播放列表，默认情况下，播放器就会按照播放列表的顺序，依次播放歌曲。

哈希表（Hash Table）

Hash 是混杂、拼凑的意思，所以在中国香港和中国台湾通常将 Hash Table 翻译为杂凑表。中国大陆音译为哈希表或者书面一些的翻译为散列表。你可能已经被这些听起来乱七八糟的的名词给搞晕了。不过哈希表的原理和想解决的事情其实很简单。
我们试想一个场景，现在你想邀请你的几个朋友周末一起去看电影，这时你拿出手机打开通讯录，当你开始输入朋友的名字或者昵称来检索他的手机号时，哈希表就已经登场了。
所谓的哈希，就是将原来的数据（朋友的名字）通过一种哈希算法（散列算法），计算得到一个与之对应的新数据，称之为哈希值。哈希值本质上是用更加简短的数据来表示原有数据。
那哈希表有什么用呢？当你的通讯录非常大的时候，如果每次需要从头到尾找一遍，那么查找的时间复杂度为O(n)，但如果使用哈希表存储通讯录，可以将时间复杂度变为O(1)。如果还记得关于时间复杂度知识的同学，应该能感受到这其中巨大的改变。

二叉树（Binary Tree）

树是一类数据结构的统称，他的名字很形象。我们生活中见到的树，露出地面的部分，下半部分通常是一个树干，上半部分通常会有庞杂的枝叶。

计算机的数据结构中的树，为了画图方便，将树干放在最上面，称之为 root（也就是根）。枝叶画在下面，类似下面这样。

细心的同学可能发现了，树和链表好像有相似之处。没错，树就是将链表的一对一，扩展成了一对多。对于计算机来说，所有的树都可以被等价转换为二叉树，而二叉树又比较符合计算机二进制的运算特点，所以我们通常使用和讨论最为广泛的，都是二叉树。

图（Graph）

这里的图，又是树的扩展，从一对多扩展为多对多。图中可以有多个元素，元素之间可以互相交错的产生多个关联，类似生活中的交通图或社交网络。

堆（Heap）

堆也是由二叉树演化而来，他的名字很形象，就像一个小土堆一样，通常会按照从大到小或者从小到大的顺序，将元素从上到下摆放在堆中，方便我们随时在堆顶取最大值或最小值。

      1
   ╱   ╲
  2     3
 ╱ ╲   ╱ ╲
4   5 6   7