java队列双队列_Java队列– Java队列-白红宇

java队列双队列_Java队列– Java队列

阅读量：2533 次

发布时间：2019-05-11

本文共 19387 字，大约阅读时间需要 64 分钟。

java队列双队列

Java Queue is an interface available in java.util package and extends java.util.Collection interface.

Just like Java List, Java Queue is a collection of ordered elements (Or objects) but it performs insert and remove operations differently. We can use Queue to store elements before processing those elements.

Java Queue是java.util包中可用的接口，并且扩展了java.util.Collection接口。

就像Java List一样，Java Queue是有序元素（或对象）的集合，但是它执行插入和删除操作的方式有所不同。我们可以使用Queue来存储元素，然后再处理这些元素。

Java队列 (Java Queue)

In this section, we will discuss some of the important points about Java Queue:

在本节中，我们将讨论有关Java Queue的一些重要点：

java.util.Queue interface is a subtype of java.util.Collection interface.
java.util.Queue接口是java.util.Collection接口的子类型。

Just like a real-world queue (for instance, in a bank or at ATM), Queue inserts elements at the end of the queue and removes from the beginning of the queue.
就像现实世界中的队列（例如，在银行或ATM中）一样，队列在队列的末尾插入元素，并从队列的开头删除元素。

Java Queue represents an ordered list of elements.
Java Queue表示元素的有序列表。

Java Queue follows FIFO order to insert and remove it’s elements. FIFO stands for First In First Out.
Java Queue遵循FIFO的顺序来插入和删除其元素。 FIFO代表先进先出。

Java Queue supports all methods of Collection interface.
Java Queue支持Collection接口的所有方法。

Most frequently used Queue implementations are LinkedList, ArrayBlockingQueue and PriorityQueue.
最常用的Queue实现是LinkedList，ArrayBlockingQueue和PriorityQueue。

BlockingQueues do not accept null elements. If we perform any null related operation, it throws NullPointerException.
BlockingQueues不接受空元素。如果执行任何与null相关的操作，则将引发NullPointerException。

BlockingQueues are used to implement Producer/Consumer based applications.
BlockingQueues用于实现基于生产者/消费者的应用程序。

BlockingQueues are thread-safe.
BlockingQueues是线程安全的。

All Queues which are available in java.util package are Unbounded Queues and Queues which are available in java.util.concurrent package are Bounded Queues.
java.util包中可用的所有队列都是“无界队列”，而java.util.concurrent包中可用的所有队列是“有界队列”。

All Deques are not thread-safe.
所有双端队列都不是线程安全的。

ConcurrentLinkedQueue is an unbounded thread-safe Queue based on linked nodes.
ConcurrentLinkedQueue是基于链接节点的无界线程安全队列。

All Queues supports insertion at the tail of the queue and removal at the head of the queue, except Deques.
除双端队列外，所有队列均支持在队列尾部插入和在队列头部除去。

Deques are queues but they support element insertion and removal at both ends.
双端队列是队列，但它们支持两端的元素插入和删除。

Java队列类图 (Java Queue Class Diagram)

Java Queue interface extends Collection interface. Collection interface extends Iterable interface. Some of the frequently used Queue implementation classes are LinkedList, PriorityQueue, ArrayBlockingQueue, DelayQueue, LinkedBlockingQueue, PriorityBlockingQueue etc.. AbstractQueue provides a skeletal implementation of the Queue interface to reduce the effort in implementing Queue.

Java Queue接口扩展了Collection接口。 Collection接口扩展了Iterable接口。一些常用的Queue实现类包括LinkedList，PriorityQueue，ArrayBlockingQueue，DelayQueue，LinkedBlockingQueue，PriorityBlockingQueue等。AbstractQueue提供了Queue接口的骨架实现，以减少实现Queue的工作量。

Java队列方法 (Java Queue Methods)

In this section we will discuss some of the useful and frequently used Java Queue methods:

在本节中，我们将讨论一些有用且经常使用的Java Queue方法：

int size(): to get the number of elements in the Set.
int size（）：获取Set中元素的数量。

boolean isEmpty(): to check if Set is empty or not.
boolean isEmpty（）：检查Set是否为空。

boolean contains(Object o): Returns true if this Set contains the specified element.
boolean contains（Object o）：如果此Set包含指定的元素，则返回true。

