來自：五分鐘學算法（微信號：blgczzz）

國外 IT 教育學院 Educative.io 創(chuàng)始人 Fahim ul Haq 寫過一篇過萬贊的文章《The top data structures you should know for your next coding interview》,總結了程序員面試中需要掌握的 8 種數(shù)據結構知識。

Fahim ul Haq 曾在 Facebook 和微軟任職,，面試過不少程序員,，所以這篇文章還是值得參考的。以下內容參考編譯自他的這篇《準備下次編程面試前你應該知道的數(shù)據結構》：

瑞典計算機科學家 Niklaus Wirth 在 1976 年寫了一本書,，叫作《Algorithms + Data Structures = Programs》（算法+數(shù)據結構=程序）,。

即便在 40 年后的今天，這條等式仍然成立,。這也是為何程序員求職者應該向面試官展示出已經透徹理解了數(shù)據結構知識,。

幾乎所有的面試問題都要求求職者表現(xiàn)出已經熟練掌握數(shù)據結構，不管你是剛畢業(yè)的應屆生還是工作了多年的老手,，都是這樣,。

有時，面試問題會明確提到數(shù)據結構,，比如“給定一個二叉樹”,；有時則比較含蓄，比如“我們想追蹤和每位作者相關的書籍數(shù)量,?！?/p>

學習數(shù)據結構知識很有必要，哪怕你只是想找份比現(xiàn)在的工作更好的一份差事,。我們首先了解數(shù)據結構的基本知識,。

什么是數(shù)據結構,？

簡單說，數(shù)據結構就是一個容器,，以某種特定的布局存儲數(shù)據,。這個“布局”使得數(shù)據結構在某些操作上非常高效，在另一些操作上則不那么高效,。你的目標就是理解數(shù)據結構,，這樣就能為手頭的問題選擇最優(yōu)的數(shù)據結構。

為什么我們需要數(shù)據結構,？

由于數(shù)據結構用來以有組織的形式存儲數(shù)據,，而且數(shù)據是計算機科學中最重要的實體，因此數(shù)據結構的真正價值顯而易見,。

無論你解決什么問題,，你都必須以這種或那種方式處理數(shù)據比如員工的工資，股票價格,，購物清單,，甚至簡單的電話簿等等。

根據不同的場景,，數(shù)據需要以特定格式存儲,。目前有一些數(shù)據結構可以滿足我們以不同格式存儲數(shù)據的需求。

常用的數(shù)據結構

我們首先列出最常用的數(shù)據結構,，然后再挨個講解：

數(shù)組

堆棧

隊列

鏈表

樹

圖

字典樹

哈希表

數(shù)組是一種最簡單和最廣泛使用的數(shù)據結構,，其它數(shù)據結構比如堆棧和隊列都源自數(shù)組。

下圖是一個大小為 4 的簡單數(shù)組,，包含幾個元素（ 1 , 2 , 3,，4）。

每個數(shù)據元素會被分配一個正的數(shù)值,，叫作“索引”,，它對應該元素在數(shù)組中的位置。大部分編程語言都將初始索引定義為 0.

以下是兩種數(shù)組：

一維數(shù)組（如上所示）

多維數(shù)組（數(shù)組的數(shù)組）

數(shù)組的基本操作：

Insert——在給定索引位置插入一個元素

Get——返回給定索引位置的元素

Delete——刪除給定索引位置的元素

Size——獲取數(shù)組內所有元素的總數(shù)

常問的數(shù)組面試問題：

找到數(shù)組中第二小的元素

找到數(shù)組中第一個沒有重復的整數(shù)

合并兩個分類數(shù)組

重新排列數(shù)組中的正值和負值

我們都熟悉很有名的撤銷（Undo）選項,，它幾乎存在每個應用程序中,。有沒有想過它是如何工作的？其思路就是,，按照最后的狀態(tài)排列在先的順序將工作的先前狀態(tài)（限于特定數(shù)字）存儲在內存中,。這只用數(shù)組是無法實現(xiàn)的，因此堆棧就有了用武之地,。

可以把堆棧看作一堆垂直排列的書籍,。為了獲得位于中間位置的書,，你需要拿掉放在它上面的所有書籍,。這就是 LIFO（后進先出）方法的工作原理。

這是一個包含三個數(shù)據元素（1,2 和 3）的堆棧圖像,，其中3位于頂部,，首先把它刪除：

堆棧的基本操作：

Push——在頂部插入元素

Pop—— 從堆棧中刪除后返回頂部元素

isEmpty——如果堆棧為空，則返回 true

Top ——返回頂部元素,，但不從堆棧中刪除

常見的堆棧面試問題：

使用堆棧計算后綴表達式

對堆棧中的值進行排序

檢查表達式中的括號是否平衡

與堆棧類似,，隊列是另一種線性數(shù)據結構，以順序方式存儲元素,。堆棧和隊列之間唯一的顯著區(qū)別是,，隊列不是使用 LIFO 方法，而是應用 FIFO 方法,，這是 First in First Out（先入先出）的縮寫,。

隊列的完美現(xiàn)實例子：一列人在售票亭等候。如果有新人來,，他們是從末尾加入隊列,，而不是在開頭——站在前面的人將先買到票然后離開隊列。

下圖是一個包含四個數(shù)據元素（1,2,3 和 4）的隊列,，其中 1 位于頂部,，首先把它刪除：

隊列的基本操作：

Enqueue() —— 向隊列末尾插入元素

