? 數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是計算機存儲和組織數(shù)據(jù)的的方式

1. 數(shù)組

在Java中，數(shù)組是用來存放同一種數(shù)據(jù)類型的集合，注意只能存放同一種數(shù)據(jù)類型。

數(shù)組的局限性分析：

　?、佟⒉迦肼?，對于無序數(shù)組，上面我們實現(xiàn)的數(shù)組就是無序的，即元素沒有按照從大到小或者某個特定的順序排列，只是按照插入的順序排列。無序數(shù)組增加一個元素很簡單，只需要在數(shù)組末尾添加元素即可，但是有序數(shù)組卻不一定了，它需要在指定的位置插入。

　　②、查找快，當然如果根據(jù)下標來查找是很快的。但是通常我們都是根據(jù)元素值來查找，給定一個元素值，對于無序數(shù)組，我們需要從數(shù)組第一個元素開始遍歷，知道找到那個元素。有序數(shù)組通過特定的算法查找的速度會比無需數(shù)組快，后面我們會講各種排序算法。

　?、?、刪除慢，根據(jù)元素值刪除，我們要先找到該元素所處的位置，然后將元素后面的值整體向前面移動一個位置。也需要比較多的時間。

　?、?、數(shù)組一旦創(chuàng)建后，大小就固定了，不能動態(tài)擴展數(shù)組的元素個數(shù)。如果初始化你給一個很大的數(shù)組大小，那會白白浪費內(nèi)存空間，如果給小了，后面數(shù)據(jù)個數(shù)增加了又添加不進去了。

很顯然，數(shù)組雖然查找快，但是插入和刪除都比較慢，所以我們不會用數(shù)組來存儲所有的數(shù)據(jù)，那有沒有什么數(shù)據(jù)結(jié)構(gòu)插入、查找、刪除都很快，而且還能動態(tài)擴展存儲個數(shù)大小

一維數(shù)組

如何定義數(shù)組

數(shù)據(jù)類型[] 數(shù)組名=new 數(shù)據(jù)類型[數(shù)組長度]；

? 數(shù)組類型 數(shù)組名[]=new 數(shù)組類型[數(shù)組長度]；

二維數(shù)組

定義

數(shù)組類型 [][] 數(shù)組名;

數(shù)組類型 數(shù)組 [][];

數(shù)組是可以再內(nèi)存中連續(xù)存儲多個元素的結(jié)構(gòu)。數(shù)組中的所有元素必須屬于相同的數(shù)據(jù)類型。

數(shù)組中的元素通過數(shù)組下標進行訪問，數(shù)組下標從0開始。

二維數(shù)組實際上是一個一維數(shù)組，它的每個元素又是一個一維數(shù)組。

使用Array類提供的方法可以方便地對數(shù)組中的元素進行排序、查詢等操作。

JDK1.5之后提供了增強for循環(huán)，可以用來實現(xiàn)對數(shù)組和集合中數(shù)據(jù)的訪問。

1. 棧

又稱為堆?；蚨询B，棧作為一種數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進行插入和刪除操作的特殊線性表。它按照先進后出的原則存儲數(shù)據(jù)，先進入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）。棧具有記憶作用，對棧的插入與刪除操作中，不需要改變棧底指針。

棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數(shù)為零時稱為空棧。插入一般稱為進棧（PUSH），刪除則稱為退棧（POP）。

　　由于堆疊數(shù)據(jù)結(jié)構(gòu)只允許在一端進行操作，因而按照后進先出（LIFO, Last In First Out）的原理運作。棧也稱為后進先出表。

這里以羽毛球筒為例，羽毛球筒就是一個棧，剛開始羽毛球筒是空的，也就是空棧，然后我們一個一個放入羽毛球，也就是一個一個push進棧，當我們需要使用羽毛球的時候，從筒里面拿，也就是pop出棧，但是第一個拿到的羽毛球是我們最后放進去的。

產(chǎn)生的問題：

　　①、上面棧的實現(xiàn)初始化容量之后，后面是不能進行擴容的（雖然棧不是用來存儲大量數(shù)據(jù)的），如果說后期數(shù)據(jù)量超過初始容量之后怎么辦？（自動擴容）

