1.2 数据结构的分类与应用
1.2 数据结构的分类与应用
- 数据结构，就是字面意思，一门用来研究数据如何高效的在计算机中进行存储和查询的学科。
- 几乎所有的数据结构，也都是从生活中和数学理论中，衍生而来。
下表列出了常见的数据结构，我们先来熟悉一下他们的名字。
| 序号 | 英文名 | 中国大陆翻译 | 中国香港翻译 | 中国台湾翻译 | 生活中的场景 |
|---|---|---|---|---|---|
| 1 | Array | 数组 | 陣列 | 陣列 | 超市的货架上摆放着一排排的商品，每个格子只能放置一个商品，类似于数组的结构。 |
| 2 | Linked List | 链表 | 鏈結列表 | 鏈結串列 | 人们在月台排队等车，每个人都知道前后两个人，类似于链表结构。 |
| 3 | Stack | 栈 | 堆疊 | 堆疊 | 堆放盘子的方式，先放进去的盘子在底部，后放进去的在顶部，取盘子时也是从顶部开始取。这就类似于栈的先进后出（FILO）特性。 |
| 4 | Queue | 队列 | 佇列 | 佇列 | 在银行办理业务时，客户需要按顺序排队等待叫号，符合队列先进先出（FIFO）的特性。 |
| 5 | Hash Table | 哈希表 | 雜湊表 | 雜湊表 | 字典（如英汉词典），通过单词快速查找对应的释义，类似于哈希表的查找功能。 |
| 6 | Binary Tree | 二叉树 | 二元樹 | 二元樹 | 家谱树，每个人有两个子女，分别在左右两侧，类似于二叉树的结构。 |
| 7 | Graph | 图 | 圖 | 圖 | 交通路网，各个城市通过公路、铁路等连接在一起，形成复杂的图结构。 |
| 8 | Heap | 堆 | 堆積 | 堆積 | 优先级队列，如医院急诊室，根据病情严重程度安排就诊顺序，类似于堆的特性。 |
请注意，不同地区的翻译可能存在差异，但这里列出的是较为通用的翻译。
数组（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