Dequeue() —— 從隊列頭部移除元素

isEmpty() —— 如果隊列為空，則返回 true

Top() —— 返回隊列的第一個元素

常問的隊列面試問題：

使用隊列來實現(xiàn)堆棧

顛倒隊列中前 k 個元素的順序

使用隊列生成從 1 到 n 的二進制數(shù)

鏈表是另一個重要的線性數(shù)據結構,，剛一看可能看起來像數(shù)組,，但在內存分配，內部結構以及如何執(zhí)行插入和刪除的基本操作方面有所不同,。

鏈表就像一個節(jié)點鏈,，其中每個節(jié)點包含數(shù)據和指向鏈中后續(xù)節(jié)點的指針等信息。有一個頭指針,，指向鏈表的第一個元素,，如果列表是空的，那么它只指向 null 或不指向任何內容,。

鏈表用于實現(xiàn)文件系統(tǒng),，哈希表和鄰接表。下圖是鏈表內部結構的直觀展示：

下面是幾種類型的鏈表：

單鏈表（單向）

雙鏈表（雙向）

鏈表的基本操作：

InsertAtEnd —— 在鏈表末尾插入指定元素

InsertAtHead —— 在鏈表頭部插入指定元素

Delete —— 從鏈表中刪除指定元素

DeleteAtHead —— 刪除鏈表的第一個元素

Search —— 返回鏈表中的指定元素

isEmpty —— 如果鏈表為空,，返回 true

常問的鏈表面試問題：

翻轉列表

檢測鏈表中的循環(huán)

返回鏈表中倒數(shù)第 n 個節(jié)點

移除鏈表中的重復值

圖就是一組節(jié)點,，以網絡的形式互相連接。節(jié)點也被稱為頂點（vertices）,。一對（x,y）就叫做一個邊,，表示頂點 x 和頂點 y 相連。一個邊可能包含權重/成本,，顯示從頂點 x 到 y 所需的成本,。

圖的類型：

無向圖

有向圖

在編程語言中,，圖可以表示為兩種形式：

鄰接矩陣

鄰接列表

常見的圖遍歷算法：

廣度優(yōu)先搜索

深度優(yōu)先搜索

常問的圖面試問題：

實現(xiàn)廣度優(yōu)先搜索和深度優(yōu)先搜索

檢查一個圖是否為樹

計算一張圖中的邊的數(shù)量

找到兩個頂點之間的最短路徑

樹是一種層級數(shù)據結構，包含了連接它們的頂點（節(jié)點）和邊,。樹和圖很相似,，但二者有個很大的不同點，即樹中沒有循環(huán),。

樹廣泛應用在人工智能和復雜的算法中,，為解決各種問題提供高效的存儲機制。

下圖是一個簡單的樹,，以及在樹型數(shù)據結構中所用的基本術語：

下面是幾種類型的樹：

N 叉樹

平衡樹

二叉樹

二叉搜索樹

平衡二叉樹

紅黑樹

2-3 樹

其中,，二叉樹和二叉搜索樹是最常用的樹。

常問的樹面試問題：

找到一個二叉樹的高度

找到一個二叉搜索樹中第 k 個最大值

找到距離根部“k”個距離的節(jié)點

找到一個二叉樹中給定節(jié)點的祖先（ancestors）

字典樹,，也叫“前綴樹”,，是一種樹形結構，在解決字符串相關問題中非常高效,。其提供非?？焖俚臋z索功能，常用于搜索字典中的單詞,，為搜索引擎提供自動搜索建議,，甚至能用于IP路由選擇。
下面展示了 “top” “thus” 和 “their” 這三個詞是如何存儲在字典樹中的：

這些單詞以從上到下的方式存儲,，其中綠色節(jié)點“p”,，“s”和“r”分別表示“top”，“thus”和“their”的末尾,。

常見的字典樹面試問題：

計算字典樹中的總字數(shù)

打印存儲在字典樹中的所有單詞

使用字典樹對數(shù)組的元素進行排序

使用字典樹從字典中形成單詞

構建一個T9字典

散列是一個用于唯一標識對象并在一些預先計算的唯一索引（稱為“密鑰”）存儲每個對象的過程,。因此，對象以“鍵值”對的形式存儲,，這些項的集合被稱為“字典”,。可以使用該鍵值搜索每個對象,。有多種不同的基于哈希的數(shù)據結構,，但最常用的數(shù)據結構是哈希表。

哈希表通常使用數(shù)組實現(xiàn),。

哈希數(shù)據結構的性能取決于以下三個因素：

哈希函數(shù)

哈希表的大小

碰撞處理方法

下圖展示了如何在數(shù)組中映射哈希,。該數(shù)組的索引是通過哈希函數(shù)計算的。

常問的哈希面試問題：

找到數(shù)組中的對稱對

追蹤遍歷的完整路徑

查看一個數(shù)組是否為另一個數(shù)組的子集

檢查給定數(shù)組是否不相交

以上就是你在準備編程面試前需要掌握的 8 種數(shù)據結構,。

●編號842,，輸入編號直達本文

●輸入m獲取文章目錄

人工智能與大數(shù)據技術

更多推薦《25個技術類公眾微信》

涵蓋：程序人生、算法與數(shù)據結構、黑客技術與網絡安全,、大數(shù)據技術,、前端開發(fā)、Java,、Python、Web開發(fā),、安卓開發(fā),、iOS開發(fā)、C/C++,、.NET,、Linux、數(shù)據庫,、運維等,。