　?、?、我們是用數(shù)組實現(xiàn)棧，在定義數(shù)組類型的時候，也就規(guī)定了存儲在棧中的數(shù)據(jù)類型，那么同一個棧能不能存儲不同類型的數(shù)據(jù)呢？（聲明為Object）

③、棧需要初始化容量，而且數(shù)組實現(xiàn)的棧元素都是連續(xù)存儲的，那么能不能不初始化容量呢？（改為由鏈表實現(xiàn)）

1. 隊列

隊列（queue）是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。

隊列的數(shù)據(jù)元素又稱為隊列元素。在隊列中插入一個隊列元素稱為入隊，從隊列中刪除一個隊列元素稱為出隊。因為隊列只允許在一端插入，在另一端刪除，所以只有最早進入隊列的元素才能最先從隊列中刪除，故隊列又稱為先進先出（FIFO—first in first out）線性表。

　隊列分為：

　?、?、單向隊列（Queue）：只能在一端插入數(shù)據(jù)，另一端刪除數(shù)據(jù)。

　?、?、雙向隊列（Deque）：每一端都可以進行插入數(shù)據(jù)和刪除數(shù)據(jù)操作。

單向隊列實現(xiàn)

?、?、與棧不同的是，隊列中的數(shù)據(jù)不總是從數(shù)組的0下標開始的，移除一些隊頭front的數(shù)據(jù)后，隊頭指針會指向一個較高的下標位置，如下圖：

　?、凇⑽覀冊僭O(shè)計時，隊列中新增一個數(shù)據(jù)時，隊尾的指針rear 會向上移動，也就是向下標大的方向。移除數(shù)據(jù)項時，隊頭指針 front 也會向下移動。那么這樣設(shè)計好像和現(xiàn)實情況相反，比如排隊買電影票，隊頭的買完票就離開了，然后隊伍整體向前移動。在計算機中也可以在隊列中刪除一個數(shù)之后，隊列整體向前移動，但是這樣做效率很差。我們選擇的做法是移動隊頭和隊尾的指針。

　　③、如果向第②步這樣移動指針，相信隊尾指針很快就移動到數(shù)據(jù)的最末端了，這時候可能移除過數(shù)據(jù)，那么隊頭會有空著的位置，然后新來了一個數(shù)據(jù)項，由于隊尾不能再向上移動了，那該怎么辦呢？如下圖：

　　為了避免隊列不滿卻不能插入新的數(shù)據(jù)，我們可以讓隊尾指針繞回到數(shù)組開始的位置，這也稱為“循環(huán)隊列”。

雙向隊列

雙端隊列就是一個兩端都是結(jié)尾或者開頭的隊列，?隊列的每一端都可以進行插入數(shù)據(jù)項和移除數(shù)據(jù)項

優(yōu)先級隊列（priority queue）

是比棧和隊列更專用的數(shù)據(jù)結(jié)構(gòu)，在優(yōu)先級隊列中，數(shù)據(jù)項按照關(guān)鍵字進行排序，關(guān)鍵字最小（或者最大）的數(shù)據(jù)項往往在隊列的最前面，而數(shù)據(jù)項在插入的時候都會插入到合適的位置以確保隊列的有序。

　　優(yōu)先級隊列 是0個或多個元素的集合，每個元素都有一個優(yōu)先權(quán)，對優(yōu)先級隊列執(zhí)行的操作有：

　?。?）查找

　　（2）插入一個新元素

　?。?）刪除

　　一般情況下，查找操作用來搜索優(yōu)先權(quán)最大的元素，刪除操作用來刪除該元素 。對于優(yōu)先權(quán)相同的元素，可按先進先出次序處理或按任意優(yōu)先權(quán)進行。

　　這里我們用數(shù)組實現(xiàn)優(yōu)先級隊列，這種方法插入比較慢，但是它比較簡單，適用于數(shù)據(jù)量比較小并且不是特別注重插入速度的情況。

　　后面我們會講解堆，用堆的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)優(yōu)先級隊列，可以相當快的插入數(shù)據(jù)。

