Java隊(duì)列

隊(duì)列是只能在其上執(zhí)行操作的對象的集合兩端的隊(duì)列。

隊(duì)列有兩個末端，稱為頭和尾。

在簡單隊(duì)列中，對象被添加到尾部并從頭部刪除并首先刪除首先添加的對象。

Java Collections Framework支持以下類型的隊(duì)列。

• 簡單的隊(duì)列允許在尾部插入和從頭部移除。

• 優(yōu)先級隊(duì)列為每個元素分配優(yōu)先級，并允許從隊(duì)列中刪除具有最高優(yōu)先級的元素。

• 延遲隊(duì)列向每個元素添加延遲，并僅在其延遲已過去時刪除該元素。

• 雙端隊(duì)列允許其元件從頭部和尾部插入和移除。

• 阻塞隊(duì)列阻塞線程，當(dāng)線程已滿時向其添加元素，當(dāng)線程為空時，它阻止線程從中刪除元素。

• 傳輸隊(duì)列是阻塞隊(duì)列，其中對象的切換發(fā)生在生產(chǎn)者線程和消費(fèi)者線程之間。

• 阻塞雙端隊(duì)列是雙端隊(duì)列和阻塞隊(duì)列的組合。

隊(duì)列的簡介

• 隊(duì)列可以定義為有序列表，它允許在一端執(zhí)行插入操作，稱為REAR，刪除操作在另一端執(zhí)行，稱為FRONT。

• 隊(duì)列被稱為先進(jìn)先出列表。

• 例如，排隊(duì)等候鐵路車票的人隊(duì)列。

隊(duì)列的應(yīng)用

由于隊(duì)列以先進(jìn)先出的方式執(zhí)行操作，這對于操作的排序是相當(dāng)公平的。 隊(duì)列的各種應(yīng)用如下所述。

• 隊(duì)列被廣泛用作單個共享資源(如打印機(jī)，磁盤，CPU)的等待列表。

• 隊(duì)列用于異步數(shù)據(jù)傳輸(例如，數(shù)據(jù)不以兩個進(jìn)程之間的相同速率傳輸)。 管道，文件IO，套接字。

• 隊(duì)列在大多數(shù)應(yīng)用程序中用作緩沖區(qū)，如MP3媒體播放器，CD播放器等。

• 隊(duì)列用于維護(hù)媒體播放器中的播放列表，以便添加和刪除播放列表中的歌曲。

• 隊(duì)列在操作系統(tǒng)中用于處理中斷。

時間復(fù)雜性

時間復(fù)雜性	訪問	搜索	插入	刪除
平均情況	θ(n)	θ(n)	θ(1)	θ(1)
最壞情況	θ(n)	θ(n)	θ(1)	θ(1)

簡單隊(duì)列

簡單隊(duì)列由 Queue 接口的實(shí)例表示。

隊(duì)列允許您執(zhí)行三個基本操作:

• 從尾部添加元素

• 從其頭部移除元素

• 在元素頂部審查

Queue接口為三個操作中的每一個定義了兩個方法。如果操作不可能，一個方法拋出異常，另一個方法方法返回false或null以指示失敗。

方法	描述
boolean add(E e)	如果可能，向隊(duì)列中添加一個元素。否則，它拋出異常。
boolean offer(E e)	如果不能添加元素，則將元素添加到隊(duì)列中，而不拋出異常。 它在失敗時返回false，在成功時返回true。
E remove()	刪除隊(duì)列的頭。如果隊(duì)列為空，它會拋出異常。此方法返回已移除的項(xiàng)目。
E poll()	從隊(duì)列中刪除元素。如果隊(duì)列為空而不是拋出異常，則返回null。
Eelement()	偷看隊(duì)列的頭，而不從隊(duì)列中刪除它。 如果隊(duì)列為空，它會拋出異常。
E peek()	查看隊(duì)列，如果隊(duì)列為空而不是拋出異常，則返回null。

LinkedList和PriorityQueue是Queue接口的兩個實(shí)現(xiàn)類。LinkedList還實(shí)現(xiàn)了List接口。

例子

以下代碼顯示如何將鏈表用作FIFO隊(duì)列。

import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;

public class Main {
  public static void main(String[] args) {
    Queue<String> queue = new LinkedList<>();
    queue.add("Java");
    // offer() will work the same as add()
    queue.offer("SQL");
    queue.offer("CSS");
    queue.offer("XML");

    System.out.println("Queue: " + queue);

    // Let"s remove elements until the queue is empty
    while (queue.peek() != null) {
      System.out.println("Head  Element: " + queue.peek());
      queue.remove();
      System.out.println("Removed one  element from  Queue");
      System.out.println("Queue: " + queue);
    }
    System.out.println("queue.isEmpty(): " + queue.isEmpty());
    System.out.println("queue.peek(): " + queue.peek());
    System.out.println("queue.poll(): " + queue.poll());
    try {
      String str = queue.element();
      System.out.println("queue.element(): " + str);
      str = queue.remove();
      System.out.println("queue.remove(): " + str);
    } catch (NoSuchElementException e) {
      System.out.println("queue.remove(): Queue is  empty.");
    }
  }
}

上面的代碼生成以下結(jié)果。