數(shù)據(jù)結(jié)構(gòu)：計(jì)算機(jī)存儲(chǔ)偶翅、組織數(shù)據(jù)的方式。程序員的目標(biāo)是為當(dāng)前的問題選擇最優(yōu)的數(shù)據(jù)結(jié)構(gòu)碉渡。
八種數(shù)據(jù)結(jié)構(gòu)：數(shù)組聚谁，棧，鏈表滞诺，隊(duì)列形导，堆，圖习霹，樹朵耕，散列表，每種數(shù)據(jù)結(jié)構(gòu)都有其特殊的存儲(chǔ)方式淋叶。
一阎曹、數(shù)組
概念：
一維數(shù)組：數(shù)組元素+數(shù)組索引
多維數(shù)組：數(shù)組的元素也是數(shù)組
基本操作：insert,get,delete（刪除某個(gè)索引處的數(shù)組）,size(獲取數(shù)組長(zhǎng)度）
題目：
查找數(shù)組第二小的元素
查找第一個(gè)沒有重復(fù)的數(shù)組元素
合并2個(gè)排序號(hào)的數(shù)據(jù)
重新排列數(shù)組中的正數(shù)和負(fù)數(shù)
二、棧
特點(diǎn)：棧是一種特殊的線性表，僅能在線性表的一端操作处嫌，棧頂允許操作栅贴，棧底不允許操作。 棧的特點(diǎn)是：先進(jìn)后出熏迹，或者說是后進(jìn)先出檐薯。棧中的元素采用LIFO (Last In First Out)，即后進(jìn)先出注暗。
基本操作：Push（棧頂插入元素）坛缕，Pop(返回棧最上方的元素，并刪除）友存，isEmpty（查詢棧是否為空）祷膳，Top（返回最上方元素陶衅，并不刪除）
題目：使用棧計(jì)算后綴表達(dá)式屡立、使用棧為棧中的元素排序、檢查字符串中的括號(hào)是否匹配正確
使用場(chǎng)景：棧常應(yīng)用于實(shí)現(xiàn)遞歸功能方面的場(chǎng)景搀军，例如斐波那契數(shù)列膨俐。撤回，即Ctrl+Z罩句，是我們最常見的操作之一焚刺，大多數(shù)應(yīng)用都會(huì)支持這個(gè)功能。你知道它是怎么實(shí)現(xiàn)的嗎门烂？答案是這樣的：把之前的應(yīng)用狀態(tài)(限制個(gè)數(shù))保存到內(nèi)存中乳愉，最近的狀態(tài)放到第一個(gè)。這時(shí)屯远，我們需要棧(stack)來實(shí)現(xiàn)這個(gè)功能蔓姚。
三、隊(duì)列
概念：隊(duì)列(Queue)與棧類似慨丐，都是采用線性結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)坡脐。它們的區(qū)別在于，棧采用LIFO方式房揭，而隊(duì)列采用先進(jìn)先出备闲，即FIFO(First in First Out)。
使用場(chǎng)景：因?yàn)殛?duì)列先進(jìn)先出的特點(diǎn)捅暴，在多線程阻塞隊(duì)列管理中非常適用恬砂。
基本操作：Enqueue—在隊(duì)列末尾插入元素，Dequeue—將隊(duì)列第一個(gè)元素刪除i蓬痒，sEmpty—查詢隊(duì)列是否為空泻骤，Top—返回隊(duì)列的第一個(gè)元素
習(xí)題：使用隊(duì)列實(shí)現(xiàn)棧，倒轉(zhuǎn)隊(duì)列的前K個(gè)元素，使用隊(duì)列將1到n轉(zhuǎn)換為二進(jìn)制瞪讼。
四钧椰、鏈表
概念“鏈表(Linked List)也是線性結(jié)構(gòu)，它與數(shù)組看起來非常像符欠，但是它們的內(nèi)存分配方式嫡霞、內(nèi)部結(jié)構(gòu)和插入刪除操作方式都不一樣。鏈表是一系列節(jié)點(diǎn)組成的鏈希柿，每一個(gè)節(jié)點(diǎn)保存了數(shù)據(jù)以及指向下一個(gè)節(jié)點(diǎn)的指針诊沪。鏈表頭指針指向第一個(gè)節(jié)點(diǎn)，如果鏈表為空曾撤，則頭指針為空或者為null端姚。鏈表分為：?jiǎn)蜗蜴湵恚p向鏈表挤悉。
使用場(chǎng)景：鏈表可以用來實(shí)現(xiàn)文件系統(tǒng)渐裸、哈希表和鄰接表。
基本操作：InsertAtEnd—在鏈表結(jié)尾插入元素装悲，InsertAtHead—在鏈表開頭插入元素昏鹃，Delete—?jiǎng)h除鏈表的指定元素，DeleteAtHead—?jiǎng)h除鏈表第一個(gè)元素诀诊，Search—在鏈表中查詢指定元素洞渤，isEmpty—查詢鏈表是否為空
題目：倒轉(zhuǎn)1個(gè)鏈表，檢查鏈表中是否存在循環(huán)属瓣，返回鏈表倒數(shù)第N個(gè)元素载迄，移除鏈表中的重復(fù)元素
五、圖
概念：圖(graph)由多個(gè)節(jié)點(diǎn)(vertex)構(gòu)成抡蛙，節(jié)點(diǎn)之間闊以互相連接組成一個(gè)網(wǎng)絡(luò)护昧。(x, y)表示一條邊(edge)，它表示節(jié)點(diǎn)x與y相連溜畅。邊可能會(huì)有權(quán)值(weight/cost)捏卓。
分類：無向圖，有向圖
表現(xiàn)形式：鄰接矩陣(Adjacency Matrix)慈格，鄰接表(Adjacency List)
遍歷圖的兩種算法：廣度優(yōu)先搜索(Breadth First Search)怠晴，深度優(yōu)先搜索(Depth First Search)
常見題目：
實(shí)現(xiàn)廣度優(yōu)先搜索，實(shí)現(xiàn)深度優(yōu)先搜索浴捆，檢查圖是否為樹蒜田，統(tǒng)計(jì)圖中邊的個(gè)數(shù)，使用Dijkstra算法查找兩個(gè)節(jié)點(diǎn)之間的最短距離选泻。
六冲粤、樹
樹(Tree)是一個(gè)分層的數(shù)據(jù)結(jié)構(gòu)美莫，由節(jié)點(diǎn)和連接節(jié)點(diǎn)的邊組成。樹是一種特殊的圖梯捕，它與圖最大的區(qū)別是沒有循環(huán)厢呵。樹被廣泛應(yīng)用在人工智能和一些復(fù)雜算法中，用來提供高效的存儲(chǔ)結(jié)構(gòu)傀顾。
常見樹：N叉樹(N-ary Tree)襟铭，平衡樹(Balanced Tree)，二叉樹(Binary Tree)短曾，二叉查找樹(Binary Search Tree)寒砖，平衡二叉樹(AVL Tree)，紅黑樹(Red Black Tree)嫉拐，2-3樹(2–3 Tree)
題目：計(jì)算樹的高度哩都，查找二叉平衡樹中第K大的元素，查找樹中與根節(jié)點(diǎn)距離為k的節(jié)點(diǎn)婉徘，查找二叉樹中某個(gè)節(jié)點(diǎn)所有祖先節(jié)點(diǎn)漠嵌。
七. 哈希表
哈希(Hash)將某個(gè)對(duì)象變換為唯一標(biāo)識(shí)符，該標(biāo)識(shí)符通常用一個(gè)短的隨機(jī)字母和數(shù)字組成的字符串來代表判哥。哈舷籽牛可以用來實(shí)現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)碉考，其中最常用的就是哈希表(hash table)塌计。
哈希表通常由數(shù)組實(shí)現(xiàn)。
哈希表的性能取決于3個(gè)指標(biāo)：
哈希函數(shù)哈希表的大小哈希沖突處理方式
題目：查找數(shù)組中對(duì)稱的組合侯谁，確認(rèn)某個(gè)數(shù)組的元素是否為另一個(gè)數(shù)組元素的子集锌仅，確認(rèn)給定的數(shù)組是否互斥。
八墙贱、前綴樹
前綴樹(Prefix Trees或者Trie)與樹類似热芹，用于處理字符串相關(guān)的問題時(shí)非常高效。它可以實(shí)現(xiàn)快速檢索惨撇，常用于字典中的單詞查詢伊脓，搜索引擎的自動(dòng)補(bǔ)全甚至IP路由。
