介紹

數(shù)據(jù)結(jié)構(gòu)是我們面試中經(jīng)常會問到的一個問題图谷，今天我們來簡單介紹下我們常用的8中基本數(shù)據(jù)結(jié)構(gòu)吧翩活！

講解流程：

一.數(shù)據(jù)結(jié)構(gòu)的定義
二.8種基本數(shù)據(jù)結(jié)構(gòu)
1.數(shù)組（Array）
2.鏈表（Linked List）
3.棧（Stack）
4.隊列 （Queue）
5.樹 （Tree）
6.圖 （Graph）
7.散列表 （Hash）
8.堆 （Heap）

一.數(shù)據(jù)結(jié)構(gòu)的定義

數(shù)據(jù)結(jié)構(gòu)是計算機(jī)存儲阱洪、組織數(shù)據(jù)的方式便贵。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)以及它們之間的相互關(guān)系冗荸，并對這種結(jié)構(gòu)定義相適應(yīng)的運算承璃，設(shè)計出相應(yīng)的算法，并確保經(jīng)過這些運算以后所得到的新結(jié)構(gòu)仍保持原來的結(jié)構(gòu)類型蚌本。
數(shù)據(jù)結(jié)構(gòu)分為線性數(shù)據(jù)結(jié)構(gòu)盔粹、非線性數(shù)據(jù)結(jié)構(gòu)
線性數(shù)據(jù)結(jié)構(gòu)：數(shù)組隘梨，棧，鏈表舷嗡，隊列
非線性數(shù)據(jù)結(jié)構(gòu)：樹轴猎，圖，堆进萄，散列表
數(shù)據(jù)結(jié)構(gòu)有很多種捻脖，一般來說，8種常用數(shù)據(jù)結(jié)構(gòu)分別為：數(shù)組中鼠，棧可婶，鏈表，隊列援雇，樹矛渴，圖，堆惫搏，散列表等蒲肋，

image.png

二.8種基本數(shù)據(jù)結(jié)構(gòu)

1.數(shù)組（Array）

數(shù)組是用于儲存多個相同類型數(shù)據(jù)的集合自点。
數(shù)組是在程序設(shè)計中，為了處理方便， 把具有相同類型的若干元素按無序的形式組織起來的一種形式躬存。這些無序排列的同類數(shù)據(jù)元素的集合稱為數(shù)組。數(shù)組是最簡單督暂、也是使用最廣泛的數(shù)據(jù)結(jié)構(gòu)胧奔。棧、隊列等其他數(shù)據(jù)結(jié)構(gòu)均由數(shù)組演變而來较沪。

int[] data = new int[100]鳞绕；
data[0]=2;

優(yōu)點：按照索引查詢元素速度快
缺點：
1.數(shù)組大小固定后無法擴(kuò)容
2.數(shù)組只能儲存一種數(shù)據(jù)類型
3.增、刪數(shù)據(jù)操作尸曼，比較耗時们何。
使用場景：頻繁查詢，對存儲空間要求不大控轿，很少增加和刪除的情況冤竹。

面試中常見問題

• 尋找數(shù)組中第二小的元素
• 找到數(shù)組中第一個不重復(fù)出現(xiàn)的整數(shù)
• 合并兩個有序數(shù)組
• 重新排列數(shù)組中的正值和負(fù)值

2.鏈表（Linked List）

鏈表是物理存儲單元上非連續(xù)的、非順序的存儲結(jié)構(gòu)茬射，數(shù)據(jù)元素的邏輯順序是通過鏈表的指針地址實現(xiàn)鹦蠕，每個元素包含兩個結(jié)點，一個是存儲元素的數(shù)據(jù)域 (內(nèi)存空間)在抛，另一個是指向下一個結(jié)點地址的指針域钟病。根據(jù)指針的指向，鏈表能形成不同的結(jié)構(gòu)，例如單鏈表肠阱，雙向鏈表票唆，循環(huán)鏈表等。

image.png

優(yōu)點：
1.不需要初始化容量
2.可以添加任意元素
3.插入和刪除時只需要更新引用
缺點：
1.含有大量引用屹徘，占用內(nèi)存空間大走趋；
2.查找元素需要遍歷整個鏈表，耗時噪伊。
使用場景：數(shù)據(jù)量較小吆视，需要頻繁增加，刪除操作的場景

