線性數據結構

1. 數組

數組（Array） 是一種很常見的數據結構。它由相同類型的元素（element）組成，并且是使用一塊連續的內存來存儲。

我們直接可以利用元素的索引（index）可以計算出該元素對應的存儲地址。

數組的特點是：提供隨機訪問 并且容量有限。

假如數組的長度為 n。
訪問：O（1）//訪問特定位置的元素
插入：O（n ）//最壞的情況發生在插入發生在數組的首部并需要移動所有元素時
刪除：O（n）//最壞的情況發生在刪除數組的開頭發生并需要移動第一元素后面所有的元素時Copy to clipboardErrorCopied

2. 鏈表

2.1. 鏈表簡介

鏈表（LinkedList） 雖然是一種線性表，但是并不會按線性的順序存儲數據，使用的不是連續的內存空間來存儲數據。

鏈表的插入和刪除操作的復雜度為 O(1) ，只需要知道目標位置元素的上一個元素即可。但是，在查找一個節點或者訪問特定位置的節點的時候復雜度為 O(n) 。

使用鏈表結構可以克服數組需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間,實現靈活的內存動態管理。但鏈表不會節省空間，相比于數組會占用更多的空間，因為鏈表中每個節點存放的還有指向其他節點的指針。除此之外，鏈表不具有數組隨機讀取的優點。

2.2. 鏈表分類

常見鏈表分類：

1. 單鏈表
2. 雙向鏈表
3. 循環鏈表
4. 雙向循環鏈表

假如鏈表中有n個元素。
訪問：O（n）//訪問特定位置的元素
插入刪除：O（1）//必須要要知道插入元素的位置Copy to clipboardErrorCopied

2.2.1. 單鏈表

單鏈表 單向鏈表只有一個方向，結點只有一個后繼指針 next 指向后面的節點。因此，鏈表這種數據結構通常在物理內存上是不連續的。我們習慣性地把第一個結點叫作頭結點，鏈表通常有一個不保存任何值的 head 節點(頭結點)，通過頭結點我們可以遍歷整個鏈表。尾結點通常指向 null。

2.2.2. 循環鏈表

循環鏈表 其實是一種特殊的單鏈表，和單鏈表不同的是循環鏈表的尾結點不是指向 null，而是指向鏈表的頭結點。

2.2.3. 雙向鏈表

雙向鏈表 包含兩個指針，一個 prev 指向前一個節點，一個 next 指向后一個節點。

2.2.4. 雙向循環鏈表

雙向循環鏈表 最后一個節點的 next 指向 head，而 head 的 prev 指向最后一個節點，構成一個環。

2.3. 應用場景

• 如果需要支持隨機訪問的話，鏈表沒辦法做到。
• 如果需要存儲的數據元素的個數不確定，并且需要經常添加和刪除數據的話，使用鏈表比較合適。
• 如果需要存儲的數據元素的個數確定，并且不需要經常添加和刪除數據的話，使用數組比較合適。

2.4. 數組 vs 鏈表

• 數組支持隨機訪問，而鏈表不支持。
• 數組使用的是連續內存空間對 CPU 的緩存機制友好，鏈表則相反。
• 數組的大小固定，而鏈表則天然支持動態擴容。如果聲明的數組過小，需要另外申請一個更大的內存空間存放數組元素，然后將原數組拷貝進去，這個操作是比較耗時的！

3. 棧

3.1. 棧簡介

棧 (stack)只允許在有序的線性數據集合的一端（稱為棧頂 top）進行加入數據（push）和移除數據（pop）。因而按照 后進先出（LIFO, Last In First Out） 的原理運作。在棧中，push 和 pop 的操作都發生在棧頂。

棧常用一維數組或鏈表來實現，用數組實現的棧叫作 順序棧 ，用鏈表實現的棧叫作 鏈式棧 。

假設堆棧中有n個元素。
訪問：O（n）//最壞情況
插入刪除：O（1）//頂端插入和刪除元素Copy to clipboardErrorCopied

3.2. 棧的常見應用常見應用場景

當我們我們要處理的數據只涉及在一端插入和刪除數據，并且滿足 后進先出（LIFO, Last In First Out） 的特性時，我們就可以使用棧這個數據結構。

