數組是最簡單也是最常見的數據結構。它們的特點是可以通過索引（位置）輕松訪問元素。
它們是做什麽用的？
想象壹下有壹排劇院椅。每把椅子都分配了壹個位置（從左到右），因此每個觀眾都會從他將要坐的椅子上分配壹個號碼。這是壹個數組。將問題擴展到整個劇院（椅子的行和列），您將擁有壹個二維數組（矩陣）。
特性
鏈表是線性數據結構，就像數組壹樣。鏈表和數組的主要區別在於鏈表的元素不存儲在連續的內存位置。它由節點組成——實體存儲當前元素的值和下壹個元素的地址引用。這樣，元素通過指針鏈接。
它們是做什麽用的？
鏈表的壹個相關應用是瀏覽器的上壹頁和下壹頁的實現。雙鏈表是存儲用戶搜索顯示的頁面的完美數據結構。
特性
堆棧是壹種抽象數據類型，它形式化了受限訪問集合的概念。該限制遵循 LIFO（後進先出）規則。因此，添加到堆棧中的最後壹個元素是您從中刪除的第壹個元素。
堆棧可以使用數組或鏈表來實現。
它們是做什麽用的？
現實生活中最常見的例子是在食堂中將盤子疊放在壹起。位於頂部的板首先被移除。放置在最底部的盤子是在堆棧中保留時間最長的盤子。
堆棧最有用的壹種情況是您需要獲取給定元素的相反順序。只需將它們全部推入堆棧，然後彈出它們。
另壹個有趣的應用是有效括號問題。給定壹串括號，您可以使用堆棧檢查它們是否匹配。
特性
隊列是受限訪問集合中的另壹種數據類型，就像前面討論的堆棧壹樣。主要區別在於隊列是按照FIFO（先進先出）模型組織的：隊列中第壹個插入的元素是第壹個被移除的元素。隊列可以使用固定長度的數組、循環數組或鏈表來實現。
它們是做什麽用的？
這種抽象數據類型 (ADT) 的最佳用途當然是模擬現實生活中的隊列。例如，在呼叫中心應用程序中，隊列用於保存等待從顧問那裏獲得幫助的客戶——這些客戶應該按照他們呼叫的順序獲得幫助。
壹種特殊且非常重要的隊列類型是優先級隊列。元素根據與它們關聯的“優先級”被引入隊列：具有最高優先級的元素首先被引入隊列。這個 ADT 在許多圖算法（Dijkstra 算法、BFS、Prim 算法、霍夫曼編碼 ）中是必不可少的。它是使用堆實現的。
另壹種特殊類型的隊列是deque 隊列（雙關語它的發音是“deck”）。可以從隊列的兩端插入/刪除元素。
特性
Maps （dictionaries）是包含鍵集合和值集合的抽象數據類型。每個鍵都有壹個與之關聯的值。
哈希表是壹種特殊類型的映射。它使用散列函數生成壹個散列碼，放入壹個桶或槽數組：鍵被散列，結果散列指示值的存儲位置。
最常見的散列函數（在眾多散列函數中）是模常數函數。例如，如果常量是 6，則鍵 x 的值是x%6。
理想情況下，散列函數會將每個鍵分配給壹個唯壹的桶，但他們的大多數設計都采用了不完善的函數，這可能會導致具有相同生成值的鍵之間發生沖突。這種碰撞總是以某種方式適應的。
它們是做什麽用的？
Maps 最著名的應用是語言詞典。語言中的每個詞都為其指定了定義。它是使用有序映射實現的（其鍵按字母順序排列）。
通訊錄也是壹張Map。每個名字都有壹個分配給它的電話號碼。
另壹個有用的應用是值的標準化。假設我們要為壹天中的每壹分鐘（24 小時 = 1440 分鐘）分配壹個從 0 到 1439 的索引。哈希函數將為h(x) = x.小時*60+x.分鐘。
特性
術語：
因為maps 是使用自平衡紅黑樹實現的（文章後面會解釋），所以所有操作都在 O(log n) 內完成；所有哈希表操作都是常量。
圖是表示壹對兩個集合的非線性數據結構：G={V, E}，其中 V 是頂點（節點）的集合，而 E 是邊（箭頭）的集合。節點是由邊互連的值 - 描述兩個節點之間的依賴關系（有時與成本/距離相關聯）的線。
圖有兩種主要類型：有向圖和無向圖。在無向圖中，邊(x, y)在兩個方向上都可用：(x, y)和(y, x)。在有向圖中，邊(x, y)稱為箭頭，方向由其名稱中頂點的順序給出：箭頭(x, y)與箭頭(y, x) 不同。
它們是做什麽用的？
特性
圖論是壹個廣闊的領域，但我們將重點介紹壹些最知名的概念：
壹棵樹是壹個無向圖，在連通性方面最小（如果我們消除壹條邊，圖將不再連接）和在無環方面最大（如果我們添加壹條邊，圖將不再是無環的）。所以任何無環連通無向圖都是壹棵樹，但為了簡單起見，我們將有根樹稱為樹。
根是壹個固定節點，它確定樹中邊的方向，所以這就是壹切“開始”的地方。葉子是樹的終端節點——這就是壹切“結束”的地方。
壹個頂點的孩子是它下面的事件頂點。壹個頂點可以有多個子節點。壹個頂點的父節點是它上面的事件頂點——它是唯壹的。
它們是做什麽用的？
我們在任何需要描繪層次結構的時候都使用樹。我們自己的家譜樹就是壹個完美的例子。妳最古老的祖先是樹的根。最年輕的壹代代表葉子的集合。
樹也可以代表妳工作的公司中的上下級關系。這樣您就可以找出誰是您的上級以及您應該管理誰。
特性
二叉樹是壹種特殊類型的樹：每個頂點最多可以有兩個子節點。在嚴格二叉樹中，除了葉子之外，每個節點都有兩個孩子。具有 n 層的完整二叉樹具有所有2?-1 個可能的節點。
二叉搜索樹是壹棵二叉樹，其中節點的值屬於壹個完全有序的集合——任何任意選擇的節點的值都大於左子樹中的所有值，而小於右子樹中的所有值。
它們是做什麽用的？
BT 的壹項重要應用是邏輯表達式的表示和評估。每個表達式都可以分解為變量/常量和運算符。這種表達式書寫方法稱為逆波蘭表示法 (RPN)。這樣，它們就可以形成壹個二叉樹，其中內部節點是運算符，葉子是變量/常量——它被稱為抽象語法樹（AST）。
BST 經常使用，因為它們可以快速搜索鍵屬性。AVL 樹、紅黑樹、有序集和映射是使用 BST 實現的。
特性
BST 有三種類型的 DFS 遍歷：
所有這些類型的樹都是自平衡二叉搜索樹。不同之處在於它們以對數時間平衡高度的方式。
AVL 樹在每次插入/刪除後都是自平衡的，因為節點的左子樹和右子樹的高度之間的模塊差異最大為 1。 AVL 以其發明者的名字命名：Adelson-Velsky 和 Landis。
在紅黑樹中，每個節點存儲壹個額外的代表顏色的位，用於確保每次插入/刪除操作後的平衡。
在 Splay 樹中，最近訪問的節點可以快速再次訪問，因此任何操作的攤銷時間復雜度仍然是 O(log n)。
它們是做什麽用的？
AVL 似乎是數據庫理論中最好的數據結構。
RBT（紅黑樹） 用於組織可比較的數據片段，例如文本片段或數字。在 Java 8 版本中，HashMap 是使用 RBT 實現的。計算幾何和函數式編程中的數據結構也是用 RBT 構建的。
在 Windows NT 中（在虛擬內存、網絡和文件系統代碼中），Splay 樹用於緩存、內存分配器、垃圾收集器、數據壓縮、繩索（替換用於長文本字符串的字符串）。
特性
最小堆是壹棵二叉樹，其中每個節點的值都大於或等於其父節點的值：val[par[x]]