數(shù)組與鏈表對比

image.png

3.棧（Stack）

棧是一種特殊的線性表酥宴，僅能在線性表的一端操作啦吧，棧頂允許操作，棧底不允許操作拙寡。從棧頂放入元素的操作叫入棧授滓，取出元素叫出棧。

image.png

特點：后進(jìn)先出

(1) 棧的基本操作

• Push——在頂部插入一個元素
• Pop——返回并移除棧頂元素
• isEmpty——如果棧為空肆糕，則返回true
• Top——返回頂部元素般堆，但并不移除它

(2) 面試中關(guān)于棧的常見問題

• 使用棧計算后綴表達(dá)式
• 對棧的元素進(jìn)行排序
• 判斷表達(dá)式是否括號平衡

4.隊列 （Queue）

隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作诚啃，而在表的后端（rear）進(jìn)行插入操作淮摔，和棧一樣，隊列是一種操作受限制的線性表始赎。進(jìn)行插入操作的端稱為隊尾和橙，進(jìn)行刪除操作的端稱為隊頭。
棧與隊列的最大差別在于棧是LIFO(后進(jìn)先出)造垛，而隊列是FIFO魔招，即先進(jìn)先出。

image.png

隊列可以用數(shù)組來實現(xiàn)五辽，也可以用鏈表來實現(xiàn)办斑。用數(shù)組實現(xiàn)的棧叫作順序棧，用鏈表實現(xiàn)的棧叫作鏈?zhǔn)綏８硕骸Ｍ瑯酉绯幔脭?shù)組實現(xiàn)的隊列叫作順序隊列，用鏈表實現(xiàn)的隊列叫作鏈?zhǔn)疥犃小?/p>

特點：先進(jìn)先出
應(yīng)用場景：因為隊列先進(jìn)先出的特點罪郊，在多線程阻塞隊列蠕蚜、循環(huán)隊列、并發(fā)隊列管理中非常適用排龄。

面試中關(guān)于隊列的常見問題

• 使用隊列表示棧
• 對隊列的前k個元素倒序
• 使用隊列生成從1到n的二進(jìn)制數(shù)

5.樹 （Tree）

樹是一種數(shù)據(jù)結(jié)構(gòu)波势，它是由n（n>=1）個有限節(jié)點組成一個具有層次關(guān)系的集合。把它叫做 “樹” 是因為它看起來像一棵倒掛的樹橄维，也就是說它是根朝上尺铣，而葉朝下的。
樹形結(jié)構(gòu)被廣泛應(yīng)用于人工智能和復(fù)雜算法争舞，它可以提供解決問題的有效存儲機(jī)制凛忿。

image.png

• Root - 根節(jié)點
• Parent - 父節(jié)點
• Child - 子節(jié)點
• Leaf - 葉子節(jié)點
• Sibling - 兄弟節(jié)點

特點：

• 每個節(jié)點有零個或多個子節(jié)點
• 沒有父節(jié)點的節(jié)點稱為根節(jié)點
• 每一個非根節(jié)點有且只有一個父節(jié)點
• 除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹

在日常的應(yīng)用中竞川，我們討論和用的更多的是樹的其中一種結(jié)構(gòu)店溢，就是二叉樹。

二叉樹是樹的特殊一種委乌，具有如下特點：
1床牧、每個結(jié)點最多有兩顆子樹，結(jié)點的度最大為2遭贸。
2戈咳、左子樹和右子樹是有順序的，次序不能顛倒壕吹。
3著蛙、即使某結(jié)點只有一個子樹，也要區(qū)分左右子樹耳贬。

二叉樹是一種比較有用的折中方案踏堡，它添加，刪除元素都很快咒劲，并且在查找方面也有很多的算法優(yōu)化顷蟆，所以，二叉樹既有鏈表的好處腐魂，也有數(shù)組的好處慕的，是兩者的優(yōu)化方案，在處理大批量的動態(tài)數(shù)據(jù)方面非常有用挤渔。

面試中關(guān)于樹結(jié)構(gòu)的常見問題

