# 線性數據結構 > 開頭還是求點贊，求轉發！原創優質公眾號，希望大家能讓更多人看到我們的文章。 > > 圖片都是我們手繪的，可以說非常用心了！ ## 1. 數組 **數組（Array）** 是一種很常見的數據結構。它由相同類型的元素（element）組成，并且是使用一塊連續的內存來存儲。 我們直接可以利用元素的索引（index）可以計算出該元素對應的存儲地址。 數組的特點是：**提供隨機訪問** 并且容量有限。 ```java 假如數組的長度為 n。 訪問：O（1）//訪問特定位置的元素 插入：O（n ）//最壞的情況發生在插入發生在數組的首部并需要移動所有元素時 刪除：O（n）//最壞的情況發生在刪除數組的開頭發生并需要移動第一元素后面所有的元素時 ```  ## 2. 鏈表 ### 2.1. 鏈表簡介 **鏈表（LinkedList）** 雖然是一種線性表，但是并不會按線性的順序存儲數據，使用的不是連續的內存空間來存儲數據。 鏈表的插入和刪除操作的復雜度為 O(1) ，只需要知道目標位置元素的上一個元素即可。但是，在查找一個節點或者訪問特定位置的節點的時候復雜度為 O(n) 。 使用鏈表結構可以克服數組需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間,實現靈活的內存動態管理。但鏈表不會節省空間，相比于數組會占用更多的空間，因為鏈表中每個節點存放的還有指向其他節點的指針。除此之外，鏈表不具有數組隨機讀取的優點。 ### 2.2. 鏈表分類 **常見鏈表分類：** 1. 單鏈表 2. 雙向鏈表 3. 循環鏈表 4. 雙向循環鏈表 ```java 假如鏈表中有n個元素。 訪問：O（n）//訪問特定位置的元素 插入刪除：O（1）//必須要要知道插入元素的位置 ``` #### 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 的操作都發生在棧頂。** 棧常用一維數組或鏈表來實現，用數組實現的棧叫作 **順序棧** ，用鏈表實現的棧叫作 **鏈式棧** 。 ```java 假設堆棧中有n個元素。 訪問：O（n）//最壞情況 插入刪除：O（1）//頂端插入和刪除元素 ```  ### 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`。 ```java 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(); } ``` #### 3.2.3. 反轉字符串 將字符串中的每個字符先入棧再出棧就可以了。 #### 3.2.4. 維護函數調用 最后一個被調用的函數必須先完成執行，符合棧的 **后進先出（LIFO, Last In First Out）** 特性。 ### 3.3. 棧的實現 棧既可以通過數組實現，也可以通過鏈表來實現。不管基于數組還是鏈表，入棧、出棧的時間復雜度都為 O(1)。 下面我們使用數組來實現一個棧，并且這個棧具有`push()`、`pop()`（返回棧頂元素并出棧）、`peek()` （返回棧頂元素不出棧）、`isEmpty()`、`size()`這些基本的方法。 > 提示：每次入棧之前先判斷棧的容量是否夠用，如果不夠用就用`Arrays.copyOf()`進行擴容； ```java public class MyStack { private int[] storage;//存放棧中元素的數組 private int capacity;//棧的容量 private int count;//棧中元素數量 private static final int GROW_FACTOR = 2; //不帶初始容量的構造方法。默認容量為8 public 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; } } ``` 驗證 ```java 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. ``` ## 4. 隊列 ### 4.1. 隊列簡介 **隊列** 是 **先進先出( FIFO，First In, First Out)** 的線性表。在具體應用中通常用鏈表或者數組來實現，用數組實現的隊列叫作 **順序隊列** ，用鏈表實現的隊列叫作 **鏈式隊列** 。**隊列只允許在后端（rear）進行插入操作也就是 入隊 enqueue，在前端（front）進行刪除操作也就是出隊 dequeue** 隊列的操作方式和堆棧類似，唯一的區別在于隊列只允許新數據在后端進行添加。 ```java 假設隊列中有n個元素。 訪問：O（n）//最壞情況 插入刪除：O（1）//后端插入前端刪除元素 ```  ### 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 內核進程隊列（按優先級排隊） - 現實生活中的派對，播放器上的播放列表; - 消息隊列 - 等等......