數(shù)組實現(xiàn)優(yōu)先級隊列，聲明為int類型的數(shù)組，關(guān)鍵字是數(shù)組里面的元素，在插入的時候按照從大到小的順序排列，也就是越小的元素優(yōu)先級越高。

　通過前面講的棧以及本篇講的隊列這兩種數(shù)據(jù)結(jié)構(gòu)，我們稍微總結(jié)一下：

　?、?、棧、隊列（單向隊列）、優(yōu)先級隊列通常是用來簡化某些程序操作的數(shù)據(jù)結(jié)構(gòu)，而不是主要作為存儲數(shù)據(jù)的。

　?、凇⒃谶@些數(shù)據(jù)結(jié)構(gòu)中，只有一個數(shù)據(jù)項可以被訪問。

　?、?、棧允許在棧頂壓入（插入）數(shù)據(jù)，在棧頂彈出（移除）數(shù)據(jù)，但是只能訪問最后一個插入的數(shù)據(jù)項，也就是棧頂元素。

　　④、隊列（單向隊列）只能在隊尾插入數(shù)據(jù)，對頭刪除數(shù)據(jù)，并且只能訪問對頭的數(shù)據(jù)。而且隊列還可以實現(xiàn)循環(huán)隊列，它基于數(shù)組，數(shù)組下標可以從數(shù)組末端繞回到數(shù)組的開始位置。

　?、?、優(yōu)先級隊列是有序的插入數(shù)據(jù)，并且只能訪問當前元素中優(yōu)先級別最大（或最?。┑脑亍?/p>

　?、蕖⑦@些數(shù)據(jù)結(jié)構(gòu)都能由數(shù)組實現(xiàn)，但是可以用別的機制（后面講的鏈表、堆等數(shù)據(jù)結(jié)構(gòu)）實現(xiàn)。

1. 鏈表

是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個（或兩個）節(jié)點里存到下一個（或上一個）節(jié)點的指針(Pointer)。

使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點，鏈表結(jié)構(gòu)可以充分利用計算機內(nèi)存空間，實現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈表失去了數(shù)組隨機讀取的優(yōu)點，同時鏈表由于增加了結(jié)點的指針域，空間開銷比較大。

單鏈表是鏈表中結(jié)構(gòu)最簡單的。一個單鏈表的節(jié)點(Node)分為兩個部分，第一個部分(data)保存或者顯示關(guān)于節(jié)點的信息，另一個部分存儲下一個節(jié)點的地址。最后一個節(jié)點存儲地址的部分指向空值。

單向鏈表

只可向一個方向遍歷，一般查找一個節(jié)點的時候需要從第一個節(jié)點開始每次訪問下一個節(jié)點，一直訪問到需要的位置。而插入一個節(jié)點，對于單向鏈表，我們只提供在鏈表頭插入，只需要將當前插入的節(jié)點設(shè)置為頭節(jié)點，next指向原頭節(jié)點即可。刪除一個節(jié)點，我們將該節(jié)點的上一個節(jié)點的next指向該節(jié)點的下一個節(jié)點。

雙端鏈表

1. 二叉樹

樹的每個節(jié)點最多只能有兩個子節(jié)點

查找某個節(jié)點，我們必須從根節(jié)點開始遍歷。

　?、?、查找值比當前節(jié)點值大，則搜索右子樹；

　　②、查找值等于當前節(jié)點值，停止搜索（終止條件）；

　?、?、查找值小于當前節(jié)點值，則搜索左子樹；

　 要插入節(jié)點，必須先找到插入的位置。與查找操作相似，由于二叉搜索樹的特殊性，待插入的節(jié)點也需要從根節(jié)點開始進行比較，小于根節(jié)點則與根節(jié)點左子樹比較，反之則與右子樹比較，直到左子樹為空或右子樹為空，則插入到相應(yīng)為空的位置，在比較的過程中要注意保存父節(jié)點的信息 及 待插入的位置是父節(jié)點的左子樹還是右子樹，才能插入到正確的位置。

刪除節(jié)點是二叉搜索樹中最復(fù)雜的操作，刪除的節(jié)點有三種情況，前兩種比較簡單，但是第三種卻很復(fù)雜。

