瑞士計算機科學家Niklaus Wirth在1976年寫了一本書，名為《算法+資料結構=程式設計》。
40多年後，這個等式仍被奉為真理。這就是為什麼在面試過程中，需要考察軟體工程師對資料結構的了解。
幾乎所有的問題都需要面試者對資料結構有深刻的了解。無論你是初入職場的新兵(剛從大學或者程式設計教育訓練班畢業)，還是擁有幾十年經驗的職場老鳥。
有些面試題會明确提及某種資料結構，例如，“給定一個二叉樹。”而另一些則隐含在面試題中，例如，“我們希望記錄每個作者相關的書籍數量。”
即便是對于一些非常基礎的工作來說，學習資料結構也是必須的。那麼，就讓我們先從一些基本概念開始入手。
什麼是資料結構?
簡單地說，資料結構是以某種特定的布局方式存儲資料的容器。這種“布局方式”決定了資料結構對于某些操作是高效的，而對于其他操作則是低效的。首先我們需要了解各種資料結構，才能在處理實際問題時選取最合适的資料結構。
為什麼我們需要資料結構?
資料是計算機科學當中最關鍵的實體，而資料結構則可以将資料以某種組織形式存儲，是以，資料結構的價值不言而喻。
無論你以何種方式解決何種問題，你都需要處理資料——無論是涉及員工薪水、股票價格、購物清單，還是隻是簡單的電話簿問題。
資料需要根據不同的場景，按照特定的格式進行存儲。有很多資料結構能夠滿足以不同格式存儲資料的需求。
常見的資料結構
首先列出一些最常見的資料結構，我們将逐一說明：
• 數組
• 棧
• 隊列
• 連結清單
• 樹
• 圖
• 字典樹(這是一種高效的樹形結構，但值得單獨說明)
• 散清單(哈希表)
數組
數組是最簡單、也是使用最廣泛的資料結構。棧、隊列等其他資料結構均由數組演變而來。下圖是一個包含元素(1，2，3和4)的簡單數組，數組長度為4。
每個資料元素都關聯一個正數值，我們稱之為索引，它表明數組中每個元素所在的位置。大部分語言将初始索引定義為零。
● 以下是數組的兩種類型：• 一維數組(如上所示)
• 多元數組(數組的數組)
數組的基本操作• Insert——在指定索引位置插入一個元素
• Get——傳回指定索引位置的元素
• Delete——删除指定索引位置的元素
• Size——得到數組所有元素的數量
面試中關于數組的常見問題• 尋找數組中第二小的元素
• 找到數組中第一個不重複出現的整數
• 合并兩個有序數組
• 重新排列數組中的正值和負值
棧
著名的撤銷操作幾乎遍布任意一個應用。但你有沒有思考過它是如何工作的呢?這個問題的解決思路是按照将最後的狀态排列在先的順序，在記憶體中存儲曆史工作狀态(當然，它會受限于一定的數量)。這沒辦法用數組實作。但有了棧，這就變得非常友善了。
可以把棧想象成一列垂直堆放的書。為了拿到中間的書，你需要移除放置在這上面的所有書。這就是LIFO(後進先出)的工作原理。
下圖是包含三個資料元素(1，2和3)的棧，其中頂部的3将被最先移除：
• Push——在頂部插入一個元素
• Pop——傳回并移除棧頂元素
• isEmpty——如果棧為空，則傳回true
• Top——傳回頂部元素，但并不移除它
面試中關于棧的常見問題• 使用棧計算字尾表達式
• 對棧的元素進行排序
• 判斷表達式是否括号平衡
隊列
與棧相似，隊列是另一種順序存儲元素的線性資料結構。棧與隊列的最大差别在于棧是LIFO(後進先出)，而隊列是FIFO，即先進先出。
一個完美的隊列現執行個體子：售票亭排隊隊伍。如果有新人加入，他需要到隊尾去排隊，而非隊首——排在前面的人會先拿到票，然後離開隊伍。
下圖是包含四個元素(1，2，3和4)的隊列，其中在頂部的1将被最先移除：
移除先入隊的元素、插入新元素
隊列的基本操作• Enqueue() —— 在隊列尾部插入元素
• Dequeue() ——移除隊列頭部的元素
• isEmpty()——如果隊列為空，則傳回true
• Top() ——傳回隊列的第一個元素
面試中關于隊列的常見問題• 使用隊清單示棧
• 對隊列的前k個元素倒序
• 使用隊列生成從1到n的二進制數
連結清單
連結清單是另一個重要的線性資料結構，乍一看可能有點像數組，但在記憶體配置設定、内部結構以及資料插入和删除的基本操作方面均有所不同。
連結清單就像一個節點鍊，其中每個節點包含着資料和指向後續節點的指針。 連結清單還包含一個頭指針，它指向連結清單的第一個元素，但當清單為空時，它指向null或無具體内容。
連結清單一般用于實作檔案系統、哈希表和鄰接表。
這是連結清單内部結構的展示：
• 單連結清單(單向)
• 雙向連結清單(雙向)
連結清單的基本操作：• InsertAtEnd - 在連結清單的末尾插入指定元素
• InsertAtHead - 在連結清單的開頭/頭部插入指定元素
• Delete - 從連結清單中删除指定元素
• DeleteAtHead - 删除連結清單的第一個元素
• Search - 從連結清單中傳回指定元素
• isEmpty - 如果連結清單為空，則傳回true
面試中關于連結清單的常見問題• 反轉連結清單
• 檢測連結清單中的循環
• 傳回連結清單倒數第N個節點
• 删除連結清單中的重複項
圖
圖是一組以網絡形式互相連接配接的節點。節點也稱為頂點。 一對節點(x，y)稱為邊(edge)，表示頂點x連接配接到頂點y。邊可以包含權重/成本，顯示從頂點x到y所需的成本。
• 無向圖
• 有向圖
在程式語言中，圖可以用兩種形式表示：• 鄰接矩陣
• 鄰接表
常見圖周遊算法• 廣度優先搜尋
• 深度優先搜尋
面試中關于圖的常見問題• 實作廣度和深度優先搜尋
• 檢查圖是否為樹
• 計算圖的邊數
• 找到兩個頂點之間的最短路徑
樹
樹形結構是一種層級式的資料結構，由頂點(節點)和連接配接它們的邊組成。 樹類似于圖，但區分樹和圖的重要特征是樹中不存在環路。
樹形結構被廣泛應用于人工智能和複雜算法，它可以提供解決問題的有效存儲機制。
這是一個簡單樹的示意圖，以及樹資料結構中使用的基本術語： • Root - 根節點
• Parent - 父節點
• Child - 子節點
• Leaf - 葉子節點
• Sibling - 兄弟節點
以下是樹形結構的主要類型：• N元樹
• 平衡樹
• 二叉樹
• 二叉搜尋樹
• AVL樹
• 紅黑樹
• 2-3樹
其中，二叉樹和二叉搜尋樹是最常用的樹。
面試中關于樹結構的常見問題：• 求二叉樹的高度
• 在二叉搜尋樹中查找第k個最大值
• 查找與根節點距離k的節點
• 在二叉樹中查找給定節點的祖先節點
字典樹(Trie)
字典樹，也稱為“字首樹”，是一種特殊的樹狀資料結構，對于解決字元串相關問題非常有效。它能夠提供快速檢索，主要用于搜尋字典中的單詞，在搜尋引擎中自動提供建議，甚至被用于IP的路由。
以下是在字典樹中存儲三個單詞“top”，“so”和“their”的例子：
這些單詞以頂部到底部的方式存儲，其中綠色節點“p”，“s”和“r”分别表示“top”，“thus”和“theirs”的底部。
面試中關于字典樹的常見問題• 計算字典樹中的總單詞數
• 列印存儲在字典樹中的所有單詞
• 使用字典樹對數組的元素進行排序
• 使用字典樹從字典中形成單詞
• 建構T9字典(字典樹+ DFS )
哈希表
哈希法(Hashing)是一個用于唯一辨別對象并将每個對象存儲在一些預先計算的唯一索引(稱為“鍵(key)”)中的過程。是以，對象以鍵值對的形式存儲，這些鍵值對的集合被稱為“字典”。可以使用鍵搜尋每個對象。基于哈希法有很多不同的資料結構，但最常用的資料結構是哈希表。
哈希表通常使用數組實作。
散列資料結構的性能取決于以下三個因素：• 哈希函數
• 哈希表的大小
• 碰撞處理方法
下圖為如何在數組中映射哈希鍵值對的說明。該數組的索引是通過哈希函數計算的。
• 在數組中查找對稱鍵值對
• 追蹤周遊的完整路徑
• 查找數組是否是另一個數組的子集
• 檢查給定的數組是否不相交
以上是在程式設計面試之前你應該知曉的八大資料結構。
原文釋出時間為：2018-08-27
本文來自雲栖社群合作夥伴“
大資料地盤”，了解相關資訊可以關注“
”。