《數(shù)據(jù)結(jié)構(gòu)與算法之美》，王爭 著

標(biāo)簽：數(shù)據(jù)結(jié)構(gòu)、算法

第2章 數(shù)組、鏈表、棧和隊列

第一部分：數(shù)組

作者在數(shù)組這個小節(jié)，本書從工程或應(yīng)用的角度出發(fā)介紹了一些內(nèi)容：

• ?數(shù)組的定義（這一節(jié)的點評，下面統(tǒng)一說）

• ?尋址公式和隨機訪問特性：其中特別指出數(shù)組中定位操作的時間復(fù)雜度是O(1)，而不是查找操作的時間復(fù)雜度是O(1)。

• 低效的插入和刪除操作

• 警惕數(shù)組訪問越界問題。這個內(nèi)容有意思，喜歡動手運行程序的讀者，可以把代碼執(zhí)行一下，看看是否如作者所說。

• 容器能否完全替代數(shù)組：比較了編程語言提供的容器類和數(shù)組的適用性。

• 數(shù)據(jù)結(jié)構(gòu)中的數(shù)組和編程語言中的數(shù)組的區(qū)別：作者簡單描述了C/C++、Java和JavaScript三種編程語言中數(shù)組數(shù)據(jù)類型的區(qū)別。

?本節(jié)點評：介紹幾種經(jīng)典編程語言中容器、和數(shù)組數(shù)據(jù)類型的區(qū)別，以及和數(shù)據(jù)結(jié)構(gòu)中數(shù)組的區(qū)別非常好，從工程和應(yīng)用的角度，可以豐富數(shù)據(jù)結(jié)構(gòu)一般教材的不足（一般教材不注重應(yīng)用性），對編程學(xué)習(xí)者，理論和實際都很重要，讓數(shù)據(jù)結(jié)構(gòu)能接地氣。

?文中有段話應(yīng)該是作者的感悟，也是我很喜歡的，推薦給讀者：“數(shù)據(jù)結(jié)構(gòu)和算法的魅力就在于此，很多時候我們并不需要死記硬背某個數(shù)據(jù)結(jié)構(gòu)或算法，而是要學(xué)習(xí)其背后的思想和處理技巧，這些東西才是最有價值的。如果讀者細心留意，就會發(fā)現(xiàn)，無論是在軟件開發(fā)還是架構(gòu)設(shè)計中，總能找到數(shù)據(jù)結(jié)構(gòu)和算法的影子”

?下面我表達一下個人的觀點

數(shù)組這個詞，在數(shù)據(jù)結(jié)構(gòu)、算法、和程序設(shè)計、編程軟件開發(fā)這些領(lǐng)域中，經(jīng)常出現(xiàn)，大家對數(shù)組的理解一般都不會有大的出錯，但是這個詞因為歷史悠久且應(yīng)用廣泛，如果不搞清楚，對喜歡探究的初學(xué)者來說，為有一些困擾。

如果只是“數(shù)組”這個詞，它代表了太多東西，要學(xué)習(xí)和理解數(shù)組，其實要加上很多前提約束，這樣初學(xué)者就不會那么困惑了。

?在數(shù)據(jù)結(jié)構(gòu)領(lǐng)域里，線性結(jié)構(gòu)是一種邏輯數(shù)據(jù)，線性表、棧和隊列是具有線性結(jié)構(gòu)的抽象數(shù)據(jù)類型（抽象在這里強調(diào)的數(shù)據(jù)集的結(jié)構(gòu)關(guān)系）。在數(shù)據(jù)結(jié)構(gòu)領(lǐng)域，數(shù)組是一種物理數(shù)據(jù)結(jié)構(gòu)（物理在這里表示的是計算機可以支持或?qū)崿F(xiàn)的結(jié)構(gòu)），線性表可以基于數(shù)組來實現(xiàn)。