• 求二叉樹的高度
• 在二叉搜索樹中查找第k個最大值
• 查找與根節(jié)點距離k的節(jié)點
• 在二叉樹中查找給定節(jié)點的祖先節(jié)點

6.圖 （Graph）

圖是一組以網(wǎng)絡(luò)形式相互連接的節(jié)點肮街。節(jié)點也稱為頂點(Vertex)。 一對節(jié)點(x判导，y)稱為邊(edge)嫉父，表示頂點x連接到頂點y。邊可以包含權(quán)重/成本眼刃，顯示從頂點x到y(tǒng)所需的成本绕辖。

圖是由頂點集合(Vertex)及頂點間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：Graph＝( V, E )
V = {x | x ∈某個數(shù)據(jù)對象 } 是頂點的有窮非空集合；
E ={ (x, y) | x, y ∈V } 是頂點之間關(guān)系的有窮集合擂红，也叫做邊(Edge)集合仪际。

按照頂點指向的方向可分為無向圖和有向圖：

image.png

面試中關(guān)于圖的常見問題

• 實現(xiàn)廣度和深度優(yōu)先搜索
• 檢查圖是否為樹
• 計算圖的邊數(shù)
• 找到兩個頂點之間的最短路徑

7.散列表 （Hash）

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

哈希表在應(yīng)用中也是比較常見的框舔，就如Java中有些集合類就是借鑒了哈希原理構(gòu)造的，例如HashMap赎婚，HashTable等刘绣，利用hash表的優(yōu)勢，對于集合的查找元素時非常方便的挣输，然而纬凤，因為哈希表是基于數(shù)組衍生的數(shù)據(jù)結(jié)構(gòu)，在添加刪除元素方面是比較慢的撩嚼，所以很多時候需要用到一種數(shù)組鏈表來做移斩，也就是拉鏈法。

特點：

• 可以利用哈希函數(shù)快速訪問到數(shù)組的目標(biāo)數(shù)據(jù)绢馍。如果發(fā)生哈希沖突向瓷，就使用鏈表進(jìn)行存儲。
• 如果數(shù)組的空間太小舰涌，使用哈希表的時候就容易發(fā)生沖突猖任，線性查找的使用頻率也會更高；反過來瓷耙，如果數(shù)組的空間太大朱躺，就會出現(xiàn)很多空箱子，造成內(nèi)存的浪費搁痛。因此长搀，給數(shù)組設(shè)定合適的空間非常重要。
• 在存儲數(shù)據(jù)的過程中鸡典，如果發(fā)生沖突源请，可以利用鏈表在已有數(shù)據(jù)的后面插入新數(shù)據(jù)來解決沖突。這種方法被稱為“鏈地址法”彻况。除了鏈地址法以外谁尸，還有幾種解決沖突的方法。其中纽甘，應(yīng)用較為廣泛的是“開放地址法”良蛮。

8.堆 （Heap）

堆是一種圖的樹形結(jié)構(gòu)，被用于實現(xiàn)“優(yōu)先隊列”(priority queues)悍赢。優(yōu)先隊列是一種數(shù)據(jù)結(jié)構(gòu)决瞳，可以自由添加數(shù)據(jù)货徙，但取出數(shù)據(jù)時要從最小值開始按順序取出。在堆的樹形結(jié)構(gòu)中皮胡，各個頂點被稱為“結(jié)點”(node)痴颊，數(shù)據(jù)就存儲在這些結(jié)點中。

堆的特點：

• 每個節(jié)點最多有兩個子節(jié)點
• 排列順序必須從上到下胸囱，同一行從左到右
• 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值祷舀；
• 存放數(shù)據(jù)時瀑梗，一般會把新數(shù)據(jù)放在最下面一行靠左的位置烹笔。如果最下面一行沒有多余空間時，就再往下另起一行抛丽，并把數(shù)據(jù)添加到這一行的最左端谤职。

堆的性質(zhì)：
- 堆總是一棵完全二叉樹
- 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值

將根結(jié)點最大的堆叫做最大堆或大根堆，根結(jié)點最小的堆叫做最小堆或小根堆亿鲜。

image.png

因為堆有序的特點允蜈，一般用來做數(shù)組中的排序，稱為堆排序蒿柳。