? 數(shù)據(jù)結構

數(shù)據(jù)結構是計算機存儲和組織數(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ù)結構插入批狐、查找、刪除都很快，而且還能動態(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ù)存儲多個元素的結構。數(shù)組中的所有元素必須屬于相同的數(shù)據(jù)類型食零。

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

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

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

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

1. 棧

又稱為堆椘瞪耍或堆疊恳谎，棧作為一種數(shù)據(jù)結構，是一種只能在一端進行插入和刪除操作的特殊線性表憋肖。它按照先進后出的原則存儲數(shù)據(jù)因痛，先進入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂岸更，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）鸵膏。棧具有記憶作用，對棧的插入與刪除操作中怎炊，不需要改變棧底指針谭企。

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

　　由于堆疊數(shù)據(jù)結構只允許在一端進行操作俄占，因而按照后進先出（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ù)后镊叁，隊頭指針會指向一個較高的下標位置，如下圖：

　∽叽ァ②晦譬、我們再設計時，隊列中新增一個數(shù)據(jù)時互广，隊尾的指針rear 會向上移動敛腌，也就是向下標大的方向。移除數(shù)據(jù)項時惫皱，隊頭指針 front 也會向下移動像樊。那么這樣設計好像和現(xiàn)實情況相反，比如排隊買電影票逸吵，隊頭的買完票就離開了凶硅，然后隊伍整體向前移動。在計算機中也可以在隊列中刪除一個數(shù)之后扫皱，隊列整體向前移動足绅，但是這樣做效率很差。我們選擇的做法是移動隊頭和隊尾的指針韩脑。

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

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

雙向隊列

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

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

是比棧和隊列更專用的數(shù)據(jù)結構宋下，在優(yōu)先級隊列中，數(shù)據(jù)項按照關鍵字進行排序辑莫，關鍵字最醒纭（或者最大）的數(shù)據(jù)項往往在隊列的最前面，而數(shù)據(jù)項在插入的時候都會插入到合適的位置以確保隊列的有序各吨。

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

　∩鹉恪（1）查找

　∷帕薄（2）插入一個新元素

　≌烟伞（3）刪除

　　一般情況下忌锯，查找操作用來搜索優(yōu)先權最大的元素限书，刪除操作用來刪除該元素 便锨。對于優(yōu)先權相同的元素呵曹，可按先進先出次序處理或按任意優(yōu)先權進行硝逢。

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

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

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

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

　⌒馗纭①涯竟、棧、隊列（單向隊列）空厌、優(yōu)先級隊列通常是用來簡化某些程序操作的數(shù)據(jù)結構庐船，而不是主要作為存儲數(shù)據(jù)的。

　〕案②筐钟、在這些數(shù)據(jù)結構中，只有一個數(shù)據(jù)項可以被訪問哮内。

　〉量谩③壮韭、棧允許在棧頂壓入（插入）數(shù)據(jù)，在棧頂彈出（移除）數(shù)據(jù)纹因，但是只能訪問最后一個插入的數(shù)據(jù)項喷屋，也就是棧頂元素。

　〔t恰、芡筒堋㈥犃校▎蜗蜿犃校┲荒茉陉犖膊迦霐?shù)據(jù)，對頭刪除數(shù)據(jù)惊畏，并且只能訪問對頭的數(shù)據(jù)恶耽。而且隊列還可以實現(xiàn)循環(huán)隊列，它基于數(shù)組颜启，數(shù)組下標可以從數(shù)組末端繞回到數(shù)組的開始位置偷俭。

　　⑤缰盏、優(yōu)先級隊列是有序的插入數(shù)據(jù)涌萤，并且只能訪問當前元素中優(yōu)先級別最大（或最小）的元素口猜。

　「合⑥、這些數(shù)據(jù)結構都能由數(shù)組實現(xiàn)济炎，但是可以用別的機制（后面講的鏈表川抡、堆等數(shù)據(jù)結構）實現(xiàn)。

1. 鏈表

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

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

單鏈表是鏈表中結構最簡單的蜡豹。一個單鏈表的節(jié)點(Node)分為兩個部分，第一個部分(data)保存或者顯示關于節(jié)點的信息溉苛，另一個部分存儲下一個節(jié)點的地址镜廉。最后一個節(jié)點存儲地址的部分指向空值。

單向鏈表

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

雙端鏈表

1. 二叉樹

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

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

　　①漱凝、查找值比當前節(jié)點值大疮蹦，則搜索右子樹；

　〉镅啤②挚币、查找值等于當前節(jié)點值，停止搜索（終止條件）扣典；

　　③慎玖、查找值小于當前節(jié)點值贮尖，則搜索左子樹；

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

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

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

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

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

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

　“兹取①全肮、刪除沒有子節(jié)點的節(jié)點

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

刪除節(jié)點，我們要先找到該節(jié)點呜投，并記錄該節(jié)點的父節(jié)點加匈。在檢查該節(jié)點是否有子節(jié)點。如果沒有子節(jié)點仑荐，接著檢查其是否是根節(jié)點雕拼，如果是根節(jié)點，只需要將其設置為null即可粘招。如果不是根節(jié)點啥寇，是葉節(jié)點，那么斷開父節(jié)點和其的關系即可洒扎。

　〖稹②、刪除有一個子節(jié)點的節(jié)點

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

『③邓线、刪除有兩個子節(jié)點的節(jié)點

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

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

　　那么如何找到刪除節(jié)點的中序后繼節(jié)點呢颤绕？其實我們稍微分析幸海，這實際上就是要找比刪除節(jié)點關鍵值大的節(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ū)別在于它使用顏色來標識結點的高度耸三，它所追求的是局部平衡而不是AVL樹中的非常嚴格的平衡乱陡。AVL樹的復雜比起紅黑樹來說簡直是小巫見大巫。紅黑樹是真正的變態(tài)級數(shù)據(jù)結構吕晌。

(AVL樹,平衡二叉樹)

7.哈希表

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

哈希表（Hash table匙瘪，也叫散列表），是根據(jù)關鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結構蝶缀。也就是說丹喻，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度翁都。這個映射函數(shù)叫做散列函數(shù)碍论，存放記錄的數(shù)組叫做散列表。

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

優(yōu)缺點

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

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

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

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

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

8. 堆

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

堆是弱序的骤竹，所以想要遍歷堆是很困難的帝牡，基本上，堆是不支持遍歷的蒙揣。

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

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