?在程序設(shè)計領(lǐng)域中，數(shù)組表示一組連續(xù)的內(nèi)存空間存儲具有相同類型的數(shù)據(jù)。在不同的編程語言中真的實現(xiàn)數(shù)組數(shù)據(jù)類型時，由于編程語言設(shè)計的理念不同，不同編程語言中的數(shù)組數(shù)據(jù)類型是不同的，也不是完全遵循數(shù)據(jù)結(jié)構(gòu)中的數(shù)組這個概念。而且隨著編程語言的發(fā)展，還出現(xiàn)了容器，容器可以說是抽象數(shù)據(jù)類型的實例化。利用C++ STL中的vector，可以認(rèn)為是線性表這種抽象數(shù)據(jù)類型的理念在C++中的實例化（不是數(shù)組的實例化）。

?理解了程序設(shè)計（編程語言）中數(shù)組和數(shù)據(jù)結(jié)構(gòu)中線性表（數(shù)組）的區(qū)別，

那么在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)部分時，為什么在數(shù)組中插入和刪除操作效率低，就不難理解了。如果在程序設(shè)計領(lǐng)域，在數(shù)組中插入一個新的元素（刪除一個元素），完全可以在O(1)的時間復(fù)雜度的方法實現(xiàn)。但是在數(shù)據(jù)結(jié)構(gòu)領(lǐng)域，線性表或數(shù)組（這兩個詞，在很多數(shù)據(jù)結(jié)構(gòu)教材中有點混用）因為要維持?jǐn)?shù)據(jù)集中的線性結(jié)構(gòu)特性，在插入和刪除時才需要移動部分元素的位置。

簡單說，如果只是程序設(shè)計中的數(shù)組，插入元素或刪除數(shù)組中的某個元素，是不需要移動其他元素的。但是如果是用程序設(shè)計編程語言的數(shù)組來實現(xiàn)線性表（或數(shù)組），那么，插入和刪除時才需要移動部分元素的位置。當(dāng)然這都是理論上的（或者稱為思想上的），到了具體的編程語言，程序設(shè)計中的數(shù)組理念，不同的編程語言可以針對編程語言自身的特點，進行相應(yīng)的調(diào)整，實現(xiàn)出不同的數(shù)組數(shù)據(jù)類型；數(shù)據(jù)結(jié)構(gòu)中的線性表（數(shù)組）理念，不同的編程語言可以實現(xiàn)出不同的數(shù)據(jù)類型或容器。

?二、鏈表

作者在鏈表這個小節(jié)，從工程或應(yīng)用的角度出發(fā)介紹了一些內(nèi)容：

• 鏈表的底層結(jié)構(gòu)：數(shù)組和鏈表的底層結(jié)構(gòu)區(qū)別

• 鏈表的定義和操作

• 鏈表的變形結(jié)構(gòu)：單鏈表、循環(huán)鏈表、雙向鏈表

• 鏈表和數(shù)組的性能對比

• 基于鏈表實現(xiàn)LRU緩存淘汰算法

• 作者總結(jié)了6個編寫鏈表相關(guān)代碼的技巧。這一部分重點推薦。具體內(nèi)容就不劇透了。

?三、棧

作者在棧這個小節(jié)，從工程或應(yīng)用的角度出發(fā)介紹了一些內(nèi)容：

• l棧的定義

• 順序棧和鏈?zhǔn)綏?/p>

• 支持動態(tài)擴容的順序棧

• 棧在函數(shù)調(diào)用中的應(yīng)用

• 棧在表達式求值中的應(yīng)用

• 棧在括號匹配中的應(yīng)用

• 如何用棧實現(xiàn)瀏覽器的前進、后退功能

?四、隊列

作者在隊列這個小節(jié)，從工程或應(yīng)用的角度出發(fā)介紹了一些內(nèi)容：

• 隊列的定義

• 順序隊列和鏈?zhǔn)疥犃?/p>

• 循環(huán)隊列

• 阻塞隊列和并發(fā)隊列

• 線程池如何處理請求一個線程

?一般的數(shù)據(jù)結(jié)構(gòu)教材中，棧和隊列都說很重要，但是，本書作者在棧和隊列部分介紹了很多應(yīng)用的場景，雖然篇幅和細節(jié)不多，但是對于初學(xué)者來說，開拓視野，以及比簡單地說教棧和隊列很有用很常用要更加打動讀者。

?