Java 隊列接口及其實現

在這裡，我們將討論 Java Queue 接口。您將了解什麼是隊列數據結構，它在 Java 中是如何表示的，哪些方法對所有隊列最重要。此外，Queue 的哪些實現是用 Java 語言編寫的。之後，我們將仔細研究最重要的實現並通過示例來學習它們。

隊列數據結構

隊列是一種線性抽像數據結構，具有特定的執行操作順序——先進先出 (FIFO)。這意味著您只能在結構的末尾添加一個元素（或入隊，放入隊列），並且只能從其開頭獲取一個元素（出隊或從隊列中刪除）。你可以很容易地想像隊列數據結構。這看起來就像現實生活中的隊列或客戶隊列。先來的顧客，也將先得到服務。如果你有四個人在麥當勞或其他地方排隊，那麼第一個排隊的人將第一個拿到商店。如果新顧客來了，他/她將排在第 5 位去買漢堡包。 所以，在使用隊列時，新元素被添加到末尾，如果你想獲取一個元素，它將從頭開始獲取。這是經典隊列數據結構工作的主要原理。

Java中的隊列

Java中的隊列是一個接口。根據 Oracle 文檔，Queue 接口有 2 個超接口、4 個繼承自隊列的不同接口，以及一個極其令人印象深刻的類列表。 這是什麼意思？首先，Java Queue是Collection Framework的一部分，實現了Collection接口。所以它支持Collection接口的所有方法，如插入、刪除等。Queue 實現 Iterable 接口，允許對象成為“for-each 循環”語句的目標。

隊列方法 Java

Queue 聲明了許多方法。作為接口的方法，它們應該在所有實現 Queue 的類中表示。最重要的隊列方法，Java：

• Boolean offer() – 如果可能，將一個新元素插入隊列
• Boolean add(E e) – 如果可能，將一個新元素插入隊列。如果成功則返回 true，如果沒有空間則拋出 IllegalStateException。
• Object poll() – 從 的頭部檢索並刪除一個元素。如果隊列為空，則返回 null。
• Object remove() – 從隊列頭部檢索並刪除一個元素。
• Object peek() – 檢索但不從隊列頭部移除元素。如果隊列為空，則返回 null。
• Object element() – 檢索但不從隊列頭部移除元素。

Java隊列的子接口

Queue接口由 4 個子接口繼承——BlockingDeque<E>、BlockingQueue<E>、Deque<E>、TransferQueue<E>。您可以將它們分為 3 組：Deques、Blocking Queues 和 Transfer Queues，其中 BlockingDeque 屬於前兩者。讓我們來看看這些群體。

德奎斯

Deque 的意思是雙端隊列，它支持從作為隊列（先進先出/FIFO）的數據尾部添加或刪除數據，或者作為另一種流行的稱為堆棧（後進先出）的數據結構從頭部添加或刪除先出/後進先出）。 實現Deque接口的類： ArrayDeque、ConcurrentLinkedDeque、LinkedBlockingDeque、LinkedList。

阻塞隊列

阻塞隊列是在兩種情況下阻塞線程的隊列：

• 線程試圖從空隊列中獲取元素
• 線程試圖將元素放入完整隊列

當一個線程試圖從一個空隊列中獲取項目時，它會等待直到其他線程將項目放入隊列中。類似地，當一個線程試圖將元素放入一個已滿的隊列時，它會一直等到其他線程將元素從隊列中取出來為元素獲取可用空間。當然，“滿隊列”的概念意味著隊列的大小是有限的，這通常在構造函數中指定。標準阻塞隊列包括 LinkedBlockingQueue、SynchronousQueue 和 ArrayBlockingQueue。BlockingQueue接口的實現類：ArrayBlockingQueue、DelayQueue、LinkedBlockingDeque、LinkedBlockingQueue、LinkedTransferQueue、PriorityBlockingQueue、SynchronousQueue。 阻塞雙端隊列是 BlockingQueue 的子接口。BlockingQueue等BlockingDeque是一個阻塞隊列，但是是雙向的。所以它繼承了Deque接口的屬性。它面向多線程執行，不允許零元素並且容量可能受到限制。如果隊列為空，則 BlockingDeque 接口的實現會阻止獲取元素的操作，如果隊列已滿，則將元素添加到隊列中。

