數據結構與算法系列七（隊列）
- 2020 年 3 月 2 日
- 筆記
有人說，數據結構與算法，計算機網絡，與操作系統都一樣，脫離日常開發，除了面試這輩子可能都用不到呀！
有人說，我是做業務開發的，只要熟練API，熟練框架，熟練各種中間件，寫的代碼不也能“飛”起來嗎？
於是問題來了：為什麼還要學習數據結構與算法呢？
#理由一： 面試的時候，千萬不要被數據結構與算法拖了後腿 #理由二： 你真的願意做一輩子CRUD Boy嗎 #理由三： 不想寫出開源框架，中間件的工程師，不是好廚子
我想好了，還是需要學習數據結構與算法。但是我有兩個困惑：
1.如何着手學習呢？
2.有哪些內容要學習呢？
學習方法推薦：
#學習方法 1.從基礎開始，系統化學習 2.多動手，每一種數據結構與算法，都自己用代碼實現出來 3.思路更重要：理解實現思想，不要背代碼 4.與日常開發結合，對應應用場景
學習內容推薦：
數據結構與算法內容比較多，我們本着實用原則，學習經典的、常用的數據結構、與常用算法
#學習內容： 1.數據結構的定義 2.算法的定義 3.複雜度分析 4.常用數據結構 數組、鏈表、棧、隊列 散列表、二叉樹、堆 跳錶、圖 5.常用算法 遞歸、排序、二分查找 搜索、哈希、貪心、分治 動態規劃、字符串匹配
你還記得在數組那一篇中，我們說過基於線性表的數據結構有哪些嗎？它們是：數組、鏈表、棧、隊列。
上一篇【數據結構與算法系列六（棧）】中，我們已經詳細了解了棧這種數據結構：棧是一種操作受限的數據結構。隊列是基於線性表的數據結構中，最後一種了，很巧！它也是一種操作受限的數據結構。
隊列同樣可以基於數組實現：順序隊列；也可以基於鏈表實現：鏈式隊列。
那麼問題來了：具體如何實現一個隊列呢？它都有哪些應用場景呢？
#考考你： 1.你能用自己的話描述隊列嗎？ 2.你知道常見的隊列分類嗎？ 3.你知道隊列代碼實現的關鍵嗎？ 4.你知道如何實現一個循環隊列嗎？ 5.你知道隊列的常見的應用場景嗎？
隊列是一種基於線性表的數據結構，與棧一樣，都是操作受限的數據結構。棧的特點是後進先出，而隊列的特點是先進先出（FIFO），就像我們平常在火車站排隊候車一樣。
隊列有兩頭：隊頭，和隊尾。從隊頭出隊元素，在隊尾入隊新的元素。
package com.anan.struct.linetable; /** * 順序隊列：基於數組實現 * @param <E> */ public class ArrayQueue<E> { private Object[] items; private int n; // 隊列需要兩個下標：對頭下標索引、隊尾下標索引 private int head; private int tail; public ArrayQueue(int capacity){ this.items = new Object[capacity]; this.n = capacity; } /** * 入隊操作： */ public boolean enqueue(E e){ // 檢查隊列是否滿 // 隊列滿條件 tail==n && head == 0 if(tail == n){ // 檢查對頭是否沒有出隊 if(head == 0){ return false; } // 如果已經有元素出隊，則向對頭移動數據 for (int i = head; i < tail ; i++) { items[i - head] = items[i]; } tail = tail - head; head = 0; } // 入隊 items[tail] = e; tail ++; return true; } /** * 出隊操作： */ public E dequeue(){ // 檢查隊列是否空 // 隊列空條件：head == tail if(head == tail){ return null; } // 出隊 E e = (E)items[head]; head ++; return e; } }
測試代碼：
package com.anan.struct.linetable; /** * 測試隊列 */ public class ArrayQueueTest { public static void main(String[] args) { // 1.創建隊列 int capacity = 10; ArrayQueue<Integer> queue = new ArrayQueue<Integer>(capacity); System.out.println("1.創建隊列---------隊列容量：" + capacity); // 2.入隊操作 System.out.println("2.入隊操作---------"); int count = 5; for (int i = 0; i < count; i++) { queue.enqueue(i); System.out.println("入隊元素：" + i); } // 3.出隊操作 System.out.println("3.出隊操作---------"); for (int i = 0; i < count; i++) { System.out.println("出隊元素：" + queue.dequeue()); } } }
測試結果：
D: 2teach 1softjdk8binjava com.anan.struct.linetable.ArrayQueueTest 1.創建隊列---------隊列容量：10 2.入隊操作--------- 入隊元素：0 入隊元素：1 入隊元素：2 入隊元素：3 入隊元素：4 3.出隊操作--------- 出隊元素：0 出隊元素：1 出隊元素：2 出隊元素：3 出隊元素：4 Process finished with exit code 0
package com.anan.struct.linetable; /** * 循環隊列 */ public class CircularQueue<E> { private Object[] items; private int n; // 隊頭、對尾指針 private int head; private int tail; public CircularQueue(int capacity){ items = new Object[capacity]; n = capacity; } /** * 入隊操作 */ public boolean enqueue(E e){ // 判斷隊列是否滿 // 隊列滿條件：(tail + 1) % n == head if((tail + 1) % n == head){ return false; } items[tail] = e; tail = (tail + 1) % n; return true; } /** * 出隊操作 */ public E dequeue(){ // 判斷隊列是否空 // 隊列空條件：tail == head if(tail == head){ return null; } E e = (E)items[head]; head = (head + 1) % n; return e; } }
#考考你答案： 1.你能用自己的話描述隊列嗎？ 1.1.隊列是基於線性表的數據結構 1.2.隊列是一種操作受限的數據結構 1.3.隊列滿足先進先出（FIFO）的特點 1.4.隊列在隊頭出隊元素，在隊尾入隊元素 2.你知道常見的隊列分類嗎？ 2.1.從底層數據結構分類有：順序隊列、鏈式隊列 2.2.從實現特點分類有：循環隊列、阻塞隊列、並發隊列 3.你知道隊列代碼實現的關鍵嗎？ 3.1.隊列滿足先進先出（FIFO）特點 3.2.隊列在隊頭出隊元素，在隊尾入隊元素 3.3.實現隊列的關鍵： a.需要兩個指針：head、tail分別指向隊頭和隊尾 b.入隊時，判斷隊列滿條件：tail == n && head == 0 c.出隊時，判斷隊列空條件：tail == head 4.你知道如何實現一個循環隊列嗎？ 4.1.在案例中，基於數組實現了一個普通的隊列 4.2.入隊操作的時候，如果隊列滿，需要移動數據 // 如果隊列滿，且已經有元素出隊，則向對頭移動數據 for (int i = head; i < tail ; i++) { items[i - head] = items[i]; } 4.3.這樣會將入隊操作，時間複雜度從O(1)，轉變成O(n)，執行效率下降 4.4.有沒有更好的方式，保持入隊操作的時間複雜度為O(1)不變呢？ 4.5.答案是：通過循環隊列來實現 4.6.關於循環隊列的代碼，你可以參考【3.3】循環隊列實現 4.7.重點關注隊列滿的條件：(tail + 1) % n == head 4.8.看你是否能理解，歡迎留言我們一起討論 5.你知道隊列的常見的應用場景嗎？ 5.1.隊列主要針對有限資源控制的應用場景 5.2.比如數據庫連接池的應用 5.3.比如線程池的應用 5.4.如果你有興趣，可以看一下JUC中線程池的底層實現 5.5.JUC線程池的底層，應用了：阻塞隊列 5.6.通過隊列還能實現：生產者---消費者模型