Iterator iterator(): Returns an iterator over the elements in this set. The elements are returned in no particular order.
Iterator iterator（）：返回对此集合中的元素进行迭代的迭代器。元素以不特定的顺序返回。

boolean removeAll(Collection c): Removes from this set all of its elements that are contained in the specified collection (optional operation).
boolean removeAll（Collection c）：从此集合中删除所有包含在指定集合中的元素（可选操作）。

boolean retainAll(Collection c): Retains only the elements in this set that are contained in the specified collection (optional operation).
boolean keepAll（Collection c）：仅保留此集合中包含在指定集合中的元素（可选操作）。

void clear(): Removes all the elements from the set.
void clear（）：从集合中删除所有元素。

E remove(): Retrieves and removes the head of this queue.
E remove（）：检索并删除此队列的头。

E poll(): Retrieves and removes the head of this queue, or returns null if this queue is empty.
E poll（）：检索并删除此队列的头部，如果此队列为空，则返回null。

E peek(): Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
E peek（）：检索但不删除此队列的头，如果此队列为空，则返回null。

boolean offer(E e): Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.
boolean offer（E e）：如果可以在不违反容量限制的情况下立即将指定的元素插入此队列。

E element(): Retrieves, but does not remove, the head of this queue.
E element（）：检索但不删除此队列的头。

boolean add(E e): Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
boolean add（E e）：如果可以立即将指定的元素插入此队列，而不会违反容量限制，则在成功时返回true，如果当前没有可用空间，则抛出IllegalStateException。

Object[] toArray(): Returns an array containing all of the elements in this set. If this set makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order.
Object [] toArray（）：返回包含此集合中所有元素的数组。如果此集合保证其迭代器返回其元素的顺序，则此方法必须以相同的顺序返回元素。

Java队列基础 (Java Queue Basics)

As Java Queue extends Java Collection, it also supports all Collection interface operations. Let’s explore some simple operations in the following example:

随着Java Queue扩展Java Collection，它还支持所有Collection接口操作。让我们在以下示例中探索一些简单的操作：

