JAVA面向對象數據結構完全學習教程（簡體書）

本書主要介紹傳統的和現代的數據結構方面的知識，重點介紹問題的解決和軟件的設計。從基礎知識開始並貫穿全書，介紹並擴展了許多Java功能的應用，如類、對象、泛型、多態、包、接口、庫中的類、繼承、異常和線程等。我們還在整個講解過程中使用統一建模語言（UML）類圖來幫助建模並可視化對象、類、接口、應用程序及其相互關係。

Chapter 1 關於基礎知識的整理。綜述面向對象，強調了組織對象和類的機制。

Chapter 2 介紹了抽象數據類型棧（Stack），引入了抽象數據類型（abstract data type,ADT）的概念。

Chapter 3 討論了遞歸（Recursion），演示了如何使用遞歸解決編程問題。

Chapter 4 介紹了抽象數據類型隊列（Queue）。

Chapter 5 對抽象數據類型集合進行了定義。

Chapter 6 介紹了一個更具體的抽象數據類型—集合。

Chapter 7 介紹了二叉搜索樹抽象數據類型。

Chapter 8 講了映射（Map）抽象數據類型，映射抽象數據類型也叫符號表、字典或關聯數組。

Chapter 9 介紹了優先級隊列抽象數據類型，它與隊列密切相關，但具有不同的訪問協議。

Chapter 10 講了圖（Graph）抽象數據類型，包括實現方法和數種有關圖的重要算法（深度優先搜索、廣度優先搜索、路徑存在與否、Z短路徑和連通分量）。

Chapter 11 介紹/回顧了一些排序和查找算法。

內爾•黛爾 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》等。

丹尼爾•T•喬伊斯 Daniel T. Joyce

美國維拉諾瓦大學計算機科學系的副教授。喬伊斯的研究興趣是軟件工程，重點是軟件需求識別。此外，他還活躍於計算機科學教育界。

挺系統的一本書，關鍵的知識點都涵蓋到了，需要靜下心來系統學習。書的印刷很精良，圖片和代碼都很清晰，看起來賞心悅目，值得購買！
——北京銀牌讀者

看起來原版是作為高校教材的，有一些配套的教學PPT和課程大綱。我是買來自己學習的所以暫時用不到這些，不過能作為教材說明該書內容還是經得起檢驗的，附贈的源程序和資料都可以用，很滿意！

——河北銀牌讀者

還贈送了PPT，大概這書可以作為教師用書。內容很詳細，可以看出作者是對JAVA編程非常瞭解，講解廢話不多，語言精練，理解起來不費事。如果是看原版理解應該更能精准。

——江西銅牌讀者

書的內容很好，對於JAVA編程開發已經入門的人來說是很好的參考，初學者理解起來有些費勁。另外附帶贈送的資源很好，源代碼齊全。

——湖北金牌讀者

內容比較豐富，知識結構很系統，書中涉及資料非常豐富，內容專業，除了我這種開發者自學，也很適合這個專業的學生。

——陝西銀牌讀者讀者

抽象數據類型—隊列
知識目標
你可以
在抽象層次描述隊列和其實現
定義隊列接口
描述用數組實現隊列操作的算法
比較基於數組實現隊列的固定隊頭和浮動隊頭方法
說明如何用數組實現無界隊列
描述用鏈表實現隊列操作的算法
用增長階分析描述及比較隊列算法的效率
定義隊列中元素的間隔時間、服務時間、周轉時間和等待時間
說明併發線程如何互相干擾、引發出錯，以及如何預防該干擾
技能目標
你可以
用數組實現有界隊列抽象數據類型（ADT）
用數組實現無界隊列ADT
用鏈表實現無界隊列ADT
繪製圖表表示特定隊列實現的隊列操作效果
使用隊列ADT作為應用程序的一部分
給定到達時間和服務要求，計算隊列元素的周轉時間和等待時間
用隊列模擬系統調研真實世界中的隊列屬性
實現一個程序，它能正確使用線程以利用問題解決方案內置的平行性
本章我們將討論隊列。在邏輯上隊列與棧相對應，棧屬�“後進先出”結構，而
隊列屬�“先進先出”結構。在隊列中時間最長的元素就是最先移除的元素。與棧
一樣，隊列有多種與系統編程有關的重要用法，而且該結構也適用于其他多種應用
程序。
我們把隊列當成一種抽象數據類型，從抽象層次、應用層次和實現層次來對待。
在抽象層次，隊列用Java接口定義。我們將討論數種隊列應用程序，特別是探討如何
用隊列確定某個字符串是否屬�回文，並調研真實世界中的隊列屬性。我們將用兩種
基本方法實現隊列：數組和鏈表。除了用數組實現有界隊列之外，我們也會學習如何
用數組實現無界隊列。與我們處理視圖的正常順序有所不同，本章的最後一節討論了
如何使用隊列來保存旨在執行並行的任務，而如果這種並行性能夠用於提高性能，我
們該如何使用Java來妥善利用並列。
4.1? 隊列
在Chapter 2中學習的棧結構，通常是在同一端進行元素添加和移除。但如果我們
需要介紹一種有不同操作方式的集合，又該怎麼辦呢？假設我們模擬洗車場洗車，車
輛從車場的一頭進去，從另一頭出來。元素從一端進入，再從相反的另一端出來的數
據結構稱為隊列。隊列數據結構，就跟洗車場一樣，其特點就是最先進去的元素（車
輛）是最先出來的元素（車輛）。
這種隊列的基本形式存在數種變體，為了進行區別，我們一般引用先進先出的隊
列。其他隊列版本將在第4.7節“隊列變體”和Chapter 9“抽象數據類型－優先級隊
列”中進行介紹。現在我們把注意力集中在隊列的常見版本，即一般所說的“隊列”
是指先進先出的隊列。與棧的情況一樣，我們從三個層次把隊列視為一種抽象數據類
型：抽象、實現和應用層次。
……