算法中的基本數(shù)據(jù)結(jié)構(gòu)，從邏輯上分可劃分為兩大類：線性結(jié)構(gòu)股耽、非線性結(jié)構(gòu)根盒。
注：線性和非線性，不代表存儲結(jié)構(gòu)是線性或是非線性物蝙，這只是一種邏輯上的劃分郑象，比如可以用數(shù)組存儲二叉樹；一般而言茬末，有前驅(qū)和后繼的厂榛，屬線性結(jié)構(gòu)，比如數(shù)組和鏈表丽惭。
線性結(jié)構(gòu)
線性結(jié)構(gòu)有：數(shù)組击奶、棧、鏈表责掏、隊列柜砾；
數(shù)組（array）
數(shù)組幾乎在每種語言入門時都會學(xué)習(xí)到，這里不再專門介紹换衬；
棧
"棧" 這個名稱痰驱，可類比于一組物體的堆疊证芭，比如一摞書（更直觀的類比，如將子彈壓入彈夾担映，最后壓入的最先射出）废士。
棧也是一種受限的序列，只能夠操作棧頂蝇完，不管入棧還是出棧官硝，都是在棧頂操作。
計算機(jī)科學(xué)中短蜕，棧 (stack) 是一種抽象數(shù)據(jù)類型氢架，用于表示元素的集合，具有兩種主要操作：
- push, 添加元素到棧的頂端（末尾）朋魔；
- pop, 移除棧最頂端（末尾）的元素岖研；
以上兩種操作可簡單概括為后進(jìn)先出 (LIFO = last in, first out)；
此外警检，應(yīng)有一個 peek 操作用于訪問棧當(dāng)前頂端（末尾）的元素（只返回不彈出）缎玫。
隊列（queue）
隊列，這個名稱解滓，可類比為現(xiàn)實(shí)生活中的排隊（不插隊的那種）；
計算機(jī)科學(xué)中筝家，隊列 是一種特殊的抽象數(shù)據(jù)類型集合洼裤，集合中的實(shí)體按順序保存。
和數(shù)組不同溪王，隊列是一種受限的序列腮鞍；
受限就受限于它只能操作 隊尾和隊首，并只能在隊尾添加元素莹菱，在隊首刪除元素移国，不像數(shù)組可以任意操作。
隊列作為一種常見數(shù)據(jù)結(jié)構(gòu)道伟，有著非常廣泛的應(yīng)用迹缀， 比如消息隊列。
隊列的基本操作有兩種：
向隊列的末端位置添加實(shí)體蜜徽，稱為入隊祝懂；
從隊列的前端位置移除實(shí)體，稱為出隊拘鞋。
隊列中的元素先進(jìn)先出 FIFO (first in, first out) ：
隊列的應(yīng)用
做過性能優(yōu)化的朋友砚蓬，對于 “HTTP 1.1 的隊頭阻塞問題” 應(yīng)該不會陌生；
具體來說就是 HTTP2 解決了 HTTP1.1 中的隊頭阻塞問題盆色。
什么是 HTTP1.1 的隊頭阻塞問題灰蛙，以及 HTTP2 怎么解決的祟剔，這里簡單說下：
其實(shí)隊頭阻塞是一個專有名詞，不僅僅在 HTTP 中存在摩梧，交換器等其他地方也會涉及這個問題物延；
實(shí)際上引起這個問題的根本原因是使用了隊列這種數(shù)據(jù)結(jié)構(gòu)。
HTTP 協(xié)議規(guī)定障本， 對于同一個 tcp 連接教届，所有的 http1.0 請求放入隊列中，只有前一個請求的響應(yīng)收到了驾霜，才能發(fā)送下一個請求案训，這個時候就發(fā)生了阻塞，并且這個阻塞主要發(fā)生在客戶端粪糙。
就好比等紅綠燈强霎，即使旁邊的綠燈亮了，你當(dāng)前所在的車道依然是紅燈蓉冈，你還是不能走城舞，還是要等著。
HTTP/1.1 的改進(jìn)
在HTTP/1.0 中每一次請求都需要建立一個 TCP 連接寞酿，請求結(jié)束后立即斷開連接家夺；
在HTTP/1.1 中，每一個連接都默認(rèn)是長連接 (persistent connection)伐弹；
對于同一個 tcp 連接拉馋，允許一次發(fā)送多個 http1.1 請求，也就是說惨好，不必等前一個響應(yīng)收到煌茴，就可以發(fā)送下一個請求了；
這樣就解決了 http1.0 的客戶端的隊頭阻塞日川，這也就是HTTP/1.1中管道 (Pipeline)的概念了蔓腐。
依然存在的問題
但是，HTTP.1 規(guī)定龄句，服務(wù)器端的響應(yīng)（response）要根據(jù)請求被接收的順序排隊回论；
也就是說，先接收到的請求分歇，其對應(yīng)的響應(yīng)也要先發(fā)送透葛。
這樣造成的問題是，如果最先收到的請求的處理時間長的話卿樱，響應(yīng)生成也慢僚害，就會阻塞已經(jīng)生成了的響應(yīng)的發(fā)送，這也會造成隊頭阻塞∪希可見靶草，HTTP1.1 的隊頭阻塞問題依然沒解決，不過是將問題從 客戶端 轉(zhuǎn)嫁到了 服務(wù)器端岳遥。
HTTP/2 相比于 HTTP/1.1 的改進(jìn)
為了解決HTTP/1.1中的服務(wù)端隊首阻塞奕翔，HTTP/2采用了二進(jìn)制分幀 和 多路復(fù)用 等方法。
幀是HTTP/2數(shù)據(jù)通信的最小單位浩蓉。在 HTTP/1.1 中數(shù)據(jù)包是文本格式派继，而 HTTP/2 的數(shù)據(jù)包是二進(jìn)制格式的，也就是二進(jìn)制幀捻艳。
采用幀的傳輸方式可以將請求和響應(yīng)的數(shù)據(jù)分割得更小驾窟，且二進(jìn)制協(xié)議可以被高效解析；
HTTP/2中认轨，同域名下的所有通信都在單個連接上完成绅络，該連接可以承載任意數(shù)量的雙向數(shù)據(jù)流；
每個數(shù)據(jù)流都以消息的形式發(fā)送嘁字，而消息又由一個或多個幀組成恩急，多個幀之間可以亂序發(fā)送，根據(jù)幀首部的流標(biāo)識在客戶端重新組裝纪蜒。
多路復(fù)用衷恭，替代了原來的隊列和阻塞機(jī)制：
在HTTP/1.1中，并發(fā)多個請求需要多個 TCP 鏈接纯续，且單個域名有 6-8 個 TCP 鏈接請求的限制（瀏覽器端做的限制随珠，不同瀏覽器的數(shù)量也可能不同）；
在HTTP/2中杆烁，同一域名下的所有通信在單個鏈接完成，僅占用一個 TCP 鏈接简卧，且在這一個鏈接上可以并行請求和響應(yīng)兔魂，互不干擾；
非線性結(jié)構(gòu)
非線性結(jié)構(gòu)有：樹举娩、圖析校；
樹
樹的遍歷方式有【前中后序遍歷】和層次遍歷，很多人對前中后這三種遍歷方式的印象比較模糊铜涉，其實(shí)換個方式就很好理解智玻，也容易記住：
所謂的【前中后】其實(shí)指的是遍歷時的根節(jié)點(diǎn)的位置芙代，其他位置按照先左后右的順序排列即可吊奢。
前序遍歷：根左右；
中序遍歷：左根右纹烹；
后序遍歷：左右根页滚；
樹的重要性質(zhì)
1召边、如果有n個頂點(diǎn)，則有 n-1 條邊裹驰；
2隧熙、任一子節(jié)點(diǎn)到達(dá)根節(jié)點(diǎn)的路徑【唯一】，且路徑長度為節(jié)點(diǎn)所處的深度幻林；
二叉樹
二叉樹是節(jié)點(diǎn)不超過二的樹贞盯，是樹的一種特殊子集，屬于被限制的樹結(jié)構(gòu)沪饺，有意思的是躏敢，它卻能夠表示和實(shí)現(xiàn)所有的樹；
二叉樹是LC的主要考點(diǎn)之一随闽，以下為和其相關(guān)的題目列表：
- LC-94.binary-tree-inorder-traversal
- LC-102.binary-tree-level-order-traversal
- LC-103.binary-tree-zigzag-level-order-traversal
- LC-144.binary-tree-preorder-traversal
- LC-145.binary-tree-postorder-traversal
- LC-199.binary-tree-right-side-view
真·二叉樹
所有節(jié)點(diǎn)的度數(shù)只能是偶數(shù)父丰，即0或2；
堆
堆掘宪，其實(shí)是一種優(yōu)先級隊列蛾扇，一種典型的實(shí)現(xiàn)就是二叉堆，也是最澄汗觯考的類型镀首。
二叉堆的特點(diǎn)
1、最小堆（min heap）：如果P是C的一個父節(jié)點(diǎn)鼠次，那么P的key或value應(yīng)小于等于C對應(yīng)的值更哄；基于這個性質(zhì)，可以得出結(jié)論腥寇，堆頂元素一定是最小的成翩；
一般我們可以利用此特性，求最小值或第k小值赦役。
2麻敌、最大堆（max heap）：和最小堆相反，P的key或value應(yīng)大于等于C對應(yīng)的值掂摔。
二叉堆相關(guān)考題：
- LC-295.find-median-from-data-stream
注：優(yōu)先隊列不只是【堆】這一種术羔，還要更為復(fù)雜的，但原理類似乙漓。
二叉查找樹
二叉查找樹（Binary Search Tree）级历，又叫做 Binary Sort Tree（二叉排序樹），俗稱叭披，二叉搜索樹寥殖。
二叉查找樹性質(zhì)如下：
- 若
左子樹不為空，則左子樹下的所有節(jié)點(diǎn)的值，均小于其根節(jié)點(diǎn)的值扛禽； - 若
右子樹不為空锋边，則右子樹下的所有節(jié)點(diǎn)的值，均大于其根節(jié)點(diǎn)的值编曼； - 左右子樹也均為二叉查找樹豆巨；
- 沒有鍵值相等的節(jié)點(diǎn)；
對于一個二叉查找樹掐场，常規(guī)操作有查找往扔、插入、刪除熊户、尋找父節(jié)點(diǎn)萍膛、求最大最小值等。
之所以將其命名為查找樹嚷堡，是因?yàn)槠浞浅＿m合查找蝗罗。
舉個栗子，如下一棵二叉查找樹蝌戒，愈查找節(jié)點(diǎn)值小于且最接近 58 的節(jié)點(diǎn)串塑，搜索的流程如圖：
[圖片上傳失敗...(image-1c4a10-1653623219302)]
二叉查找樹還有一個特性是： 中序遍歷的結(jié)果，是一個有序數(shù)組北苟，有時候我們可以利用到這個性質(zhì)桩匪。
LC-相關(guān)題目：
- 98.validate-binary-search-tree
二叉平衡樹
平衡樹是計算機(jī)科學(xué)中的一類數(shù)據(jù)結(jié)構(gòu)，是一種改進(jìn)后的二叉查找樹友鼻，一般來講傻昙，二叉查找樹的查詢復(fù)雜度取決于目標(biāo)節(jié)點(diǎn)到根節(jié)點(diǎn)的距離，即樹的深度彩扔，因此當(dāng)節(jié)點(diǎn)的深度普遍較大時妆档，查詢的時間復(fù)雜度也會隨之提升。
為了實(shí)現(xiàn)更高效的查詢虫碉，就誕生了平衡樹贾惦。
這里所說的平衡，指的是所有葉子的深度趨于平衡蔗衡，廣義上指的是在樹上所有可能的查找的均攤復(fù)雜度更低纤虽。
一些數(shù)據(jù)庫的引擎使用的就是這種數(shù)據(jù)結(jié)構(gòu)乳绕，其目標(biāo)是為了將查詢的時間復(fù)雜度降到 logn绞惦，可以簡單理解為，樹在數(shù)據(jù)結(jié)果層面實(shí)現(xiàn)了二分查找算法洋措。
二叉平衡樹的基本操作
- 旋轉(zhuǎn)
- 插入
- 刪除
- 查詢前驅(qū)
- 查詢后繼
AVL 樹（大致了解就好）
AVL樹济蝉，得名于它的兩個發(fā)明者的名字首字母，是最早被發(fā)明的自平衡二叉查找樹，其任一節(jié)點(diǎn)對應(yīng)的兩棵子樹的最大高度差為1王滤，因此它也被稱為高度平衡樹贺嫂。
AVL樹本質(zhì)上還是一棵二叉搜索樹，它的特點(diǎn)是：
1.其本身首先是一棵二叉搜索樹雁乡。
2.帶有平衡條件：每個結(jié)點(diǎn)的左右子樹的高度之差的絕對值（平衡因子）最多為1（1, 0, -1）第喳，所以帶有平衡因子 -2 或 2 的節(jié)點(diǎn)就會被認(rèn)為是不平衡的，需要重新平衡這棵樹踱稍。
也就是說曲饱，AVL樹，本質(zhì)上是自帶了平衡功能的二叉查找樹珠月。
紅黑樹
又被稱為"對稱二叉 B 樹"扩淀，紅黑樹的結(jié)構(gòu)復(fù)雜，但它的操作有著良好的最壞情況運(yùn)行時間啤挎，并且在實(shí)踐中很高效：它可以在 O(logn) 時間內(nèi)完成查找驻谆，插入和刪除（n 是樹中元素的數(shù)目）。
字典樹（前綴樹）
又稱 Trie（[tra?]） 樹庆聘，典型應(yīng)用是統(tǒng)計場景胜臊，排序和保存大量的字符串（但并不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計掏觉。
它的優(yōu)點(diǎn)是：利用字符串的公共前綴來減少查詢時間区端，最大限度地減少無謂的字符串比較，查詢效率比哈希樹要高澳腹。
特性：
- 根節(jié)點(diǎn)不包含字符织盼，除根節(jié)點(diǎn)外的所有子節(jié)點(diǎn)都只包含一個字符；
- 將從根節(jié)點(diǎn)到某一子節(jié)點(diǎn)的路徑上的字符串聯(lián)起來酱塔，為該節(jié)點(diǎn)對應(yīng)的字符串沥邻；
- 每個節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。
LC-相關(guān)算法：
- LC-208.implement-trie-prefix-tree
- LC-211.add-and-search-word-data-structure-design
- LC-212.word-search-ii