3.2.1. 實現瀏覽器的回退和前進功能

我們只需要使用兩個棧(Stack1 和 Stack2)和就能實現這個功能。比如你按順序查看了 1,2,3,4 這四個頁面，我們依次把 1,2,3,4 這四個頁面壓入 Stack1 中。當你想回頭看 2 這個頁面的時候，你點擊回退按鈕，我們依次把 4,3 這兩個頁面從 Stack1 彈出，然后壓入 Stack2 中。假如你又想回到頁面 3，你點擊前進按鈕，我們將 3 頁面從 Stack2 彈出，然后壓入到 Stack1 中。示例圖如下:

3.2.2. 檢查符號是否成對出現

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷該字符串是否有效。

有效字符串需滿足：

1. 左括號必須用相同類型的右括號閉合。
2. 左括號必須以正確的順序閉合。

比如 “()”、"()[]{}"、"{[]}" 都是有效字符串，而 “(]” 、"([)]" 則不是。

這個問題實際是 Leetcode 的一道題目，我們可以利用棧 Stack 來解決這個問題。

1. 首先我們將括號間的對應規則存放在 Map 中，這一點應該毋容置疑；
2. 創建一個棧。遍歷字符串，如果字符是左括號就直接加入stack中，否則將stack 的棧頂元素與這個括號做比較，如果不相等就直接返回 false。遍歷結束，如果stack為空，返回 true。

public boolean isValid(String s){// 括號之間的對應規則HashMap<Character, Character> mappings = new HashMap<Character, Character>();mappings.put(')', '(');mappings.put('}', '{');mappings.put(']', '[');Stack<Character> stack = new Stack<Character>();char[] chars = s.toCharArray();for (int i = 0; i < chars.length; i++) {if (mappings.containsKey(chars[i])) {char topElement = stack.empty() ? '#' : stack.pop();if (topElement != mappings.get(chars[i])) {return false;}} else {stack.push(chars[i]);}}return stack.isEmpty();
}Copy to clipboardErrorCopied

3.2.3. 反轉字符串

將字符串中的每個字符先入棧再出棧就可以了。

3.2.4. 維護函數調用

最后一個被調用的函數必須先完成執行，符合棧的 后進先出（LIFO, Last In First Out） 特性。

3.3. 棧的實現

棧既可以通過數組實現，也可以通過鏈表來實現。不管基于數組還是鏈表，入棧、出棧的時間復雜度都為 O(1)。

下面我們使用數組來實現一個棧，并且這個棧具有push()、pop()（返回棧頂元素并出棧）、peek() （返回棧頂元素不出棧）、isEmpty()、size()這些基本的方法。

提示：每次入棧之前先判斷棧的容量是否夠用，如果不夠用就用Arrays.copyOf()進行擴容；