傳輸隊列

TransferQueue 接口擴展了 BlockingQueue 接口。但是，與 BlockingQueue 接口隊列的實現不同，如果隊列為空（讀取）或隊列已滿（寫入），線程可能會被阻塞，TransferQueue 接口隊列會阻塞寫入流，直到另一個流檢索元素。為此使用傳輸方法。也就是說，BlockingQueue的實現保證Producer創建的元素一定在隊列中，而TransferQueue的實現保證Producer元素被Consumer“接收”。TransferQueue 接口的官方 Java 實現只有一個——LinkedTransferQueue。

Java 隊列實現

有很多類實現了 Queue 接口：

• AbstractQueue根據 Queue Java 8 文檔，這個抽像類提供了一些 Queue 操作的基本實現。它不允許空元素。基於Queue經典的offer、poll、peek分別增加了3個方法add、remove、element 。但是，它們會拋出異常，而不是通過返回 false 或 null 來指示失敗。
• ArrayBlockingQueue — 由數組支持的固定大小的 FIFO 阻塞隊列
• ArrayDeque — Deque 接口的可調整大小的數組實現
• ConcurrentLinkedDeque — 基於鏈接節點的無界並發雙端隊列。
• ConcurrentLinkedQueue — 基於鏈接節點的無界線程安全隊列。
• DelayQueue — 由堆支持的基於時間的調度隊列
• LinkedBlockingDeque — Deque 接口的並發實現。
• LinkedBlockingQueue — 由鏈接節點支持的可選邊界 FIFO 阻塞隊列
• LinkedList — List 和 Deque 接口的雙向鍊錶實現。實現所有可選列表操作，並允許所有元素（包括 null）
• LinkedTransferQueue — 基於鏈接節點的無界傳輸隊列
• PriorityBlockingQueue — 由堆支持的無界阻塞優先級隊列
• PriorityQueue——基於堆數據結構的優先級隊列
• SynchronousQueue — 一個阻塞隊列，其中每個插入操作都必須等待另一個線程的相應刪除操作，反之亦然。

最流行的實現是 LinkedList、ArrayBlockingQueue 和 PriorityQueue。讓我們看看它們並做一些例子以便更好地理解。

鍊錶

Java 中的 LinkedList 類實現了 List 和 Deque 接口。所以，它是 List 和 Deque 的組合，一個雙向隊列，支持從兩側添加和刪除元素。在 Java 中，LinkedList 是雙向鍊錶：List 的每個元素都調用 Node 並包含一個對象和對兩個相鄰對象（前一個和下一個）的引用。 您可能會說 LinkedList 在使用內存方面不是很有效。沒錯，但是這種數據結構在插入和刪除操作性能方面可能很有用。然而，它只有在你為它們使用迭代器時才會發生（在這種情況下它發生在恆定時間內）。通過從頭到尾（取較近的）搜索所需元素來執行按索引的訪問操作。但是，不要忘記在元素之間存儲引用的額外成本。因此，LinkedList 是 Java 中最流行的隊列實現。它也是 List 和 Deque 的實現，它允許我們創建一個雙向隊列，該隊列由包括 null 在內的任何對象組成。LinkedList 是元素的集合。

鍊錶構造器

不帶參數的LinkedList()用於構造一個空列表。 LinkedList(Collection<? extends E> c)用於創建包含指定集合的​​元素的列表，它們按順序由集合的迭代器返回。

主要鍊錶方法：

