介紹

數(shù)據(jù)結(jié)構(gòu)是我們面試中經(jīng)常會(huì)問到的一個(gè)問題，今天我們來簡(jiǎn)單介紹下我們常用的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.隊(duì)列 （Queue）
5.樹 （Tree）
6.圖 （Graph）
7.散列表 （Hash）
8.堆 （Heap）

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

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)以及它們之間的相互關(guān)系，并對(duì)這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，并確保經(jīng)過這些運(yùn)算以后所得到的新結(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ù)組，棧，鏈表，隊(duì)列
非線性數(shù)據(jù)結(jié)構(gòu)：樹，圖，堆，散列表
數(shù)據(jù)結(jié)構(gòu)有很多種，一般來說，8種常用數(shù)據(jù)結(jié)構(gòu)分別為：數(shù)組，棧，鏈表，隊(duì)列，樹，圖，堆，散列表等，

image.png

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

1.數(shù)組（Array）

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

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

優(yōu)點(diǎn)：按照索引查詢?cè)厮俣瓤?br> 缺點(diǎn)：
1.數(shù)組大小固定后無法擴(kuò)容
2.數(shù)組只能儲(chǔ)存一種數(shù)據(jù)類型
3.增、刪數(shù)據(jù)操作，比較耗時(shí)。
使用場(chǎng)景：頻繁查詢，對(duì)存儲(chǔ)空間要求不大，很少增加和刪除的情況。

面試中常見問題

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

2.鏈表（Linked List）

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

image.png

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

數(shù)組與鏈表對(duì)比

image.png

3.棧（Stack）

棧是一種特殊的線性表，僅能在線性表的一端操作，棧頂允許操作，棧底不允許操作。從棧頂放入元素的操作叫入棧，取出元素叫出棧。

image.png

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

(1) 棧的基本操作

• Push——在頂部插入一個(gè)元素
• Pop——返回并移除棧頂元素
• isEmpty——如果棧為空，則返回true
• Top——返回頂部元素，但并不移除它

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

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

4.隊(duì)列 （Queue）

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

image.png

隊(duì)列可以用數(shù)組來實(shí)現(xiàn)，也可以用鏈表來實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)的棧叫作順序棧，用鏈表實(shí)現(xiàn)的棧叫作鏈?zhǔn)綏?。同樣，用?shù)組實(shí)現(xiàn)的隊(duì)列叫作順序隊(duì)列，用鏈表實(shí)現(xiàn)的隊(duì)列叫作鏈?zhǔn)疥?duì)列。

特點(diǎn)：先進(jìn)先出
應(yīng)用場(chǎng)景：因?yàn)殛?duì)列先進(jìn)先出的特點(diǎn)，在多線程阻塞隊(duì)列、循環(huán)隊(duì)列、并發(fā)隊(duì)列管理中非常適用。

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

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

5.樹 （Tree）

樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做 “樹” 是因?yàn)樗雌饋硐褚豢玫箳斓臉洌簿褪钦f它是根朝上，而葉朝下的。
樹形結(jié)構(gòu)被廣泛應(yīng)用于人工智能和復(fù)雜算法，它可以提供解決問題的有效存儲(chǔ)機(jī)制。

image.png

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

特點(diǎn)：

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

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

二叉樹是樹的特殊一種，具有如下特點(diǎn)：
1、每個(gè)結(jié)點(diǎn)最多有兩顆子樹，結(jié)點(diǎn)的度最大為2。
2、左子樹和右子樹是有順序的，次序不能顛倒。
3、即使某結(jié)點(diǎn)只有一個(gè)子樹，也要區(qū)分左右子樹。

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

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

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

6.圖 （Graph）

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

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

按照頂點(diǎn)指向的方向可分為無向圖和有向圖：

image.png

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

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

7.散列表 （Hash）

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

哈希表在應(yīng)用中也是比較常見的，就如Java中有些集合類就是借鑒了哈希原理構(gòu)造的，例如HashMap，HashTable等，利用hash表的優(yōu)勢(shì)，對(duì)于集合的查找元素時(shí)非常方便的，然而，因?yàn)楣１硎腔跀?shù)組衍生的數(shù)據(jù)結(jié)構(gòu)，在添加刪除元素方面是比較慢的，所以很多時(shí)候需要用到一種數(shù)組鏈表來做，也就是拉鏈法。

特點(diǎn)：

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

8.堆 （Heap）

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

堆的特點(diǎn)：

• 每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)
• 排列順序必須從上到下，同一行從左到右
• 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
• 存放數(shù)據(jù)時(shí)，一般會(huì)把新數(shù)據(jù)放在最下面一行靠左的位置。如果最下面一行沒有多余空間時(shí)，就再往下另起一行，并把數(shù)據(jù)添加到這一行的最左端。

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

將根結(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根結(jié)點(diǎn)最小的堆叫做最小堆或小根堆。

image.png

因?yàn)槎延行虻奶攸c(diǎn)，一般用來做數(shù)組中的排序，稱為堆排序。