数组是一种直接利用内存物理结构（计算机的特性）的最基本的数据结构。只需使用for语句，就可以连续地处理数组中所存储的数据，实现各种各样的算法。但是在现实世界中也有一些数据结构，仅凭借数组是无法实现的，比如有的数据结构可以把数据堆积得像小山一样，有的数据结构可以把数据排成一队，有的数据结构可以任意地改变数，据的排列顺序，还有的数据结构可以把数据分为两路排列，等等。为了用程序实现这些数据结构，就必须要设法改造数组，但是与之相应的内存的物理结构又是改变不了的。
就像在算法中有典型算法一样，在数据结构中也有典型数据结构，它们都是由老一辈程序员发明创造的。这些数据结构其实都是通过程序从逻辑上改变了内存的物理结构，即数据在内存上呈现出的连续分布状态。接下来笔者会依次介绍每种典型的数据结构，所以请抓住它们各自的特点。
主要的典型数据结构
| 名称 | 数据结构的特征 |
| 栈 | 把数据像小山一样堆积起来 |
| 队列 | 把数据排成一队 |
| 链表 | 可以任意地改变数据的排列顺序 |
| 二叉树 | 把数据分为两路排列 |
“栈”(Stack)的本意是干草堆(如图6.4所示)。在牧场中，把喂家畜吃的干草堆积在地上就会形成一座小山。为了把干草堆成山就要从下往上不断地堆积。在程序中干草就相当于数据。而在给家畜喂食的时候，则要按照从上往下的顺序把堆积起来的干草（数据）取下来。也就是说，数据的使用顺序与堆积顺序是相反的。通常把这种存取方式称为LIFO(Last In First Out，后进先出)，即最后被存入的数据是最先被处理的。在那些作为程序处理对象的实际业务中，可以用栈来模拟诸如堆积在桌子上的文件等场景。既然无法马上处理，就暂且先都堆放在栈里吧。
“队列”(Queue)就是等待做某事而排成的队。笔者经常要在东京的西日暮里站从营团地铁换乘日本铁路。下了地铁就要去买日本铁路的车票，在购票窗口前买票的乘客会排成一队。这就是现实世界中的队列(如图6.5所示)。队列与栈正相反，排在队头的乘客可以最先买到车票。通常把这种形式称为FIFO(First In First Out，先进先出)，即最先被存入的数据也是最先被处理的。当无法一下子处理完数据的时候，就可以暂且先把这些数据排成队。之后会介绍队列的数据结构，其实现方式一般是把数组的首尾相连，形成一个圆环。
“链表”的概念就相当于几个人手拉着手排成一排(如图6.6所示）。某个人只要松开拉住的那只手，再去拉住另一只手，这一排人（相当于数据）的排列顺序就改变了。而只要先松开拉住的手，再让一个新人加入进来并拉住他的手，就相当于完成了数据的插入操作。
“二叉树”的概念正如其名，就相当于一棵树。不过这棵树与自然界中的树稍有些不同，二叉树从树干开始分权，树枝上又有分权，但每次都只会分为两杈，在每个分权点上有一片叶子（相当于数据）（如图6.7所示)。稍后诸位就会了解到二叉树其实是链表的特殊形态。
参考资料：计算机是怎么跑起来的第六章
完结！
