## 26 驚嘆面試官：由淺入深手寫隊列 ## 引導語 現在不少大廠面試的時候會要求手寫代碼，我曾經看過一個大廠面試時，要求在線寫代碼，題目就是：在不使用 Java 現有隊列 API 的情況下，手寫出一個隊列的實現出來，隊列的數據結構，入隊和出隊方式都自己定義。 這題其實考察的有幾個點： 1. 考察你對隊列的內部結構熟不熟悉； 2. 考察你定義 API 的功底； 3. 考察寫代碼的基本功，代碼風格。 本章就和大家一起，結合以上幾點，手寫一個隊列出來，一起來熟悉一下思路和過程，完整隊列代碼見：demo.four.DIYQueue 和 demo.four.DIYQueueDemo ### 1 接口定義 在實現隊列之前，我們首先需要定義出隊列的接口，就是我們常說的 API，API 是我們隊列的門面，定義時主要原則就是簡單和好用。 我們這次實現的隊列只定義放數據和拿數據兩個功能，接口定義如下： ``` /** * 定義隊列的接口，定義泛型，可以讓使用者放任意類型到隊列中去 * author wenhe * date 2019/9/1 */ public interface Queue<T> { /** * 放數據 * @param item 入參 * @return true 成功、false 失敗 */ boolean put(T item); /** * 拿數據，返回一個泛型值 * @return */ T take(); // 隊列中元素的基本結構 class Node<T> { // 數據本身 T item; // 下一個元素 Node<T> next; // 構造器 public Node(T item) { this.item = item; } } } ``` 有幾點我們說明下： 1. 定義接口時，一定要寫注釋，接口的注釋，方法的注釋等等，這樣別人看我們的接口時，會輕松很多‘； 2. 定義接口時，要求命名簡潔明了，最好讓別人一看見命名就知道這個接口是干啥的，比如我們命名為 Queue，別人一看就清楚這個接口是和隊列相關的； 3. 用好泛型，因為我們不清楚放進隊列中的到底都是那些值，所以我們使用了泛型 T，表示可以在隊列中放任何值； 4. 接口里面無需給方法寫上 public 方法，因為接口中的方法默認都是 public 的，你寫上編譯器也會置灰，如下圖：  5. 我們在接口中定義了基礎的元素 Node，這樣隊列子類如果想用的話，可以直接使用，增加了復用的可能性。 ### 2 隊列子類實現 接著我們就要開始寫子類實現了，我們準備寫個最常用的鏈表數據結構的隊列。 #### 2.1 數據結構 底層數據結構我們采用鏈表，一說到鏈表，大家應該馬上就會想到三個關鍵要素：鏈表頭、鏈表尾和鏈表元素，我們也實現了，代碼如下： ``` /** * 隊列頭 */ private volatile Node<T> head; /** * 隊列尾 */ private volatile Node<T> tail; /** * 自定義隊列元素 */ class DIYNode extends Node<T>{ public DIYNode(T item) { super(item); } } ``` 除了這些元素之外，我們還有隊列容器的容量大小、隊列目前的使用大小、放數據鎖、拿數據鎖等等，代碼如下： ``` /** * 隊列的大小，使用 AtomicInteger 來保證其線程安全 */ private AtomicInteger size = new AtomicInteger(0); /** * 容量 */ private final Integer capacity; /** * 放數據鎖 */ private ReentrantLock putLock = new ReentrantLock(); /** * 拿數據鎖 */ private ReentrantLock takeLock = new ReentrantLock(); ``` #### 2.2 初始化 我們提供了使用默認容量（Integer 的最大值）和指定容量兩種方式，代碼如下： ``` /** * 無參數構造器，默認最大容量是 Integer.MAX_VALUE */ public DIYQueue() { capacity = Integer.MAX_VALUE; head = tail = new DIYNode(null); } /** * 有參數構造器，可以設定容量的大小 * @param capacity */ public DIYQueue(Integer capacity) { // 進行邊界的校驗 if(null == capacity || capacity < 0){ throw new IllegalArgumentException(); } this.capacity = capacity; head = tail = new DIYNode(null); } ``` #### 2.3 put 方法的實現 ``` public boolean put(T item) { // 禁止空數據 if(null == item){ return false; } try{ // 嘗試加鎖，500 毫秒未獲得鎖直接被打斷 boolean lockSuccess = putLock.tryLock(300, TimeUnit.MILLISECONDS); if(!lockSuccess){ return false; } // 校驗隊列大小 if(size.get() >= capacity){ log.info("queue is full"); return false; } // 追加到隊尾 tail = tail.next = new DIYNode(item); // 計數 size.incrementAndGet(); return true; } catch (InterruptedException e){ log.info("tryLock 500 timeOut", e); return false; } catch(Exception e){ log.error("put error", e); return false; } finally { putLock.unlock(); } } ``` put 方法的實現有幾點我們需要注意的是： 1. 注意 try catch finally 的節奏，catch 可以捕捉多種類型的異常，我們這里就捕捉了超時異常和未知異常，在 finally 里面一定記得要釋放鎖，不然鎖不會自動釋放的，這個一定不能用錯，體現了我們代碼的準確性； 2. 必要的邏輯檢查還是需要的，比如入參是否為空的空指針檢查，隊列是否滿的臨界檢查，這些檢查代碼可以體現出我們邏輯的嚴密性； 3. 在代碼的關鍵地方加上日志和注釋，這點也是非常重要的，我們不希望關鍵邏輯代碼注釋和日志都沒有，不利于閱讀代碼和排查問題； 4. 注意線程安全，此處實現我們除了加鎖之外，對于容量的大小（size）我們選擇線程安全的計數類：AtomicInteger，來保證了線程安全； 5. 加鎖的時候，我們最好不要使用永遠阻塞的方法，我們一定要用帶有超時時間的阻塞方法，此處我們設置的超時時間是 300 毫秒，也就是說如果 300 毫秒內還沒有獲得鎖，put 方法直接返回 false，當然時間大小你可以根據情況進行設置； 6. 根據不同的情況設置不同的返回值，put 方法返回的是 false，在發生異常時，我們可以選擇返回 false，或者直接拋出異常； 7. put 數據時追加到隊尾的，所以我們只需要把新數據轉化成 DIYNode，放到隊列的尾部即可。 #### 2.4 take 方法的實現 take 方法和 put 方法的實現非常類似，只不過 take 是從頭部拿取數據，代碼實現如下： ``` public T take() { // 隊列是空的，返回 null if(size.get() == 0){ return null; } try { // 拿數據我們設置的超時時間更短 boolean lockSuccess = takeLock.tryLock(200,TimeUnit.MILLISECONDS); if(!lockSuccess){ throw new RuntimeException("加鎖失敗"); } // 把頭結點的下一個元素拿出來 Node expectHead = head.next; // 把頭結點的值拿出來 T result = head.item; // 把頭結點的值置為 null，幫助 gc head.item = null; // 重新設置頭結點的值 head = (DIYNode) expectHead; size.decrementAndGet(); // 返回頭結點的值 return result; } catch (InterruptedException e) { log.info(" tryLock 200 timeOut",e); } catch (Exception e) { log.info(" take error ",e); }finally { takeLock.unlock(); } return null; } ``` 通過以上幾步，我們的隊列已經寫完了，完整代碼見：demo.four.DIYQueue。 ### 3 測試 API 寫好了，接下來我們要針對 API 寫一些場景測試和單元測試，我們先寫個場景測試，看看 API 能否跑通，代碼如下： ``` @Slf4j public class DIYQueueDemo { // 我們需要測試的隊列 private final static Queue<String> queue = new DIYQueue<>(); // 生產者 class Product implements Runnable{ private final String message; public Product(String message) { this.message = message; } @Override public void run() { try { boolean success = queue.put(message); if (success) { log.info("put {} success", message); return; } log.info("put {} fail", message); } catch (Exception e) { log.info("put {} fail", message); } } } // 消費者 class Consumer implements Runnable{ @Override public void run() { try { String message = (String) queue.take(); log.info("consumer message :{}",message); } catch (Exception e) { log.info("consumer message fail",e); } } } // 場景測試 @Test public void testDIYQueue() throws InterruptedException { ThreadPoolExecutor executor = new ThreadPoolExecutor(10,10,0,TimeUnit.MILLISECONDS, new LinkedBlockingQueue<>()); for (int i = 0; i < 1000; i++) { // 是偶數的話，就提交一個生產者，奇數的話提交一個消費者 if(i % 2 == 0){ executor.submit(new Product(i+"")); continue; } executor.submit(new Consumer()); } Thread.sleep(10000); } ``` 代碼測試的場景比較簡單，從 0 開始循環到 1000，如果是偶數，就讓生產者去生產數據，并放到隊列中，如果是奇數，就讓消費者去隊列中拿數據出來進行消費，運行之后的結果如下：  從顯示的結果來看，咱們寫的 DIYQueue 沒有太大的問題，當然如果想大規模的使用，還需要詳細的單元測試和性能測試。 #### 4 總結 通過本章的學習，不知道你有沒有一種隊列很簡單的感覺，其實隊列本身就很簡單，沒有想象的那么復雜。 只要我們懂得了隊列的基本原理，清楚幾種常用的數據結構，手寫隊列問題其實并不大，你也趕緊來試一試吧。