1700415272
计算机是怎样跑起来的 [:1700412673]
1700415273
计算机是怎样跑起来的 6.4 要点4：了解并掌握典型数据结构的类型和概念
1700415274
1700415275
数组是一种直接利用内存物理结构（计算机的特性）的最基本的数据结构。只需使用for语句，就可以连续地处理数组中所存储的数据，实现各种各样的算法。但在现实世界中也有一些数据结构，仅凭借数组是无法实现的，比如有的数据结构可以把数据堆积得像山一样，有的数据结构可以把数据排成一队，有的数据结构可以任意地改变数据的排列顺序，还有的数据结构可以把数据分为两路排列，等待。为了用程序实现这些数据结构，就必须要设法改造数组，但是与之相应的内存的物理结构又是改变不了的，这可怎么办好呢？
1700415276
1700415277
就像在算法中有典型算法一样，在数据结构中也有典型数据结构（如表6.1所示），它们都是由程序员发明创造的。
1700415278
1700415279
表6.1 主要的典型数据结构
1700415280
1700415281
名称 数据结构的特征
1700415282
1700415283
栈 把数据堆积的像山一样
1700415284
1700415285
队列 把数据排成一队
1700415286
1700415287
链表 可以任意地改变数据的排列顺序
1700415288
1700415289
二叉树 把数据分为两路排列
1700415290
1700415291
这些数据结构其实都是通过程序从逻辑上改变了内存的物理结构，即数据在内存上呈现出的连续分布状态。接下来笔者会依次介绍每种典型的数据结构，所以请抓住它们各自的特点
1700415292
1700415293
栈（stack）的本意就是干草堆（如图6.4所示）
1700415294
1700415295
图6.4 栈的示意图
1700415296
1700415297
1700415298
1700415299
1700415300
在牧场中，把干草堆积在地上就会形成一座小山。为了把干草堆成山就要从下往上不断地堆积。在程序中干草就相当于数据。而在给家畜喂食的时候，要从上往下把堆积的干草（数据）取下来，也就是说，数据的使用顺序与堆积顺序是相反的，通常把这种存取方式称为LIFO（Last In First Out，后进先出），即最后被存入 的数据最先被处理的。在那些作为程序处理对象的实际业务中，可以用栈来模拟诸如堆积在桌子上的文件等场景，既然无法马上处理，就暂且先都堆放在栈里吧
1700415301
1700415302
队列（Queue）就是等待做某事而排成的队（如图6.5所示）
1700415303
1700415304
图6.5 队列示意图
1700415305
1700415306
1700415307
1700415308
1700415309
队列与栈正相反，排在队首的乘客最先接受服务，通常把这种形式称为FIFI（First In First Out，先进先出），即最先被存入的数据最先被处理。当无法一下处理完数据的时候，就可以暂且先把这些数据排队。之后会介绍队列的数据结构，其实现方式一般是把数组的首尾相连，形成一个圆环
1700415310
1700415311
“链表”的概念相当于几个人手拉手排成一排（如图6.6所示）
1700415312
1700415313
图6.6 链表示意图
1700415314
1700415315
1700415316
1700415317
1700415318
某个人只要松开拉住的那只手，再去拉住另一只手，这一排人（相当于数据）的排列顺序就改变了。而只要松开拉住的手，再让一个新人加入进来并拉住他的手，就相当于完成了数据的插入操作
1700415319
1700415320
二叉树的概念正如其名，相当于一棵树，不过这棵树与自然界中的树稍有不同，二叉树从树干开始分杈，树枝上又有分杈，但每次都只会分成两杈，在每个分杈点上有一片叶子（相当于数据）（如图6.7所示）。稍后就会了解到二叉树其实是链表的特殊形态
1700415321