• add(E element) 將指定的元素附加到此列表的末尾；
• add(int index, E element) 在指定位置index處插入元素；
• get(int index) 返回此列表中指定位置的元素；
• remove(int index) 移除索引位置的元素；
• remove(Object o) 從此列表中移除第一個出現的 ?o 元素（如果存在）。
• remove() 檢索並刪除列表的第一個元素。
• addFirst(), addLast() 添加一個元素到列表的開頭/結尾
• clear() 從列表中刪除所有元素
• 如果列表包含 o 元素，則 contains(Object o) 返回 true。
• indexOf(Object o) 返回 o 元素第一次出現的索引，如果不在列表中則返回 -1。
• set(int index, E element) 用元素替換索引位置的元素
• size() 返回列表中元素的數量。
• toArray() 返回一個數組，其中包含列表中從第一個元素到最後一個元素的所有元素。
• pop() 從堆棧中彈出一個元素（由列表表示）
• push(E e) 將元素推入堆棧（由此列表表示）

Java 隊列示例——LinkedList（以不同方式放置和刪除元素）

import java.util.*;
 
public class LinkedListTest {
 
       public static void main(String args[]){
 
           LinkedList<Integer> myLinkedList= new LinkedList<Integer>();
           myLinkedList.add(1);
           myLinkedList.add(2);
           myLinkedList.add(4);
           System.out.println("three added elements: " + myLinkedList);
           //put one element into the head, not to the tail:
           myLinkedList.push(5);
           System.out.println("The new element last in will be the first: " + myLinkedList);
           //add new element at the specified position:
           myLinkedList.add(4,3);
           //put one element into the head, not to the tail (same as push):
           myLinkedList.addFirst(6);
           System.out.println(myLinkedList);
           //now remove element no 2 (it is 1):
           myLinkedList.remove(2);
           System.out.println(myLinkedList);
           //now remove the head of the list
           myLinkedList.pop();
           System.out.println(myLinkedList);
           //remove with the other method
           myLinkedList.remove();
           System.out.println(myLinkedList);
           //and with one more
           myLinkedList.poll();
           System.out.println(myLinkedList);
       }
       }

優先隊列

PriorityQueue不完全是FIFO一般意義上的隊列。優先級隊列的元素根據它們的自然順序進行排序，或者由隊列構造時提供的比較器排序，具體取決於使用的​​構造函數。然而，它不是像列表這樣的線性結構中的順序（從最大到最小，反之亦然）。基於優先級最小堆的優先級隊列。堆是一種基於二叉樹的數據結構. 每個父母的優先權大於其子女的優先權。如果每個父節點不超過兩個子節點，並且級別的填充從上到下（從同一級別 - 從左到右），則一棵樹稱為完全二叉樹。每次向其中添加或刪除新元素時，二叉堆都會自行重組。在最小堆的情況下，無論插入順序如何，最小的元素都會進入根。基於這個最小堆的優先級隊列，所以如果我們有一個整數 PriorityQueue，它的第一個元素將是這些數字中最小的。如果刪除根，則下一個最小的成為根。

主要的 PriorityQueue 方法：

• boolean add(object)將指定的元素插入到優先級隊列中。成功時返回真。如果隊列已滿，該方法將拋出異常。
• boolean offer(object)將指定元素插入此優先級隊列。如果隊列已滿，則該方法返回 false。
• boolean remove(object)從此隊列中移除指定元素的單個實例（如果存在）。
• 對象 poll()檢索並刪除此隊列的頭部。如果隊列為空，則返回 null。
• void clear()從優先級隊列中刪除所有元素。
• Object element()檢索此隊列的頭部而不刪除它。如果隊列為空，則拋出 NoSuchElementException。
• 對象 peek()檢索隊列的頭部而不刪除它。如果隊列為空，則返回 null。
• 如果隊列包含 o 元素，則boolean contains(Object o)返回 true。
• int size()返回此隊列中的元素數。

優先隊列的例子

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

重要的是要了解優先級隊列是基於二叉堆的，因此它們不會使元素保持線性排序。從根到葉的每條路都是有序的，但從根到不同的路則不是。這意味著您可以非常快速地獲取隊列的最小元素。如果你每次都刪除頭部，你將打印一個排序結構。

數組阻塞隊列

