Question

数组是一种直接利用内存物理结构（计算机的特性）的最基本的数据结构。只需使用for语句，就可以连续地处理数组中所存储的数据，实现各种各样的算法。但在现实世界中也有一些数据结构，仅凭借数组是无法实现的，比如有的数据结构可以把数据堆积得像山一样，有的数据结构可以把数据排成一队，有的数据结构可以任意地改变数据的排列顺序，还有的数据结构可以把数据分为两路排列，等待。为了用程序实现这些数据结构，就必须要设法改造数组，但是与之相应的内存的物理结构又是改变不了的，这可怎么办好呢？

就像在算法中有典型算法一样，在数据结构中也有典型数据结构（如表6.1所示），它们都是由程序员发明创造的。

表6.1 主要的典型数据结构

名称      数据结构的特征

栈        把数据堆积的像山一样

队列       把数据排成一队

链表       可以任意地改变数据的排列顺序

二叉树     把数据分为两路排列

这些数据结构其实都是通过程序从逻辑上改变了内存的物理结构，即数据在内存上呈现出的连续分布状态。接下来笔者会依次介绍每种典型的数据结构，所以请抓住它们各自的特点

栈（stack）的本意就是干草堆（如图6.4所示）

图6.4 栈的示意图

在牧场中，把干草堆积在地上就会形成一座小山。为了把干草堆成山就要从下往上不断地堆积。在程序中干草就相当于数据。而在给家畜喂食的时候，要从上往下把堆积的干草（数据）取下来，也就是说，数据的使用顺序与堆积顺序是相反的，通常把这种存取方式称为LIFO（Last In First Out，后进先出），即最后被存入 的数据最先被处理的。在那些作为程序处理对象的实际业务中，可以用栈来模拟诸如堆积在桌子上的文件等场景，既然无法马上处理，就暂且先都堆放在栈里吧

队列（Queue）就是等待做某事而排成的队（如图6.5所示）

图6.5 队列示意图

队列与栈正相反，排在队首的乘客最先接受服务，通常把这种形式称为FIFI（First In First Out，先进先出），即最先被存入的数据最先被处理。当无法一下处理完数据的时候，就可以暂且先把这些数据排队。之后会介绍队列的数据结构，其实现方式一般是把数组的首尾相连，形成一个圆环

“链表”的概念相当于几个人手拉手排成一排（如图6.6所示）

图6.6 链表示意图

某个人只要松开拉住的那只手，再去拉住另一只手，这一排人（相当于数据）的排列顺序就改变了。而只要松开拉住的手，再让一个新人加入进来并拉住他的手，就相当于完成了数据的插入操作

二叉树的概念正如其名，相当于一棵树，不过这棵树与自然界中的树稍有不同，二叉树从树干开始分杈，树枝上又有分杈，但每次都只会分成两杈，在每个分杈点上有一片叶子（相当于数据）（如图6.7所示）。稍后就会了解到二叉树其实是链表的特殊形态

图6.7 二叉树示意图