常見抽象資料類型

一、棧

結構：棧頂、棧底

特點：後進先出。從棧頂壓入棧，從棧頂壓出棧

二、隊列

1、隊列

• 結構

  隊頭、隊尾

• 特點

  先進先出。從隊尾入隊列，從隊頭出隊列

2、雙端隊列

結構：隊頭、隊尾

特點：隊頭隊尾均可入隊/出隊

3、優先級隊列

三、樹

1、樹

結構：

• 一種分層的結構，由根節點 + 根節點的子孫節點（子樹）組成

重要概念：

• 節點

  根節點、内部節點、外部節點（葉子節點）

  父親節點、兄弟節點、孩子節點（左孩子、右孩子）

• 邊

  一對父子節點(u,v)

• 路徑

  指一系列的節點，其中任意兩個連續的節點都是一條邊

• 深度

  節點祖先的個數，根節點的深度是0

• 高度

  從葉子節點往上數的層數，葉子節點的高度是0

• 層

  同一深度的所有節點位于1層，根節點是第0層

2、二叉樹

特點：每個節點最多有兩個孩子節點（被稱為左孩子或右孩子）

2.1 滿二叉樹

特點：除最後一層無任何子節點外，每一層上的所有結點都有兩個子結點二叉樹。

2.2 完全二叉樹

特點：和滿二叉樹的差別是，它的最後一行可能不是完整的，但絕對是右方的連續部分缺失。即葉子結點隻可能在最大的兩層出現

2.2.1 堆（headq）

• 特點：

  堆是一顆完全二叉樹

  除了根節點之外的每個位置，該位置中存儲的鍵值大于等于其父節點的鍵值

2、AVL樹

3、伸展樹

4、(2,4)樹

5、紅黑樹

四、圖

1、圖

2、無向圖

3、有向圖

五、映射

1、映射

每個唯一的關鍵字（key）都被關聯到對應的一個值（value）上。這種關系被稱為映射（map）或關聯數組。

2、哈希表

一種，支援使用鍵作為索引的結構，文法如M[key]

2.1 哈希函數

哈希函數 h ：将每個鍵k映射到[0,N-1]區間内的整數，其中N是哈希表桶數組的容量

• 哈希碼
• 壓縮函數

2.2 桶數組

2.3 負載因子

3、跳躍表

六、集合