本书主要介绍传统的和现代的数据结构方面的知识，重点介绍问题的解决和软件的设计。从基础知识开始并贯穿全书，介绍并扩展了许多Java功能的应用，如类、对象、泛型、多态、包、接口、库中的类、继承、异常和线程等。还在整个讲解过程中使用统一建模语言（UML）类图来帮助建模并可视化对象、类、接口、应用程序及其相互关系。

JAVA面向对象数据结构编程经典教程，受到万千读者口碑检验！专业的人写专业的书给专业的读者！重印多次全新再造，去芜存菁，重写了大部分资料，另外新增大量数据结构相关键资料，帮助你深度掌握JAVA面向对象数据结构！

[ 美］内尔·黛尔 Nell Dale 得克萨斯大学奥斯汀分校计算机科学博士。她自 1975 年以来，一直在得克萨斯大学奥斯汀分校任教，同时专注于计算机科学教育、写作。出版或参与出版过的专著有《Computer Science Illuminated》《Programming and Problem Solving withC : Brief Edition》《C Plus Data Structures》等。 [ 美］奇普·威姆斯 Chip Weems 美国马萨诸塞大学阿默斯特分校计算机科学专业副教授。在过去的 20 多年中，他教授了入门编程、软件工程、计算机体系结构和并行处理等课程。自 1986 年以来，他与其他人合作编写了 13 本教科书，帮助 100 多万学生学习计算机编程。他的书已被译成法语、西班牙语和俄语。现在，他从事计算机体系结构、编译器、并行处理和编译器体系结构协同优化方面的研 究。出版或参与出版的专著有《Turbo Pascal》《Programmingand Problem Solving with C 》《Programming inC 》《C Plus Data Structures》等。

Chapter 1  知识整理 1.1  类、对象和应用程序  类  统一方法  对象  应用程序  1.2  组织类  继承  包  1.3  异常  处理异常状况  异常与类：实例  1.4  数据结构  非独立实现的结构  独立实现结构  数据结构的含义？  1.5  基本结构化机制  内存  引用  数组  1.6  算法比较：增长阶分析  测算法的时间效率  情况复杂度  输入值的大小  算法比较  66 增长顺序  68 选择排序算法  69 常见的增长阶  72   小结  73   习题  74 Chapter 2  抽象数据类型—栈  2.1  抽象  信息隐藏  数据抽象  数据层次  前置条件和后置条件  Java接口  基于接口的多态性  2.2  栈  栈的操作  栈的用法  2.3  集合元素  常用集合  2.4  栈接口  异常情况  接口  应用实例  2.5  基于数组的栈实现  ArrayBoundedstack类  栈操作的定义  ArrayListStack类  2.6  应用程序：平衡表达式  平衡类  应用程序  软件架构  2.7  链表  数组与链表  LLNode类  链表操作  2.8  基于链接的栈  LinkedStack类  压栈操作  弹栈操作  其他栈操作  比较栈的实现方式  2.9  应用程序：后缀表达式评估器 讨论  后缀表达式求值  后缀表达式求值算法  错误处理  PostFixEvaluator类  PFixCLI类  2.10  栈变体  重新审视栈抽象数据类型  Java栈类和集合框架    小结    习题  Chapter 3  递归  3.1  递归定义、算法和程序  递归定义 递归计算  递归程序  阶乘的迭代解决方案  3.2  三个问题  验证递归算法  确定输入限制  编写递归方法  调试递归方法  3.3  数组的递归处理  二分查找  3.4  链表的递归处理  链表的递归性质 链表遍历  链表转换  …… 11.5  查找  顺序查找  高概率排序  有序集合  哈希法    小结    习题      附录A    附录B    附录C    附录D    术语表    索引

抽象数据类型—队列 知识目标 你可以 在抽象层次描述队列和其实现 定义队列接口 描述用数组实现队列操作的算法 比较基于数组实现队列的固定队头和浮动队头方法 说明如何用数组实现无界队列 描述用链表实现队列操作的算法 用增长阶分析描述及比较队列算法的效率 定义队列中元素的间隔时间、服务时间、周转时间和等待时间 说明并发线程如何互相干扰、引发出错，以及如何预防该干扰 技能目标 你可以 用数组实现有界队列抽象数据类型（ADT） 用数组实现无界队列ADT 用链表实现无界队列ADT 绘制图表表示特定队列实现的队列操作效果 使用队列ADT作为应用程序的一部分 给定到达时间和服务要求，计算队列元素的周转时间和等待时间 用队列模拟系统调研真实世界中的队列属性 实现一个程序，它能正确使用线程以利用问题解决方案内置的平行性 本章我们将讨论队列。在逻辑上队列与栈相对应，栈属于“后进先出”结构，而 队列属于“先进先出”结构。在队列中时间最长的元素就是最先移除的元素。与栈 一样，队列有多种与系统编程有关的重要用法，而且该结构也适用于其他多种应用 程序。 我们把队列当成一种抽象数据类型，从抽象层次、应用层次和实现层次来对待。 在抽象层次，队列用Java接口定义。我们将讨论数种队列应用程序，特别是探讨如何 用队列确定某个字符串是否属于回文，并调研真实世界中的队列属性。我们将用两种 基本方法实现队列：数组和链表。除了用数组实现有界队列之外，我们也会学习如何 用数组实现无界队列。与我们处理视图的正常顺序有所不同，本章的最后一节讨论了 如何使用队列来保存旨在执行并行的任务，而如果这种并行性能够用于提高性能，我 们该如何使用Java来妥善利用并列。 4.1  队列 在Chapter 2中学习的栈结构，通常是在同一端进行元素添加和移除。但如果我们 需要介绍一种有不同操作方式的集合，又该怎么办呢？假设我们模拟洗车场洗车，车 辆从车场的一头进去，从另一头出来。元素从一端进入，再从相反的另一端出来的数 据结构称为队列。队列数据结构，就跟洗车场一样，其特点就是最先进去的元素（车 辆）是最先出来的元素（车辆）。 这种队列的基本形式存在数种变体，为了进行区别，我们一般引用先进先出的队 列。其他队列版本将在第4.7节“队列变体”和Chapter 9“抽象数据类型－优先级队 列”中进行介绍。现在我们把注意力集中在队列的常见版本，即一般所说的“队列” 是指先进先出的队列。与栈的情况一样，我们从三个层次把队列视为一种抽象数据类 型：抽象、实现和应用层次。 队列操作 书店的例子暗示了可以应用于队列的两种操作。首先，我们可以在队尾添加新元 素，这个操作叫入队（enqueue）；其次，我们可以从队头移除元素，这个操作叫出队 （dequeue）。图4.2用方块模拟队列元素，向我们展示了上述操作对队列产生的影响。 与栈操作的压栈和退栈不一样，队列的添加和移除操作没有标准的名称。 enqueue 操作有时也会叫enq、 enque、 add（添加）或者insert（插入）， dequeue的别称也有 deq、 deque、 remove（移除）、或serve。 使用队列 Chapter 2中讨论了操作系统和编译程序如何使用栈。同样地，队列也经常用于系 统编程。例如，某个操作系统通常备有随时可执行的处理队列，或者等待特定事件发 生便可执行的处理队列。 另一个例子是，计算机系统通常必须提供“存储区”，以存放在两个处理进程、两 个程序甚至两个系统之间传送的信息。这个存储区通常称为“缓存”，通常作为队列实 现。例如，如果一个邮件伺服器在同一时间收到大量邮件信息，这些信息会先存放在 缓存区，直到该邮件伺服器做好准备处理这些信息。如果伺服器是按照信息到达的先 后顺序—先进先出的顺序进行处理的话，那么该缓存就属于队列。 很多其他应用程序在处理之前都要先存储请求。试想一下为顾客提供服务的应用 程序，比如出售飞机票或者电影票。这些应用程序通常会用队列来处理请求。 如书店的例子所示，软件所用的队列在现实世界中有相对应的例子。类似的还有 我们要排队买比萨、排队进影院、排队过收费站、排队坐过山车等。队列数据结构的 另一种重要应用是帮助我们模拟和分析现实世界的这些队列，有关这点我们将在第4.8 节“应用程序：平均等待时间”中的范例应用中介绍。 4.2  队列接口 本节将正式指定队列ADT。除了enqueue和dequeue操作与push、 pop和top不同之 外，队列所使用的基本方法与栈ADT一样： 队列都是泛型的—特定队列持有的对象类型在该队列实例化时由客户端指示。 定义支持队列的类在ch04.queues package中成组呈现。 提供观察函数操作size（大小），以便应用程序确定队列的大小。队列的大小对于 应用程序而言很重要，因为它意味着元素可以待在队列多久。 提供观察函数操作isEmpty（为空）和isFull（为满），以便客户端在合适的情况下 能够预防自己尝试从空队列中移除元素，或者在满队列中添加元素。 创建QueueUnderflowException（队列下溢异常）和QueueOverflowException（队列 溢出异常）两个类。 创建一个QueueInterface（队列接口），定义队列方法的特征。实现队列应该要实 现这个接口。 两个异常类的代码基本上与Chapter 2中栈所用的两个异常类的代码一样，所以这 里不予展示。与栈的情况一样，应用程序员能够在访问队列之前，决定使用isFull和 isEmpty两个观察函数来预防出现问题，或者应用程序能够尝试访问操作，“捕获并处 理”引发的异常。 以下为QueueInterface。该接口定义队列五个方法的特征—enqueue、 dequeue、 isEmpty、 isFull和size。