　　1、該節(jié)點是葉節(jié)點（沒有子節(jié)點）

　　2、該節(jié)點有一個子節(jié)點

　　3、該節(jié)點有兩個子節(jié)點

　　下面我們分別對這三種情況進行講解。

　　①、刪除沒有子節(jié)點的節(jié)點

　　要刪除葉節(jié)點，只需要改變該節(jié)點的父節(jié)點引用該節(jié)點的值，即將其引用改為 null 即可。要刪除的節(jié)點依然存在，但是它已經(jīng)不是樹的一部分了，由于Java語言的垃圾回收機制，我們不需要非得把節(jié)點本身刪掉，一旦Java意識到程序不在與該節(jié)點有關(guān)聯(lián)，就會自動把它清理出存儲器。

刪除節(jié)點，我們要先找到該節(jié)點，并記錄該節(jié)點的父節(jié)點。在檢查該節(jié)點是否有子節(jié)點。如果沒有子節(jié)點，接著檢查其是否是根節(jié)點，如果是根節(jié)點，只需要將其設(shè)置為null即可。如果不是根節(jié)點，是葉節(jié)點，那么斷開父節(jié)點和其的關(guān)系即可。

　?、?、刪除有一個子節(jié)點的節(jié)點

　　刪除有一個子節(jié)點的節(jié)點，我們只需要將其父節(jié)點原本指向該節(jié)點的引用，改為指向該節(jié)點的子節(jié)點即可。

?、?、刪除有兩個子節(jié)點的節(jié)點

　　當刪除的節(jié)點存在兩個子節(jié)點，那么刪除之后，兩個子節(jié)點的位置我們就沒辦法處理了。既然處理不了，我們就想到一種辦法，用另一個節(jié)點來代替被刪除的節(jié)點，那么用哪一個節(jié)點來代替呢？

　　我們知道二叉搜索樹中的節(jié)點是按照關(guān)鍵字來進行排列的，某個節(jié)點的關(guān)鍵字次高節(jié)點是它的中序遍歷后繼節(jié)點。用后繼節(jié)點來代替刪除的節(jié)點，顯然該二叉搜索樹還是有序的。（這里用后繼節(jié)點代替，如果該后繼節(jié)點自己也有子節(jié)點，我們后面討論。）

　　那么如何找到刪除節(jié)點的中序后繼節(jié)點呢？其實我們稍微分析，這實際上就是要找比刪除節(jié)點關(guān)鍵值大的節(jié)點集合中最小的一個節(jié)點，只有這樣代替刪除節(jié)點后才能滿足二叉搜索樹的特性。

　　后繼節(jié)點也就是：比刪除節(jié)點大的最小節(jié)點。

6.紅黑樹

　　有如下兩個特征：

　?、?、節(jié)點都有顏色；

　?、?、在插入和刪除的過程中，要遵循保持這些顏色的不同排列規(guī)則。

　　第一個很好理解，在紅-黑樹中，每個節(jié)點的顏色或者是黑色或者是紅色的。當然也可以是任意別的兩種顏色，這里的顏色用于標記，我們可以在節(jié)點類Node中增加一個boolean型變量isRed，以此來表示顏色的信息。

　　第二點，在插入或者刪除一個節(jié)點時，必須要遵守的規(guī)則稱為紅-黑規(guī)則：

　　1.每個節(jié)點不是紅色就是黑色的；

　　2.根節(jié)點總是黑色的；

　　3.如果節(jié)點是紅色的，則它的子節(jié)點必須是黑色的（反之不一定）,(也就是從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)；

　　4.從根節(jié)點到葉節(jié)點或空子節(jié)點的每條路徑，必須包含相同數(shù)目的黑色節(jié)點（即相同的黑色高度）。

　　從根節(jié)點到葉節(jié)點的路徑上的黑色節(jié)點的數(shù)目稱為黑色高度，規(guī)則 4 另一種表示就是從根到葉節(jié)點路徑上的黑色高度必須相同。