ArrayBlockingQueue的內部數據結構是基於一個循環數組來存儲元素的。它是一個典型的隊列（FIFO），以防新元素插入隊列尾部，提取操作從隊列頭部返回一個元素。隊列容量一旦創建就無法更改。嘗試將元素插入（放置）到已滿隊列會導致阻塞流程；試圖從空隊列中取出一個元素也會阻塞線程。正如我們之前所說，這個數組是圓形的。這意味著數組的第一個和最後一個元素在邏輯上是相鄰的。每次將元素放入隊列或從隊列中移除時，隊列都會推進頭元素和尾元素的索引。如果某個索引推進數組的最後一個元素，它會從 0 重新開始。因此，在頭部移除的情況下，隊列不必移動所有元素（就像在通常的數組中一樣）。但是，在從中間移除元素（使用 Iterator.remove）的情況下，元素會移動。 ArrayBlockingQueue支持在構造函數中使用fair參數的附加公平策略，以對生產者（插入元素）和消費者（提取元素）的等待流的工作進行排序。默認情況下，不保證順序。但是，如果隊列是使用“fair == true”創建的，則 ArrayBlockingQueue 類的實現以 FIFO 順序提供線程訪問。股權通常會減少帶寬，但也會降低波動性並防止資源耗盡。

ArrayBlockingQueue 類構造函數

• ArrayBlockingQueue (int capacity)創建一個具有固定容量和默認訪問策略的隊列。
• ArrayBlockingQueue (int capacity, boolean fair)創建一個具有固定容量和指定訪問策略的隊列。
• ArrayBlockingQueue (int capacity, boolean fair, Collection <? extends E> c)創建一個由訪問策略指定的具有固定容量的隊列，並包含隊列中的元素。

這裡我們有 BlockingQueueExample 示例。我們創建一個 ArrayBlockingQueue 隊列，其容量為一個元素和一個公平標誌。啟動了兩個線程。其中第一個是生產者線程，它使用 put 方法對來自消息數組的消息進行排隊。第二個 Consumer 線程使用take方法從隊列中讀取元素並將它們顯示在控制台中。元素的順序是隊列的自然順序。

import java.util.concurrent.*;
 
public class ArrayBlockingQueueExample {
 
   private BlockingQueue<Integer> blockingQueue;
   private final Integer[]  myArray = {1,2,3,4,5};
  
       public ArrayBlockingQueueExample ()
       { blockingQueue = new ArrayBlockingQueue<Integer>(1, true);
           (new Thread(new Producer())).start();
           (new Thread(new Consumer())).start();
       }
 
       class Producer implements Runnable
       {
           public void run() {
               try {
                   int counter = 0;
                   for (int i=0; i < myArray.length; i++) {
                       blockingQueue.put(myArray[i]);
                       if (counter++ < 2)
                           Thread.sleep(3000);
                   } blockingQueue.put(-1);
               }
               catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }
 
       class Consumer implements Runnable
       {
           public void run() {
               try {
                   Integer message = 0;
                   while (!((message = blockingQueue.take()).equals(-1)))
                       System.out.println(message);
               } catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }
 
       public static void main(String[] args) {
           new ArrayBlockingQueueExample();
       }
   }

輸出是自然順序的隊列；前兩個元素出現延遲。 為了鞏固您所學的知識，我們建議您觀看我們的 Java 課程中的視頻課程

結論

• Queue 用於在隊列末尾插入元素並從隊列開頭移除元素。它遵循 FIFO 概念。
• Java Queue 是 Collection Framework 的一部分，實現了 Collection 接口。所以它支持Collection接口的所有方法，如插入、刪除等。
• Queue 最常用的實現是 LinkedList、ArrayBlockingQueue 和 PriorityQueue。
• 優先級隊列的元素根據它們的自然順序進行排序，或者由隊列構造時提供的比較器排序，具體取決於使用的​​構造函數。
• 如果對 BlockingQueues 執行任何 null 操作，則會拋出 NullPointerException。