3. 1 抽象數(shù)據類型

????????抽象數(shù)據類型(abstractdata type, ADT)是帶有一組操作的一些對象的集合凝垛。抽象數(shù)據類型是數(shù)學的抽象；在ADT的定義中沒有地方提到關于這組操作是如何實現(xiàn)的任何解釋炸渡。 諸如表、集合丽已、圖以及與它們各自的操作一起形成的這些對象都可以被看做是抽象數(shù)據類型蚌堵。

????????Java類也考慮到ADT的實現(xiàn)，不過適當?shù)仉[藏了實現(xiàn)的細節(jié)沛婴。 這樣吼畏，程序中需要對ADT實施操作的任何其他部分可以通過調用適當?shù)姆椒▉磉M行。 如果由于某種原因需要改變實現(xiàn)的細節(jié)瘸味，那么通過僅僅改變執(zhí)行這些ADT操作的例程應該是很容易做到的宫仗。 這種改變對于程序的其余部分是完全透明的。

????????對于每種ADT并不存在什么法則來告訴我們必須要有哪些操作旁仿，這是一個設計決策藕夫。 錯誤處理和結構調整（在適當?shù)牡胤剑┮话阋踩Q于程序的設計者。 本章中將要討論的這三種數(shù)據 [ill 結構是ADT的 最基本的例子枯冈。我們將會看到它們中的每一種是如何以多種方法實現(xiàn)的毅贮，不過，當它們被正確地實現(xiàn)以后尘奏，使用它們的程序卻沒有必要知道它們是如何實現(xiàn)的滩褥。

3.2 表ADT

????????我們將處理形如A0 , A1, A2 …， AN-1的一般的表炫加。 我們說這個表的大小是N瑰煎。 我們將大小為0 的特殊的表稱為空表(emptylist)。

????????對于除空表外的任何表俗孝，我們說 Ai后繼 Ai-1 (或繼 Ai-1之后酒甸，i < N)并稱 Ai-1前驅 Ai (i >0)。表中的第一個元素是 A0赋铝，而 最后一個元素是 AN-1插勤。 我們將不定義 A0的前驅元，也不定義 AN-1的后繼元革骨。 元素Ai 在表中的位置為i + 1农尖。 為了簡單起見，我們假設表中的元素是整數(shù)良哲，但一般說來任意的復元素也是允許的（而且容易由Java泛型類處理）盛卡。

????????與這些“定義”相關的是要在表ADT上進行操作的集合。prinTList和makeEmpty是常用的操作筑凫，其功能顯而易見窟扑；find返回某一項首次出現(xiàn)的位置喇颁；insert和remove一般是從表的某個位置插入和刪除某個元素；而findKth則返回（作為參數(shù)而被指定的）某個位置上的元素嚎货。如果34,12, 52, 16, 12是一個表，則find(52)會返回2;insert(x, 2)可把表變成34,12, x, 52, 16, 12(如果我們插入到給定位置上的話）蔫浆；而remove(52)則又將該表變?yōu)?34, 12 , X, 16 , 12殖属。

3. 2. 1 表的簡單數(shù)組實現(xiàn)

????????對表的所有這些操作都可以通過使用數(shù)組來實現(xiàn)。雖然數(shù)組是由固定容量創(chuàng)建的瓦盛，但在需要的時候可以用雙倍的容量創(chuàng)建一個不同的數(shù)組洗显。它解決由于使用數(shù)組而產生的最嚴重的問題，即從歷史上看為了使用一個數(shù)組原环，需要對表的大小進行估計挠唆。而這種估計在Java或任何現(xiàn)代編程語言中都是不需要的。下列程序段解釋一個數(shù)組arr 在必要的時候如何被擴展（其初始長度為10):

????????數(shù)組的實現(xiàn)可以使得printList 以線性時間被執(zhí)行嘱吗，而findKth 操作則花費常數(shù)時間玄组，這正是我們所能夠預期的。不過谒麦，插入和刪除的花費卻潛藏著昂貴的開銷俄讹，這要看插入和刪除發(fā)生在什么地方。最壞的情形下绕德，在位置0的插入（即在表的前端插入）首先需要將整個數(shù)組后移一個位置以空出空間來患膛，而刪除第一個元素則需要將表中的所有元素前移一個位置，因此這兩種操作的最壞情況為O(N)耻蛇。平均來看踪蹬，這兩種操作都需要移動表的一半的元素，因此仍然需要線性時間臣咖。另一方面跃捣，如果所有的操作都發(fā)生在表的高端，那就沒有元素需要移動亡哄，而添加和刪除則只花費0(1 )時間枝缔。