注意：新插入的節(jié)點顏色總是紅色的，這是因為插入一個紅色節(jié)點比插入一個黑色節(jié)點違背紅-黑規(guī)則的可能性更小，原因是插入黑色節(jié)點總會改變黑色高度（違背規(guī)則4），但是插入紅色節(jié)點只有一半的機會會違背規(guī)則3（因為父節(jié)點是黑色的沒事，父節(jié)點是紅色的就違背規(guī)則3）。另外違背規(guī)則3比違背規(guī)則4要更容易修正。

紅黑樹和二叉樹的區(qū)別 ：

紅黑樹和之前所講的AVL樹類似，都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。自從紅黑樹出來后，AVL樹就被放到了博物館里，據(jù)說是紅黑樹有更好的效率，更高的統(tǒng)計性能。 紅黑樹和AVL樹的區(qū)別在于它使用顏色來標識結(jié)點的高度，它所追求的是局部平衡而不是AVL樹中的非常嚴格的平衡。AVL樹的復(fù)雜比起紅黑樹來說簡直是小巫見大巫。紅黑樹是真正的變態(tài)級數(shù)據(jù)結(jié)構(gòu)。

(AVL樹,平衡二叉樹)

7.哈希表

Hash表也稱散列表，也有直接譯作哈希表，Hash表是一種根據(jù)關(guān)鍵字值（key - value）而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。它基于數(shù)組，通過把關(guān)鍵字映射到數(shù)組的某個下標來加快查找速度，但是又和數(shù)組、鏈表、樹等數(shù)據(jù)結(jié)構(gòu)不同，在這些數(shù)據(jù)結(jié)構(gòu)中查找某個關(guān)鍵字，通常要遍歷整個數(shù)據(jù)結(jié)構(gòu)

哈希表（Hash table，也叫散列表），是根據(jù)關(guān)鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

?而當使用哈希表進行查詢的時候，就是再次使用哈希函數(shù)將key轉(zhuǎn)換為對應(yīng)的數(shù)組下標，并定位到該空間獲取value，如此一來，就可以充分利用到數(shù)組的定位性能進行數(shù)據(jù)定位

優(yōu)缺點

優(yōu)點：不論哈希表中有多少數(shù)據(jù)，查找、插入、刪除（有時包括刪除）只需要接近常量的時間即0(1）的時間級。實際上，這只需要幾條機器指令。

哈希表運算得非常快，在計算機程序中，如果需要在一秒種內(nèi)查找上千條記錄通常使用哈希表（例如拼寫檢查器)哈希表的速度明顯比樹快，樹的操作通常需要O(N)的時間級。哈希表不僅速度快，編程實現(xiàn)也相對容易。

如果不需要有序遍歷數(shù)據(jù)，并且可以提前預(yù)測數(shù)據(jù)量的大小。那么哈希表在速度和易用性方面是無與倫比的。

缺點：它是基于數(shù)組的，數(shù)組創(chuàng)建后難于擴展，某些哈希表被基本填滿時，性能下降得非常嚴重，所以程序員必須要清楚表中將要存儲多少數(shù)據(jù)（或者準備好定期地把數(shù)據(jù)轉(zhuǎn)移到更大的哈希表中，這是個費時的過程）。

（有個不錯的例子，點擊）

8. 堆

堆是一顆完全二叉樹，在這棵樹中，所有父節(jié)點都滿足大于等于其子節(jié)點的堆叫大根堆，所有父節(jié)點都滿足小于等于其子節(jié)點的堆叫小根堆。堆雖然是一顆樹，但是通常存放在一個數(shù)組中，父節(jié)點和孩子節(jié)點的父子關(guān)系通過數(shù)組下標來確定。

堆是弱序的，所以想要遍歷堆是很困難的，基本上，堆是不支持遍歷的。

　　對于查找，由于堆的特性，在查找的過程中，沒有足夠的信息來決定選擇通過節(jié)點的兩個子節(jié)點中的哪一個來選擇走向下一層，所以也很難在堆中查找到某個關(guān)鍵字。

因此，堆這種組織似乎非常接近無序，不過，對于快速的移除最大（或最小）節(jié)點，也就是根節(jié)點，以及能快速插入新的節(jié)點，這兩個操作就足夠了。