## 隊列概述 隊列，又稱為佇列（queue），是先進先出（FIFO, First-In-First-Out）的線性表。在具體應用中通常用鏈表或者數組來實現。隊列只允許在后端（稱為*rear*）進行插入操作，在前端（稱為*front*）進行刪除操作。隊列的操作方式和堆棧類似，唯一的區別在于隊列只允許新數據在后端進行添加。 　　在Java中隊列又可以分為兩個大類，一種是阻塞隊列和非阻塞隊列。 　　1、沒有實現阻塞接口： 　　1）實現java.util.Queue的LinkList, 　　2）實現java.util.AbstractQueue接口內置的不阻塞隊列：?PriorityQueue?和?ConcurrentLinkedQueue 　　2、實現阻塞接口的 　　java.util.concurrent 中加入了 BlockingQueue 接口和五個阻塞隊列類。它實質上就是一種帶有一點扭曲的 FIFO 數據結構。不是立即從隊列中添加或者刪除元素，線程執行操作阻塞，直到有空間或者元素可用。 　　五個隊列所提供的各有不同： 　　\* ArrayBlockingQueue?：一個由數組支持的有界隊列。 　　\* LinkedBlockingQueue?：一個由鏈接節點支持的可選有界隊列。 　　\* PriorityBlockingQueue?：一個由優先級堆支持的無界優先級隊列。 　　\* DelayQueue?：一個由優先級堆支持的、基于時間的調度隊列。 　　\* SynchronousQueue?：一個利用 BlockingQueue 接口的簡單聚集（rendezvous）機制。 　　隊列是Java中常用的數據結構，比如在線程池中就是用到了隊列，比如消息隊列等。 　　由隊列先入先出的特性，我們知道隊列數據的存儲結構可以兩種，一種是基于數組實現的，另一種則是基于單鏈實現。前者在創建的時候就已經確定了數組的長度，所以隊列的長度是固定的，但是可以循環使用數組，所以這種隊列也可以稱之為循環隊列。后者實現的隊列內部通過指針指向形成一個隊列，這種隊列是單向且長度不固定，所以也稱之為非循環隊列。下面我將使用兩種方式分別實現隊列。 ## 二、基于數組實現循環隊列 　　由于在往隊列中放數據或拉取數據的時候需要移動數組對應的下標，所以需要記錄一下隊尾和隊頭的位置。說一下幾個核心的屬性吧： 　　1、queue：隊列，object類型的數組，用于存儲數據，長度固定，當存儲的數據數量大于數組當度則拋出異常； 　　2、head：隊頭指針，int類型，用于記錄隊列頭部的位置信息。 　　3、tail：隊尾指針，int類型，用于記錄隊列尾部的位置信息。 　　4、size：隊列長度，隊列長度大于等于0或者小于等于數組長度。 ### 非線程安全隊列 ```java import java.util.Arrays; import java.util.concurrent.TimeUnit; /** * Created by Mr.zihan on 2021/12/18. * connect to cowboy2014@qq.com * 特點：基于數組實現的非線程安全的隊列 */ public class MyQueue { /** * 隊列管道，當管道中存放的數據大于隊列的長度時將不會再offer數據，直至從隊列中poll數據后 */ private Object[] queue; //隊列的頭部，獲取數據時總是從頭部獲取 private int head; //隊列尾部，push數據時總是從尾部添加 private int tail; //隊列長度 private int size; //數組中能存放數據的最大容量 private final static int MAX_CAPACITY = 1<<30; //數組長度 private int capacity; //最大下標 private int maxIndex; public MyQueue(int initialCapacity) { if (initialCapacity > MAX_CAPACITY) { throw new OutOfMemoryError("initialCapacity too large"); } if (initialCapacity <= 0) { throw new IndexOutOfBoundsException("initialCapacity must be more than zero"); } this.queue = new Object[initialCapacity]; this.capacity = initialCapacity; this.maxIndex = initialCapacity - 1; this.head = this.tail = -1; this.size = 0; } public MyQueue(){ queue = new Object[16]; capacity = 16; head = tail = -1; size = 0; maxIndex = 15; } /** * 往隊列尾部添加數據 * @param object 數據 */ public void offer(Object object){ if (size >= capacity){ System.out.println("queue's size more than or equal to array's capacity"); return; } if (++tail > maxIndex){ //循環隊列 tail = 0; } queue[tail] = object; size++; } /** * 從隊列頭部拉出數據 * @return 返回隊列的第一個數據 */ public Object poll(){ if (size <= 0){ System.out.println("the queue is null"); return null; } if (++head > maxIndex){ head = 0; } size--; Object old = queue[head]; queue[head] = null; return old; } ``` 這個隊列是非線程安全的。測試思路： 1. 使用一個線程不停發送數據； 2. 另外10個線程用來處理隊列中的數據，二者的速率相當，防止過早隊列滿或隊列空。 ``` public static void main(String[] args) { MyQueue myQueue = new MyQueue(); //啟動n個線程做真實推送 for (int i = 0; i < 10; i++) { new Thread(() -> { while (true) { try { long starTime = System.currentTimeMillis(); //獲取一條推送消息，此方法會進行不進行阻塞 String msg = (String) myQueue.poll(); //模擬推送耗時 TimeUnit.MILLISECONDS.sleep(10); if (null == msg){ continue; } long endTime = System.currentTimeMillis(); System.out.println(String.format("[%s,%s,take耗時:%s],%s,收到消息:%s", starTime, endTime, (endTime - starTime), Thread.currentThread().getName(), msg)); } catch (InterruptedException e) { e.printStackTrace(); } } }).start(); } // 定義一個線程發送消息 int i = 0; while (true){ myQueue.offer("消息編號" + i++); try { TimeUnit.MILLISECONDS.sleep(1); } catch (InterruptedException e) { e.printStackTrace(); } } } ``` 證據呈上，編號2138的消息被消費了好多遍： ``` [1639817508763,1639817508773,take耗時:10],Thread-5,收到消息:消息編號2138 [1639817508763,1639817508773,take耗時:10],Thread-1,收到消息:消息編號2139 the queue is null [1639817508763,1639817508773,take耗時:10],Thread-4,收到消息:消息編號2140 the queue is null [1639817508763,1639817508773,take耗時:10],Thread-9,收到消息:消息編號2138 the queue is null [1639817508763,1639817508773,take耗時:10],Thread-7,收到消息:消息編號2138 ``` ### 優化為線程安全隊列 #### 使用volatile ``` private volatile Object[] queue; //隊列的頭部，獲取數據時總是從頭部獲取 private volatile int head; //隊列尾部，push數據時總是從尾部添加 private volatile int tail; ``` #### 使用synchronized關鍵字 #### 使用ReentrantLock #### 使用CAS ## 參考資料 1. [教你如何使用Java手寫一個基于數組實現的隊列](ttps://www.cnblogs.com/rainple/p/9988341.html)