package com.journaldev.queue;import java.util.*;public class QueueExample {   public static void main(String[] args) {			Queue
    
      queue = new LinkedList<>();	queue.add("one");	queue.add("two");	queue.add("three");	queue.add("four");	System.out.println(queue);			queue.remove("three");	System.out.println(queue);	System.out.println("Queue Size: " + queue.size());	System.out.println("Queue Contains element 'two' or not? : " + queue.contains("two"));	// To empty the queue	queue.clear();   }}

Output:-

输出：-

[one, two, three, four][one, two, four]Queue Size: 3Queue Contains element 'two' or not? : true

要排队的Java数组 (Java Array to Queue)

Here we can explore how to convert a Java array to Queue using “Collections.addAll()” method with one simple example.

在这里，我们将通过一个简单的示例探讨如何使用“ Collections.addAll（）”方法将Java数组转换为Queue。

import java.util.*;public class ArrayToQueue {    public static void main(String[] args) {			String nums[] = {"one","two","three","four","five"};	Queue
    
      queue = new LinkedList<>();	Collections.addAll(queue, nums);	System.out.println(queue);   }}

Output:-

When we run above program, We will get the following output:

输出：-

当我们运行上述程序时，我们将获得以下输出：

[one, two, three, four, five]

Java队列到阵列 (Java Queue to Array)

Here we will explore how to convert a Java Queue to a Java Array using “toArray()” with one simple example.

在这里，我们将通过一个简单的示例探讨如何使用“ toArray（）”将Java队列转换为Java Array。

import java.util.*;public class QueueToArray {   public static void main(String[] args) {			Queue
    
      queue = new LinkedList<>();	queue.add("one");	queue.add("two");	queue.add("three");	queue.add("four");	queue.add("five");			String strArray[] = queue.toArray(new String[queue.size()]);	System.out.println(Arrays.toString(strArray));    }}

Output:-

When we run above program, We will get the following output:

输出：-

当我们运行上述程序时，我们将获得以下输出：

[one, two, three, four, five]

Java队列常见操作 (Java Queue Common Operations)

Java Queue supports all operations supported by Collection interface and some more operations. It supports almost all operations in two forms.

Java Queue支持Collection接口支持的所有操作以及更多其他操作。它支持两种形式的几乎所有操作。

One set of operations throws an exception if the operation fails.
如果操作失败，则一组操作将引发异常。

The other set of operations returns a special value if the operation fails.
如果操作失败，则另一组操作将返回一个特殊值。

The following table explains all Queue common operations briefly.

下表简要说明了所有“队列”常用操作。

Operation	Throws exception	Special value
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

操作方式	引发异常	特殊价值
插	加（e）	报价
去掉	去掉（）	轮询（）
检查	元件（）	窥视（）

We will pickup each operation and discuss them in-detail with some useful examples in the coming sections.

我们将进行每个操作，并在接下来的部分中详细介绍一些有用的示例。

Java队列插入操作 (Java Queue Insert Operations)

In this section, we will discuss about Java Queue Insert operation in-detail with some useful examples. If this operation performs successfully, it returns “true” value. As we know, Queue supports insert operation in two forms:

在本节中，我们将通过一些有用的示例详细讨论Java队列插入操作。如果此操作成功执行，则返回“ true”值。众所周知，Queue支持两种形式的插入操作：

Queue.add(e):
Queue.add（e）：

It throws an exception if the operation fails.

如果操作失败，它将引发异常。

Queue.offer(e):
Queue.offer（e）：

It returns a special value if the operation fails.

如果操作失败，它将返回一个特殊值。

NOTE:- Here special value may be either “false” or “null”

注意：-这里的特殊值可以是“ false”或“ null”

队列add（）操作 (Queue add() operation)

The add() operation is used to insert new element into the queue. If it performs insert operation successfully, it returns “true” value. Otherwise it throws java.lang.IllegalStateException.

add（）操作用于将新元素插入队列。如果成功执行插入操作，则返回“ true”值。否则，它将引发java.lang.IllegalStateException。

Let us develop one simple example to demonstrate this functionality.

让我们开发一个简单的示例来演示此功能。

import java.util.concurrent.*;public class QueueAddOperation {   public static void main(String[] args) {			BlockingQueue
    
      queue = new ArrayBlockingQueue<>(2);	System.out.println(queue.add("one"));	System.out.println(queue.add("two"));	System.out.println(queue);	System.out.println(queue.add("three"));	System.out.println(queue);   }}

Output:-

When we run above program, We will get the following output:

输出：-

当我们运行上述程序时，我们将获得以下输出：

truetrue[one, two]Exception in thread "main" java.lang.IllegalStateException: Queue full

As our queue is limited to two elements, when we try to add third element using BlockingQueue.add(), it throws an exception as shown above.

由于我们的队列仅限于两个元素，因此当我们尝试使用BlockingQueue.add（）添加第三个元素时，它将引发异常，如上所示。

队列offer（）操作 (Queue offer() operation)

The offer() operation is used to insert new element into the queue. If it performs insert operation successfully, it returns “true” value. Otherwise it returns “false” value.

offer（）操作用于将新元素插入队列。如果成功执行插入操作，则返回“ true”值。否则返回“假”值。

Let us develop one simple example to demonstrate this functionality.

让我们开发一个简单的示例来演示此功能。

import java.util.concurrent.*;public class QueueOfferOperation {   public static void main(String[] args) {			BlockingQueue
    
      queue = new ArrayBlockingQueue<>(2);	System.out.println(queue.offer("one"));	System.out.println(queue.offer("two"));	System.out.println(queue);	System.out.println(queue.offer("three"));	System.out.println(queue);   }}

Output:-

When we run above program, We will get the following output:

输出：-

当我们运行上述程序时，我们将获得以下输出：

truetrue[one, two]false[one, two]

As our queue is limited to two elements, when we try to add third element using BlockingQueue.offer() operation, it returns “false” value as shown above.

由于我们的队列仅限于两个元素，因此当我们尝试使用BlockingQueue.offer（）操作添加第三个元素时，它将返回“ false”值，如上所示。

Java队列删除操作 (Java Queue Delete Operations)

In this section, we will discuss about Java Queue Delete operation in-detail with some useful examples. The Delete operations returns the head element of the queue, if it performs successfully. As we know, Queue supports delete operation in two forms:

在本节中，我们将详细讨论Java Queue Delete操作，并提供一些有用的示例。如果删除操作成功执行，则它返回队列的head元素。众所周知，Queue支持两种形式的删除操作：

Queue.remove():
Queue.remove（）：

It throws an exception if the operation fails.

如果操作失败，它将引发异常。

Queue.poll():
Queue.poll（）：

It returns a special value if the operation fails.

如果操作失败，它将返回一个特殊值。

NOTE:- Here special value may be either “false” or “null”

注意：-这里的特殊值可以是“ false”或“ null”

队列remove（）操作 (Queue remove() operation)

The remove() operation is used to delete an element from the head of the queue. If it performs delete operation successfully, it returns the head element of the queue. Otherwise it throws java.util.NoSuchElementException.

remove（）操作用于从队列的开头删除元素。如果成功执行删除操作，则返回队列的头元素。否则，它将引发java.util.NoSuchElementException。

Let us develop one simple example to demonstrate this functionality.

让我们开发一个简单的示例来演示此功能。

import java.util.*;public class QueueRemoveOperation {   public static void main(String[] args)    {			Queue
    
      queue = new LinkedList<>();	queue.offer("one");	queue.offer("two");			System.out.println(queue);			System.out.println(queue.remove());	System.out.println(queue.remove());			System.out.println(queue.remove());		   }}

Output:-

When we run above program, We will get the following output:

输出：-

当我们运行上述程序时，我们将获得以下输出：

[one, two]onetwoException in thread "main" java.util.NoSuchElementException

As our queue has only two elements, when we try to call remove() method for third time, it throws an exception as shown above.

由于我们的队列只有两个元素，因此当我们尝试第三次调用remove（）方法时，它将引发一个异常，如上所示。

NOTE:-

Queue.remove(element) is used to delete a specified element from the queue. If it performs delete operation successfully, it returns “true” value. Otherwise it returns “false” value.

注意：-

Queue.remove（element）用于从队列中删除指定的元素。如果成功执行删除操作，则返回“ true”值。否则返回“假”值。

队列poll（）操作 (Queue poll() operation)

The poll() operation is used to delete an element from the head of the queue. If it performs delete operation successfully, it returns the head element of the queue. Otherwise it returns “null” value.

poll（）操作用于从队列的开头删除元素。如果成功执行删除操作，则返回队列的头元素。否则返回“空”值。

Let us develop one simple example to demonstrate this functionality.

让我们开发一个简单的示例来演示此功能。

import java.util.*;public class QueuePollOperation {   public static void main(String[] args)    {			Queue
    
      queue = new LinkedList<>();	queue.offer("one");	queue.offer("two");			System.out.println(queue);			System.out.println(queue.poll());	System.out.println(queue.poll());			System.out.println(queue.poll());		   }}

Output:-

When we run above program, We will get the following output:

输出：-

当我们运行上述程序时，我们将获得以下输出：

[one, two]onetwonull

As our queue has only two elements, when we try to call poll() method for third time, it returns null value as shown above.

由于队列只有两个元素，因此当我们尝试第三次调用poll（）方法时，它将返回空值，如上所示。

Java队列检查操作 (Java Queue Examine Operations)

In this section, we will discuss about Java Queue Examine operations in-detail with some useful examples. If this operation performs successfully, it returns the head element of the queue without removing it. As we know, Queue supports examine operation in two forms:

在本节中，我们将通过一些有用的示例详细讨论Java队列检查操作。如果此操作成功执行，它将返回队列的head元素而不将其删除。众所周知，Queue支持两种形式的检查操作：

Queue.element():
Queue.element（）：

It throws an exception if the operation fails.

如果操作失败，它将引发异常。

Queue.peek():
Queue.peek（）：

It returns a special value if the operation fails.

如果操作失败，它将返回一个特殊值。

NOTE:- Here special value may be either “false” or “null”

注意：-这里的特殊值可以是“ false”或“ null”

队列element（）操作 (Queue element() operation)

The element() operation is used to retrieve an element from the head of the queue, without removing it. If it performs examine operation successfully, it returns the head element of the queue. Otherwise it throws java.util.NoSuchElementException.

element（）操作用于从队列的开头检索元素，而不将其删除。如果成功执行检查操作，则返回队列的head元素。否则，它将引发java.util.NoSuchElementException。

Let us develop one simple example to demonstrate this functionality.

让我们开发一个简单的示例来演示此功能。

import java.util.*;public class QueueElementOperation {   public static void main(String[] args) {			Queue
    
      queue = new LinkedList<>();	queue.add("one");			System.out.println(queue.element());	System.out.println(queue);	queue.clear();	System.out.println(queue.element());   }}

Output:-

When we run above program, We will get the following output:

输出：-

当我们运行上述程序时，我们将获得以下输出：

one[one]Exception in thread "main" java.util.NoSuchElementException

If we try to call element() method on empty Queue, it throws an exception as shown above.

如果我们尝试在空Queue上调用element（）方法，则会引发如上所示的异常。

队列peek（）操作 (Queue peek() operation)

The peek() operation is used to retrieve an element from the head of the queue, without removing it. If it performs examine operation successfully, it returns the head element of the queue. Otherwise it returns null value.

peek（）操作用于从队列的开头检索元素，而不删除它。如果成功执行检查操作，则返回队列的head元素。否则返回空值。

Let us develop one simple example to demonstrate this functionality.

让我们开发一个简单的示例来演示此功能。

import java.util.*;public class QueuePeekOperation {   public static void main(String[] args) {			Queue
    
      queue = new LinkedList<>();	queue.add("one");			System.out.println(queue.peek());	System.out.println(queue);	queue.clear();	System.out.println(queue.peek());   }}

Output:-

When we run above program, We will get the following output:

输出：-

当我们运行上述程序时，我们将获得以下输出：

one[one]null

If we try to call peek() method on empty Queue, it returns null value, but does NOT throw an exception as shown above.

如果我们尝试在空Queue上调用peek（）方法，它将返回空值，但不会引发如上所示的异常。

Java队列类别 (Java Queue Categories)

In Java, we can find many Queue implementations. W can broadly categorize them into the following two types

在Java中，我们可以找到许多Queue实现。 W可以将它们大致分为以下两种类型

Bounded Queues
有界队列

Unbounded Queues
无限队列

Bounded Queues are queues which are bounded by capacity that means we need to provide the max size of the queue at the time of creation. For example ArrayBlockingQueue (see previous example).

有界队列是受容量限制的队列，这意味着我们需要在创建时提供队列的最大大小。例如ArrayBlockingQueue（请参见前面的示例）。

Unbounded Queues are queues which are NOT bounded by capacity that means we should not provide the size of the queue. For example LinkedList (see previous example).

无限制队列是不受容量限制的队列，这意味着我们不应该提供队列的大小。例如LinkedList（请参阅前面的示例）。

All Queues which are available in java.util package are Unbounded Queues and Queues which are available in java.util.concurrent package are Bounded Queues.

java.util包中可用的所有队列都是“无界队列”，而java.util.concurrent包中可用的所有队列是“有界队列”。

In other ways, W can broadly categorize them into the following two types:

通过其他方式，W可以将它们大致分为以下两种类型：

Blocking Queues
阻塞队列

Non-Blocking Queues
非阻塞队列

All Queues which implement BlockingQueue interface are BlockingQueues and rest are Non-Blocking Queues.

实现BlockingQueue接口的所有队列都是BlockingQueue，其余的都是Non-Blocking队列。

BlockingQueues blocks until it finishes it’s job or time out, but Non-BlockingQueues do not.

BlockingQueues阻塞直到完成工作或超时，但Non-BlockingQueues不会阻塞。

Some Queues are Deques and some queues are PriorityQueues.

有些队列是双端队列，有些队列是PriorityQueue。

BlockingQueue操作 (BlockingQueue Operations)

In addition to Queue’s two forms of operations, BlockingQueue’s supports two more forms as shown below.

除Queue的两种操作形式外，BlockingQueue的支持以下两种其他形式的操作。

Operation	Throws exception	Special value	Blocks	Times out
Insert	add(e)	offer(e)	put(e)	offer(e, time, unit)
Remove	remove()	poll()	take()	poll(time, unit)
Examine	element()	peek()	N/A	N/A

操作方式	引发异常	特殊价值	积木	超时
插	加（e）	报价	放	报价（e，时间，单位）
去掉	去掉（）	轮询（）	采取（）	民意测验（时间，单位）
检查	元件（）	窥视（）	不适用	不适用