????????存在許多情形，在這些情形下的表是通過在高端進行插入操作建成的蚊惯，其后只發(fā)生對數(shù)組的訪問（即只有findKth?操作）愿卸。在這種情況下，數(shù)組是表的一種恰當?shù)膶崿F(xiàn)截型。然而趴荸，如果發(fā)生對表的一些插入和刪除操作，特別是對表的前端進行宦焦，那么數(shù)組就不是一種好的選擇发钝。

3.2.2 簡單鏈表

????????為了避免插入和刪除的線性開銷顿涣，我們需要保證表可以不連續(xù)存儲，否則表的每個部分都可能需要整體移動酝豪。圖3-1 指出鏈表的一般想法涛碑。

????????鏈表由一系列節(jié)點組成，這些節(jié)點不必在內存中相連孵淘。每一個節(jié)點均含有表元素和到包含該元素后繼元的節(jié)點的鏈(link)蒲障。我們稱之為next 鏈。最后一個單元的next鏈引用null 瘫证。

????????為了執(zhí)行prinList或find(x), 只要從表的第一個節(jié)點開始然后用一些后繼的next鏈遍歷該表即可揉阎。這種操作顯然是線性時間的，和在數(shù)組實現(xiàn)時一樣背捌，不過其中的常數(shù)可能會比用數(shù)組實現(xiàn)時要大毙籽。findKth 操作不如數(shù)組實現(xiàn)時的效率高； findKth(i) 花費0(i) 的時間并以這種明顯的方式遍歷鏈表而完成毡庆。在實踐中這個界是保守的坑赡，因為調用findKth 常常是以（按i ) 排序后的方式進行。例如扭仁， findKth(2), findKth (3), findKth( 4) 以及findKth(6)可通過對表的一次掃描同時實現(xiàn)垮衷。

? ??????remove 方法可以通過修改一個next 引用來實現(xiàn)。圖3-2 給出在原表中刪除第三個元素的結果乖坠。

????????我們看到搀突，在實踐中如果知道變動將要發(fā)生的地方，那么向鏈表插入或從鏈表中刪除一項的操作不需要移動很多 的項熊泵，而只涉及常數(shù)個節(jié)點鏈的改變仰迁。在表的前端添加項或刪除第一項的特殊情形此時也屬于常數(shù)時間的操作，當然要假設到鏈表前端的鏈是存在的顽分。只要我們擁有到鏈表最后節(jié)點的鏈徐许，那么在鏈表末尾進行添加操作的特殊情形（即讓新的項成為最后一項）可以花費常數(shù)時間。因此卒蘸，典型的鏈表擁有到該表兩端的鏈雌隅。刪除最后一項比較復雜，因為必須找出指向最后節(jié)點的項缸沃，把它的next鏈改成null , 然后再更新持有最后節(jié)點的鏈恰起。在經典的鏈表中，每個節(jié)點均存儲到其下一節(jié)點的鏈趾牧，而擁有指向最后節(jié)點的鏈并不提供最后節(jié)點的前驅節(jié)點的任何信息检盼。

? ??????保留指向最后節(jié)點的節(jié)點的第3個鏈的想法行不通，因為它在刪除操作期間也需要更新翘单。我們的做法是吨枉，讓每一個節(jié)點持有一個指向它在表中的前驅節(jié)點的鏈蹦渣，如圖3-4所示，我們稱之為雙鏈表(doubly linked list)貌亭。

3. 3 Java Collections API中的表

????????在類庫中柬唯，Java語言包含有一些普通數(shù)據結構的實現(xiàn)。該語言的這一部分通常叫作Collections API圃庭。表ADT是在Collections API中實現(xiàn)的數(shù)據結構之一权逗。我們將在第4章看到其他一些數(shù)據結構。

3. 3. 1 Collecction接口

? ??????Collections API位于java.util包中冤议。集合(collection)的概念在Collection接口中得到抽象，它存儲一組類型相同的對象师坎。圖3-5顯示該接口一些最重要的部分（但一些方法未被顯示）恕酸。

????????在Collection接口中的許多方法所做的工作由它們的英文名稱可以看出.Collection接口擴展了Iterable接口。實現(xiàn)Iterable接口的那些類可以擁有增強 的for循環(huán)胯陋，該循環(huán)施于這些類之上以觀察它們所有的項蕊温。例如，圖3-6中的例程可以用來打印任意集合中的所有的項遏乔。這種方式的print的實現(xiàn)和當coll具有類型AnyType[]時能夠使用的相應的實現(xiàn)是完全相同的义矛，它們逐個字符都是一樣的。

