本节书摘来华章计算机《数据结构与抽象：Java语言描述（原书第4版）》一书中的第1章 ，［美］弗兰克M.卡拉诺（Frank M. Carrano） 蒂莫西M.亨利（Timothy M. Henry） 著 罗得岛大学 新英格兰理工学院 辛运帏 饶一梅 译 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
引 言
Data Structures and Abstractions with Java, Fourth Edition
组 织 数 据
环顾四周，你就会发现人们安排事情的方式。早晨去商店时，你会站在线后等待付账。这条线会让人们按先来后到的次序排队。线后的第一个人是最先得到服务的人，也是最先离开队列的人。最终，你到达线前，结账后拿着你购买的一包物品离开商店。包里的东西没有特别的次序，且有些还是一样的。
你看到桌子上的一摞书或一叠纸了吗？很容易看到或拿走一摞东西最上面的一件，或者在一摞东西上面放一件新的东西。一摞东西也是按时间顺序组织的，最后放的在最上面，最先放的在最下面。
在桌子上，可以看到做事清单。清单中的每一项对你或重要或不重要。写这些项时，可能是按照它们的重要性排列的，也可能是按照字母序排列的。这个次序是你定的，清单只是写这些项的地方。
字典是单词及其定义的字母序列表。你在里面查找一个单词从而得到它的定义。如果你的字典是纸制印刷的，则字母序的组织方式能帮助你快速找到这个单词。如果你的字典是电子版的，则字母序的组织方式是隐式的，但它仍然能加快查找过程。
再来看计算机，文件是放到文件夹（或称目录）中的。每个文件夹又包含若干其他的文件夹或文件。这种组织类型是层次的。如果将它画成图，会得到一个类似家族树或公司内部部门图的东西。数据的这些组织方式是类似的，称为树。
最后来看看道路地图，你正用它来规划周末游。道路和城市的地图向你展示如何从一个地方到达另一个地方。通常会有几条不同的路。一条路可能路程更短些，另一条路可能所需时间更短。地图的组织方式称为图。
计算机程序也需要组织它们的数据，其组织方式类似于我们刚刚引用的例子，即程序可以使用栈、线性表、字典等。这些数据组织的方式表示为抽象数据类型。抽象数据类型（Abstract Data Type，ADT）是描述数据集（set）及数据上操作的规格说明。每个ADT说明存储什么数据及对数据进行什么操作。因为ADT不明示如何保存数据，也不说明如何实现操作，所以我们可以脱离程序设计语言来谈论ADT。相比之下，数据结构（data structure）是某种程序设计语言中ADT的一种实现。
集合（collection）是一个一般术语，是指包含一组对象的ADT。有些集合允许有重复项，而有些则不允许有重复项。
我们可以创建一个ADT包（bag），它由一个无序集合构成，其中允许有重复值。它好像是一个杂货店的袋子、一个午餐袋，或一个薯片袋。假定从薯片袋中拿出一片。你不知道薯片何时放入袋中。你不知道袋子中是否有另一片薯片，它的形状与刚拿走的那片一模一样。但你真的不在意这个。如果在意，就不会将薯片放入袋子中！
袋子中的物品没有次序，但有时你想让它们有次序。ADT可以以多种方式排列项的次序。例如，ADT线性表（list）对项进行编号。这样，线性表有第一项、第二项等。虽然可以将项添加到线性表的表尾，但也可以将项添加到线性表的表头，或者在两项的中间。这样操作后新加项后面的项需要重新编号。另外，可以删除线性表指定位置的项。所以线性表中项的位置并不能表明这个项是何时添加进来的。注意，线性表不决定项的放置位置。这件事由你来决定。
相反，ADT栈（stack）和队列（queue）按时间确定项的次序。当从栈中删除项时，删除的是最后添加的项。当从队列中删除项时，删除的是最早添加的项。所以，栈像是一摞书。你可以拿走最上面的书，或者将另一本书放在这摞书的上面。队列像是一队人。人从队列前头离开，站队时站到最后。
如果项可以进行比较，有些ADT按排列的次序管理项。例如，字符串可以按字母序组织。例如，当在ADT有序表（sorted list）中添加项时，由ADT来确定这个项在有序表中的位置。你不用指明这个项的位置，而在ADT线性表中需要指明。
ADT字典（dictionary）含有项对，很像是字典中含有的单词及其定义。在这个例子中，单词充当关键字（key），用它来查找项。有些字典对项进行排序，有些字典没有排序。
ADT树（tree）根据层次组织项。例如，在家族树中，人与其孩子和父母相关联。ADT二叉查找树（binary search tree）按照层次和排序来组织项，这使得项的查找更容易。
ADT图（graph）是ADT树的推广，它按照项之间的关系而不是层次来组织。例如，道路图是一个图，展示的是城镇之间已有的道路和距离。
本书介绍如何使用并实现这些数据组织方式。本书假定你已经了解了Java，如果需要复习这方面的知识，附录对你很有用。附录A概述了编写适用于javadoc注释的方法。附录B复习了Java的基本语句。附录C讨论了类和方法的基础结构。附录D介绍了组成与继承的要点。最后，附录E介绍读和写外部文件的方法。附录B、C和E在本书的网站上（pearsonhighered.com/carrano）也能找到。可以根据需要下载并参考这些资料。本书中称为“Java插曲”的章节，集中讨论了与Java相关的内容，这些内容对你可能是全新的，包括如何处理异常。后面的序言中讨论了如何设计类、说明方法，以及写Java接口。使用接口和编写注释来说明方法，都是介绍ADT不可缺少的部分。