public class MyStack {private int[] storage;//存放棧中元素的數組private int capacity;//棧的容量private int count;//棧中元素數量private static final int GROW_FACTOR = 2;//不帶初始容量的構造方法。默認容量為8public MyStack() {this.capacity = 8;this.storage=new int[8];this.count = 0;}//帶初始容量的構造方法public MyStack(int initialCapacity) {if (initialCapacity < 1)throw new IllegalArgumentException("Capacity too small.");this.capacity = initialCapacity;this.storage = new int[initialCapacity];this.count = 0;}//入棧public void push(int value) {if (count == capacity) {ensureCapacity();}storage[count++] = value;}//確保容量大小private void ensureCapacity() {int newCapacity = capacity * GROW_FACTOR;storage = Arrays.copyOf(storage, newCapacity);capacity = newCapacity;}//返回棧頂元素并出棧private int pop() {if (count == 0)throw new IllegalArgumentException("Stack is empty.");count--;return storage[count];}//返回棧頂元素不出棧private int peek() {if (count == 0){throw new IllegalArgumentException("Stack is empty.");}else {return storage[count-1];}}//判斷棧是否為空private boolean isEmpty() {return count == 0;}//返回棧中元素的個數private int size() {return count;}}Copy to clipboardErrorCopied

驗證

MyStack myStack = new MyStack(3);
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.push(5);
myStack.push(6);
myStack.push(7);
myStack.push(8);
System.out.println(myStack.peek());//8
System.out.println(myStack.size());//8
for (int i = 0; i < 8; i++) {System.out.println(myStack.pop());
}
System.out.println(myStack.isEmpty());//true
myStack.pop();//報錯：java.lang.IllegalArgumentException: Stack is empty.Copy to clipboardErrorCopied

4. 隊列

4.1. 隊列簡介

隊列 是 先進先出( FIFO，First In, First Out) 的線性表。在具體應用中通常用鏈表或者數組來實現，用數組實現的隊列叫作 順序隊列 ，用鏈表實現的隊列叫作 鏈式隊列 。隊列只允許在后端（rear）進行插入操作也就是 入隊 enqueue，在前端（front）進行刪除操作也就是出隊 dequeue

隊列的操作方式和堆棧類似，唯一的區別在于隊列只允許新數據在后端進行添加。

假設隊列中有n個元素。
訪問：O（n）//最壞情況
插入刪除：O（1）//后端插入前端刪除元素Copy to clipboardErrorCopied

4.2. 隊列分類

4.2.1. 單隊列

單隊列就是常見的隊列, 每次添加元素時，都是添加到隊尾。單隊列又分為 順序隊列（數組實現） 和 鏈式隊列（鏈表實現）。

順序隊列存在“假溢出”的問題也就是明明有位置卻不能添加的情況。

假設下圖是一個順序隊列，我們將前兩個元素 1,2 出隊，并入隊兩個元素 7,8。當進行入隊、出隊操作的時候，front 和 rear 都會持續往后移動，當 rear 移動到最后的時候,我們無法再往隊列中添加數據，即使數組中還有空余空間，這種現象就是 ”假溢出“ 。除了假溢出問題之外，如下圖所示，當添加元素 8 的時候，rear 指針移動到數組之外（越界）。

為了避免當只有一個元素的時候，隊頭和隊尾重合使處理變得麻煩，所以引入兩個指針，front 指針指向對頭元素，rear 指針指向隊列最后一個元素的下一個位置，這樣當 front 等于 rear 時，此隊列不是還剩一個元素，而是空隊列。——From 《大話數據結構》

4.2.2. 循環隊列

循環隊列可以解決順序隊列的假溢出和越界問題。解決辦法就是：從頭開始，這樣也就會形成頭尾相接的循環，這也就是循環隊列名字的由來。

還是用上面的圖，我們將 rear 指針指向數組下標為 0 的位置就不會有越界問題了。當我們再向隊列中添加元素的時候， rear 向后移動。

順序隊列中，我們說 front==rear 的時候隊列為空，循環隊列中則不一樣，也可能為滿，如上圖所示。解決辦法有兩種：

1. 可以設置一個標志變量 flag,當 front==rear 并且 flag=0 的時候隊列為空，當front==rear 并且 flag=1 的時候隊列為滿。
2. 隊列為空的時候就是 front==rear ，隊列滿的時候，我們保證數組還有一個空閑的位置，rear 就指向這個空閑位置，如下圖所示，那么現在判斷隊列是否為滿的條件就是： (rear+1) % QueueSize= front 。

4.3. 常見應用場景

當我們需要按照一定順序來處理數據的時候可以考慮使用隊列這個數據結構。

• 阻塞隊列： 阻塞隊列可以看成在隊列基礎上加了阻塞操作的隊列。當隊列為空的時候，出隊操作阻塞，當隊列滿的時候，入隊操作阻塞。使用阻塞隊列我們可以很容易實現“生產者 - 消費者“模型。
• 線程池中的請求/任務隊列： 線程池中沒有空閑線程時，新的任務請求線程資源時，線程池該如何處理呢？答案是將這些請求放在隊列中，當有空閑線程的時候，會循環中反復從隊列中獲取任務來執行。隊列分為無界隊列(基于鏈表)和有界隊列(基于數組)。無界隊列的特點就是可以一直入列，除非系統資源耗盡，比如 ：FixedThreadPool 使用無界隊列 LinkedBlockingQueue。但是有界隊列就不一樣了，當隊列滿的話后面再有任務/請求就會拒絕，在 Java 中的體現就是會拋出java.util.concurrent.RejectedExecutionException 異常。
• Linux 內核進程隊列（按優先級排隊）
• 現實生活中的派對，播放器上的播放列表;
• 消息隊列
• 等等…

樹

樹就是一種類似現實生活中的樹的數據結構（倒置的樹）。任何一顆非空樹只有一個根節點。

一棵樹具有以下特點：

1. 一棵樹中的任意兩個結點有且僅有唯一的一條路徑連通。
2. 一棵樹如果有 n 個結點，那么它一定恰好有 n-1 條邊。
3. 一棵樹不包含回路。

下圖就是一顆樹，并且是一顆二叉樹。

如上圖所示，通過上面這張圖說明一下樹中的常用概念：

• 節點 ：樹中的每個元素都可以統稱為節點。
• 根節點 ：頂層節點或者說沒有父節點的節點。上圖中 A 節點就是根節點。
• 父節點 ：若一個節點含有子節點，則這個節點稱為其子節點的父節點。上圖中的 B 節點是 D 節點、E 節點的父節點。
• 子節點 ：一個節點含有的子樹的根節點稱為該節點的子節點。上圖中 D 節點、E 節點是 B 節點的子節點。
• 兄弟節點 ：具有相同父節點的節點互稱為兄弟節點。上圖中 D 節點、E 節點的共同父節點是 B 節點，故 D 和 E 為兄弟節點。
• 葉子節點 ：沒有子節點的節點。上圖中的 D、F、H、I 都是葉子節點。
• 節點的高度 ：該節點到葉子節點的最長路徑所包含的邊數。
• 節點的深度 ：根節點到該節點的路徑所包含的邊數
• 節點的層數 ：節點的深度+1。
• 樹的高度 ：根節點的高度。

二叉樹的分類

二叉樹（Binary tree）是每個節點最多只有兩個分支（即不存在分支度大于 2 的節點）的樹結構。

二叉樹 的分支通常被稱作“左子樹”或“右子樹”。并且，二叉樹 的分支具有左右次序，不能隨意顛倒。

二叉樹 的第 i 層至多擁有 2^(i-1) 個節點，深度為 k 的二叉樹至多總共有 2^k-1 個節點

滿二叉樹

一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是 滿二叉樹。也就是說，如果一個二叉樹的層數為 K，且結點總數是(2^k) -1 ，則它就是 滿二叉樹。如下圖所示：

完全二叉樹

除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者是在右邊缺少連續若干節點，則這個二叉樹就是 完全二叉樹 。

大家可以想象為一棵樹從根結點開始擴展，擴展完左子節點才能開始擴展右子節點，每擴展完一層，才能繼續擴展下一層。如下圖所示：

完全二叉樹有一個很好的性質：父結點和子節點的序號有著對應關系。

細心的小伙伴可能發現了，當根節點的值為 1 的情況下，若父結點的序號是 i，那么左子節點的序號就是 2i，右子節點的序號是 2i+1。這個性質使得完全二叉樹利用數組存儲時可以極大地節省空間，以及利用序號找到某個節點的父結點和子節點，后續二叉樹的存儲會詳細介紹。

平衡二叉樹

紅黑樹

二叉樹的存儲

鏈式存儲

順序存儲

二叉樹的遍歷

先序遍歷

public void preOrder(TreeNode root){if(root == null){return;}system.out.println(root.data);preOrder(root.left);preOrder(root.right);
}Copy to clipboardErrorCopied

中序遍歷

public void inOrder(TreeNode root){if(root == null){return;}inOrder(root.left);system.out.println(root.data);inOrder(root.right);
}Copy to clipboardErrorCopied

后序遍歷

public void postOrder(TreeNode root){if(root == null){return;}postOrder(root.left);postOrder(root.right);system.out.println(root.data);
}

圖

圖的基本概念

頂點

邊

度

無向圖和有向圖

無權圖和帶權圖

圖的存儲

鄰接矩陣存儲

鄰接表存儲

圖的搜索

廣度優先搜索

深度優先搜索

堆

什么是堆

堆的用途

堆的分類

堆的存儲

堆的操作

插入元素

刪除堆頂元素

自底向上堆化

自頂向下堆化

堆的操作總結

堆排序

建堆

排序

排序