3.3.2 Iterator接口

????????實現(xiàn)Iterable 接口的集合必須提供一個稱為iterator 的方法盟萨，該方法返回一個Iterator類型的對象凉翻。該Iterator 是一個在java.util 包中定義的接口，見圖3-7捻激。

????????Iterator 接口的思路是制轰，通過Iterator 方法，每個集合均可創(chuàng)建并返回給客戶一個實現(xiàn)Iterator 接口的對象胞谭，并將當前位置的概念在對象內部存儲下來垃杖。

????????每次對next 的調用都給出集合的（尚未見到的）下一項。因此丈屹，第1 次調用next 給出第1 項调俘，第2 次調用給出第2 項，等等旺垒。hasNe 立用來告訴圖3-7 java. u口1 包中的巨erator 接口是否存在下一項彩库。當編譯器見到一個正在用于Iterator?的對象的增強的for 循環(huán)的時候，它用對iterator 方法的那些調用代替增強的for 循環(huán)以得到一個Iterator?對象袖牙，然后調用next和hasNext侧巨。因此，前面看到的print例程由編譯器重寫鞭达，見圖3-8 所示司忱。

? ? ? ?由于Iterator 接口中的現(xiàn)有方法有限皇忿，因此，很難使用Iterator做簡單遍歷Collection以外的任何工作坦仍。Iterator接口還包含一個方法鳍烁，叫作remove 。該方法可以刪除由next最新返回的項（此后繁扎，我們不能再調用remove, 直到對next再一次調用以后）幔荒。雖然Collection接口也包含一個remove方法，但是梳玫，使用巨erator 的remove方法可能有更多的優(yōu)點爹梁。

????????Iterator的remove方法的主要優(yōu)點在于，Collection 的remove方法必須首先找出要被刪除的項提澎。如果知道所要刪除的項的準確位置姚垃，那么刪除它的開銷很可能要小得多。下一節(jié)我們將要看到一個例子盼忌，是在集合中每隔一項刪除一項积糯。這個程序用迭代器(iterator)很容易編寫，而且比用Collection的remove方法潛藏著更高的效率谦纱。

