數據結構概述
數據結構的分類
數組
在內存中的分配是連續的，通過下標來訪問
-
優點：
1、按照索引查詢元素速度快
2、按照索引遍歷數組方便 -
缺點：
1、數組的大小固定後就無法擴容了
2、數組只能存儲一種類型的數據
3、添加，刪除的操作慢，因爲要移動其他的元素。 -
適用場景：
頻繁查詢，對存儲空間要求不大，很少增加和刪除的情況。
鏈表
鏈表是物理存儲單元上非連續的、非順序的存儲單元；數據元素的邏輯順序通過鏈表的指針地址實現；
每個元素節點包含兩個域，一個是存儲元素的數據域 (內存空間)，另一個是指向下一個結點地址的指針域。根據指針的指向，鏈表能形成不同的結構，例如單鏈表，雙向鏈表，循環鏈表等
-
鏈表的優點：
鏈表是很常用的一種數據結構，不需要初始化容量，可以任意加減元素；
添加或者刪除元素時只需要改變前後兩個元素結點的指針域指向地址即可，所以添加，刪除很快； -
缺點：
因爲含有大量的指針域，佔用空間較大；
查找元素需要遍歷鏈表來查找，非常耗時。 -
適用場景：
數據量較小，需要頻繁增加，刪除操作的場景；
棧
是一種線性表，只能在一端進行操作，也就是棧頂，特點是先進後出，或者說後進先出；
在棧頂放入元素叫入棧，取出元素叫出棧
棧的結構就像一個集裝箱，越先放進去的東西越晚才能拿出來，所以，棧常應用於實現遞歸功能方面的場景，例如斐波那契數列。
隊列
也是一種線性表，不同的是，隊列可以在一端添加元素，在另一端取出元素，滿足先進先出；在一端添加元素叫入隊，在另一端取出元素叫出隊；
使用場景：因爲隊列先進先出的特點，在多線程阻塞隊列管理中非常適用。
樹
樹是一種數據結構，它是由n（n>=1）個有限節點組成一個具有層次關係的集合。把它叫做 「樹」 是因爲它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：
每個節點有零個或多個子節點；
沒有父節點的節點稱爲根節點；
每一個非根節點有且只有一個父節點；
除了根節點外，每個子節點可以分爲多個不相交的子樹；
在日常的應用中，我們討論和用的更多的是樹的其中一種結構，就是二叉樹。
二叉樹是樹的特殊一種，具有如下特點：
1、每個結點最多有兩顆子樹，結點的度最大爲2。
2、左子樹和右子樹是有順序的，次序不能顛倒。
3、即使某結點只有一個子樹，也要區分左右子樹。
二叉樹是一種比較有用的折中方案，它添加，刪除元素都很快，並且在查找方面也有很多的算法優化，所以，二叉樹既有鏈表的好處，也有數組的好處，是兩者的優化方案，在處理大批量的動態數據方面非常有用。
擴展：
二叉樹有很多擴展的數據結構，包括平衡二叉樹、紅黑樹、B+樹等，這些數據結構二叉樹的基礎上衍生了很多的功能，在實際應用中廣泛用到，例如mysql的數據庫索引結構用的就是B+樹，還有HashMap的底層源碼中用到了紅黑樹。
紅黑樹
從根節點到任意節點最多經歷2lg(n+1)步，因此紅黑樹的時間複雜度爲O(lgn)
根據性質3（如果一個節點爲紅，則其孩子必爲黑）可知，高度爲h的樹的黑高度至少爲h/2
所以 n >= 2^(h/2) - 1，所以lg(n+1) <= h/2，所以可知一個有n個內節點的紅黑樹高度至多爲2lg(n+1）
1、5個性質
- 根節點爲黑
- 每個節點不是紅就是黑
- 如果一個節點爲紅，則其孩子必爲黑
- 葉子節點爲黑
- 任意一結點到每個葉子結點的路徑都包含數量相同的黑結點。
2、爲什麼能夠自平衡
三種操作：左旋、右旋和變色。
- 左旋：以某個結點作爲支點(旋轉結點)，其右子結點變爲旋轉結點的父結點，右子結點的左子結點變爲旋轉結點的右子結點，左子結點保持不變。
- 右旋：以某個結點作爲支點(旋轉結點)，其左子結點變爲旋轉結點的父結點，左子結點的右子結點變爲旋轉結點的左子結點，右子結點保持不變。
- 變色：結點的顏色由紅變黑或由黑變紅。
散列表
散列表，也叫哈希表，是根據關鍵碼和值 (key和value) 直接進行訪問的數據結構，通過key和value來映射到集合中的一個位置，這樣就可以很快找到集合中的對應元素。
記錄的存儲位置=f(key)
這裏的對應關係 f 成爲散列函數，又稱爲哈希 (hash函數)，而散列表就是把Key通過一個固定的算法函數既所謂的哈希函數轉換成一個整型數字，然後就將該數字對數組長度進行取餘，取餘結果就當作數組的下標，將value存儲在以該數字爲下標的數組空間裏，這種存儲空間可以充分利用數組的查找優勢來查找元素，所以查找的速度很快。
堆
堆是一種比較特殊的數據結構，可以被看做一棵樹的數組對象，具有以下的性質：
堆中某個節點的值總是不大於或不小於其父節點的值；
堆總是一棵完全二叉樹。
將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。
堆的定義如下：n個元素的序列{k1,k2,ki,…,kn}當且僅當滿足下關係時，稱之爲堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)，滿足前者的表達式的成爲小頂堆，滿足後者表達式的爲大頂堆，這兩者的結構圖可以用完全二叉樹排列出來，
因爲堆有序的特點，一般用來做數組中的排序，稱爲堆排序。
圖
圖是由結點的有窮集合V和邊的集合E組成。其中，爲了與樹形結構加以區別，在圖結構中常常將結點稱爲頂點，邊是頂點的有序偶對，若兩個頂點之間存在一條邊，就表示這兩個頂點具有相鄰關係。
按照頂點指向的方向可分爲無向圖和有向圖：
圖是一種比較複雜的數據結構，在存儲數據上有着比較複雜和高效的算法，分別有鄰接矩陣 、鄰接表、十字鏈表、鄰接多重表、邊集數組等存儲結構
map、unordered_map和set、unordered_set
unordered_map、unordered_set中的unordered表明這兩個存儲結構是無序的，其實是基於散列表；查找效率較高
map、set的底層實現原理是紅黑樹，因此裏面的元素都是有序的。紅黑樹的每一個節點都代表着其中的一個元素。因此，對於它們進行的查找，刪除，添加等一系列的操作都相當於是對紅黑樹進行的操作。其中很多操作在lgn的時間複雜度下就可以實現，因此效率非常的高。