????????當直接使用Iterator(而不是通過一個增強的for循環(huán)間接使用）時看成， 重要的是要記住一個基本法則：如果對正在被迭代的集合進行結構上的改變（即對該集合使用add、remove或clear方法）跨嘉， 那么迭代器就不再合法（并且在其后使用該迭代器時將會有Concurrent－ModificationException異常被拋出）川慌。為避免迭代器準備給出某一項作為下一項( nextitem)而該項此后被刪除，或者也許一個新的項正好插入該項的前面這樣一些討厭的情形偿荷，有必要記住上述法則窘游。這意味著，只有在需要立即使用一個迭代器的時候跳纳，我們才應該獲取迭代器忍饰。然而，如果迭代器調用了它自己的remove方法寺庄，那么這個迭代器就仍然是合法的艾蓝。這是有時候我們更愿意使用迭代器的remove方法的第二個原因。

3.3.3 List接口斗塘、ArrayList類和LinkedList類

????????本節(jié)跟我們關系最大的集合就是表(list) , 它由java.util包中的List接口指定赢织。List接口繼承了Collection接口，因此它包含Collection接口的所有方法馍盟，外加其他一些方法于置。圖3-9解釋其中最重要的一些方法。

????????List ADT有兩種流行的實現(xiàn)方式贞岭。ArrayList類提供了List ADT的—種可增長數(shù)組的實現(xiàn)八毯。使用ArrayList的優(yōu)點在于搓侄，對get和set的調用花費常數(shù)時間。其缺點是新項的插入和現(xiàn)有項的刪除代價昂貴话速，除非變動是在ArrayList的末端進行讶踪。LinkedList類則提供了List ADT的雙鏈表實現(xiàn)。使用LinkedList的優(yōu)點在于泊交，新項的插入和現(xiàn)有項的刪除均開銷很小乳讥， 這里假設變動項的位置是已知的。這意味著廓俭，在表的前端進行添加和刪除都是常數(shù)時間的操作云石， 由此LinkedList更提供了方法addFirst 和removeFirst、addLast 和remove Last以及getFirst和getLast等以有效地添加研乒、刪除和訪問表兩端的項留晚。使用LinkedList的缺點是它不容易作索引，因此對get的調用是昂貴的告嘲，除非調用非常接近表的端點（如果對get的調用是對接近表后部的項進行，那么 搜索的進行可以從表的后部開始）奖地。

? ?

? ? ? ? 這里橄唬，ArrayList的運行時間是O(N),但對于LinkedList來說，其運行時間則是O(N2）参歹，因為在LinkedList中仰楚，對get的調用為 O(N)操作。 可是犬庇，要是使用一個增強的for循環(huán)僧界，那么它對任意List的運行時間都是O(N),因為迭代器將有效地從項到下一項推進。

????????對搜索而言臭挽，ArrayList和LinkedList都是低效的捂襟，對Collection的contains和remove兩個方法（它們都以 AnyType 為參數(shù)）的調用均花費線性時間。

????????在ArrayList中有一個容量的概念欢峰，它表示基礎數(shù)組的大小葬荷。 在需要的時候，ArrayList將自動增加其 容最以保證它至少具有表的大小纽帖。 如果該大小的早期估計存在宠漩，那么 ensureCapacity可以設置 容量為一個足夠大的最以避免數(shù)組 容量以后的擴展。再有懊直，trimToSize可以在所有的ArrayList添加操作完成之后使用以避免浪費空間扒吁。

3.4ArrayList類的實現(xiàn)

https://gitee.com/sunyunjie/DataStrycturesAndAlgorithmAnalysis

3.5LinkedList類的實現(xiàn)

https://gitee.com/sunyunjie/DataStrycturesAndAlgorithmAnalysis

3.6 棧ADT

3. 6. 1 棧模型

3. 6. 1 棧模型

????????棧(stack)是限制插入和刪除只能在一個位置上進行的表，該位置是表的末端室囊，叫作棧的頂(top)雕崩。對棧的基本操作有push(進棧）和pop(出棧）魁索，前者相當于插入，后者則是刪除最后插入的元素晨逝。最后插入的元素可以通過使用top例程在執(zhí)行pop之前進行考查蛾默。對空棧進行的pop或top一般被認為是棧ADT中的一個錯誤。另一方面捉貌，當運行push時空間用盡是一個實現(xiàn)限制支鸡，但不是ADT錯誤。

????????棧有時又叫作LIFO(后進先出）表趁窃。在圖3-33中描述的模型只象征著push是輸入操作而pop和top是輸出操作牧挣。普通的清空棧的操作和判斷是否空棧的測試都是棧的操作指令系統(tǒng)的一部分，但是醒陆，我們對棧所能夠做的瀑构，基本上也就是push和pop操作。

????????圖3-34表示在進行若干操作后的一個抽象的棧刨摩。一般的模型是寺晌，存在某個元素位于棧頂，而該元素是唯一的可見元素澡刹。

3.6.2 棧的實現(xiàn)

????????由于棧是個表共耍，因此任何實現(xiàn)表的方法都能實現(xiàn)棧茅郎。顯然，ArrayList和LinkedList都支持棧操作；99%的時間它們都是最合理的選擇拍柒。偶爾設計一種特殊目的的實現(xiàn)可能會更快（例如钞螟，如果被放到棧上的項屬于基本類型）勤众。因為棧操作是常數(shù)時間操作论寨，所以，除非在非常獨特的環(huán)境下胞锰，這是不可能產生任何明顯的改進的灾锯。對于這些特殊的時機，我們將給出兩個流飛盯行的實現(xiàn)方法嗅榕，一種方法使用鏈式結構挠进，而另一種方法則使用數(shù)組，二者均簡化了在ArrayList和LinkedList中的邏輯誊册，因此我們不提供代碼领突。

棧的鏈表實現(xiàn)

棧的第一種實現(xiàn)方法是使用單鏈表。通過在表的頂端插入來實現(xiàn)push,通過刪除表頂端元素實現(xiàn)pop案怯。top操作只是考查表頂端元素并返回它的值君旦。有時pop操作和top操作合二為一。

棧的數(shù)組實現(xiàn)

????????另一種實現(xiàn)方法避免了鏈而且可能是更流行的解決方案。由于模仿ArrayList的add 操作金砍，因此相應的實現(xiàn)方法非常簡單局蚀。與每個棧相關聯(lián)的操作是讓theArray和topOfStack, 對于空棧它是- 1 (這就是空棧初始化的做法）。為將某個元素x推入棧中恕稠，我們使topOfStack增1然后置theArray [topOfStack] = x琅绅。為了彈出棧元素，我們置返回值為theArray［topOfStack]然后使topOfStack減1鹅巍。

????????注意千扶，這些操作不僅以常數(shù)時間運行，而且是以非陈媾酰快的常數(shù)時間運行澎羞。在某些機器上，若在帶有自增和自減尋址功能的寄存器上操作敛苇，則（整數(shù)的）push和pop都可以寫成一條機器指令妆绞。最現(xiàn)代化的計算機將棧操作作為它的指令系統(tǒng)的一部分，這個事實強化了這樣一種觀念枫攀，即棧很可能是在計算機科學中在數(shù)組之后的最基本的數(shù)據結構括饶。

3. 7 隊列 ADT

????????像棧一樣，隊列(queue)也是表来涨。然而巷帝，使用隊列時插入在一端進行而刪除則在另一端進行。

3. 7. 1 隊列摸型

????????隊列的基本操作是enqueue(入隊）扫夜，但是在表的末端（ 叫作隊尾(rear))插入一個元素，和dequeue(出隊）驰徊，它是刪除（并返回）在表的開頭（叫作隊頭(front))的元素笤闯。圖3-37顯示一個隊列的圖3-37 隊列模型抽象模型。

3. 7.2 隊列的數(shù)組實現(xiàn)

????????如同棧的情形一樣棍厂，對于隊列而言任何的表的實現(xiàn)都是合法的颗味。像棧一樣，對于每一種操作牺弹，鏈表實現(xiàn)和數(shù)組實現(xiàn)都給出快速的O(1)運行時間浦马。隊列的鏈表實現(xiàn)是簡單直接的，我們留作練習张漂。下面討論隊列的數(shù)組實現(xiàn)晶默。

????????對于每一個隊列數(shù)據結構，我們保留一個數(shù)組theArray以及位置front和back,它們代表隊列的兩端航攒。我們還要記錄實際存在于隊列中的元素的個數(shù)currentSize磺陡。下圖表示處于某個中間狀態(tài)的一個隊列。

????????操作應該是清楚的。為使一個元素x 入隊（即執(zhí)行enqueue) , 我們讓currentSize 和back增1,然后置七heArray[back] = x币他。若使元素dequeue (出隊）坞靶， 我們置返回值為theArray[front]，且currentSize減1然后使front增1蝴悉。也可以有其他的方法（將在后面討論）≌靡酰現(xiàn)在論述錯誤檢測。

????????上述實現(xiàn)存在一個潛在的問題拍冠。經過10次enqueue后隊列似乎是滿了尿这，因為back現(xiàn)在是數(shù)組的最后一個下標，而下一次再enqueue就會是一個不存在的位置倦微。然而妻味，隊列中也許只存在幾個元素，因為若干元素可能已經出隊了欣福。像棧一樣责球，即使在有許多操作的情況下隊列也常常不是很大。

????????簡單的解決方法是拓劝，只要front或back到達數(shù)組的尾端雏逾，它就又繞回到開頭。下面諸圖顯示在某些操作期間的隊列情況郑临。這叫作循環(huán)數(shù)組(circular array)實現(xiàn)栖博。

????????實現(xiàn)回繞所需要的附加代碼是極小的（不過它可能使得運行時間加倍）。如果front或back增l導致超越了數(shù)組厢洞，那么其值就要重置到數(shù)組的第一個位置仇让。

小結

????????本章描述了一些ADT的概念，并且利用三種最常見的抽象數(shù)據類型(ADT)闡述了這種概念躺翻。 主要目的就是將抽象數(shù)據類型的具體實現(xiàn)與它們的功能分開丧叽。 程序必須知道操作都做些什么，但是如果不知道如何去做那就更好公你。

????????表踊淳、棧和隊列或許在全部計算機科學中是三個基本的數(shù)據結構，大量的例子證明了它們廣泛的用途陕靠。 特別地迂尝，我們看到棧是如何用來記錄過程和方法調用的，以及遞歸實際上是如何實 現(xiàn)的剪芥。 這對于我們的理解非常重要垄开，其原因不只因為它使得過程語言成為可能，而且還因為知 道遞歸的實現(xiàn)從而消除了圍繞其使用的大量謎團税肪。 雖然遞歸非常強大说榆，但是它并不是完全隨意 的操作虚吟；遞歸的誤用和亂用可能導致程序崩潰。