36 What Are the Common Types of Blocking Queues #

In this lesson, we will mainly discuss the common types of blocking queues.

The implementation classes of the BlockingQueue interface are all placed in the J.U.C package. In this lesson, we will introduce common and commonly used implementation classes, including ArrayBlockingQueue, LinkedBlockingQueue, SynchronousQueue, PriorityBlockingQueue, and DelayQueue.

ArrayBlockingQueue #

Let’s start with the most basic ArrayBlockingQueue. ArrayBlockingQueue is the most typical bounded queue which internally uses an array to store elements and achieves thread safety using ReentrantLock.

When we create it, we need to specify its capacity, and it cannot be expanded afterwards. We can also specify whether it is fair in the constructor. The code is as follows:

ArrayBlockingQueue(int capacity, boolean fair)

The first parameter is the capacity, and the second parameter is whether it is fair. Just like ReentrantLock, if the ArrayBlockingQueue is set to be unfair, there is a possibility of “cutting in line”; if it is set to be fair, the thread that has been waiting for the longest time will be processed first, and other threads are not allowed to cut in line. However, this fair strategy also brings some performance loss because the throughput of unfairness is usually higher than that of fairness.

LinkedBlockingQueue #

As the name suggests, this is a blocking queue implemented internally using a linked list. If we do not specify its initial capacity, its capacity defaults to the maximum value of an integer, Integer.MAX_VALUE. Since this number is very large, it is usually not possible to put in so many data, so LinkedBlockingQueue is also called an unbounded queue, which means it has almost no limits.

SynchronousQueue #

As shown in the figure, the biggest difference of the SynchronousQueue is that its capacity is 0. Therefore, there is no place to temporarily store elements, which means that each time data is taken, it will block until there is data to be put; similarly, each time data is put, it will block until there is a consumer to take it.

It should be noted that the capacity of SynchronousQueue is not 1 but 0, because SynchronousQueue does not need to hold elements. What it does is direct handoff. Whenever it needs to hand off, SynchronousQueue will pass the element directly from the producer to the consumer. During this process, there is no need to do storage. Therefore, if used properly, its efficiency is very high.

In addition, because its capacity is 0, compared with a general blocking queue, the implementations of many methods in SynchronousQueue are interesting. Let’s take a few examples:

The peek method of SynchronousQueue always returns null. The code is as follows:

public E peek() {
    return null;
}

Because the meaning of the peek method is to take out the head node, but since the capacity of SynchronousQueue is 0, there is no head node, so the peek method has no meaning and always returns null. Similarly, the element method always throws NoSuchElementException.

The size method of SynchronousQueue always returns 0 because it has no capacity internally. The code is as follows:

public int size() {
    return 0;
}

It directly returns 0. Similarly, the isEmpty method always returns true:

public boolean isEmpty() {
    return true;
}

Because it is always empty.

PriorityBlockingQueue #

The ArrayBlockingQueue and LinkedBlockingQueue we mentioned earlier both use the first-in-first-out order for sorting. However, what if we need custom sorting? This is when we need to use PriorityBlockingQueue.

PriorityBlockingQueue is an unbounded blocking queue that supports priority. We can specify the sorting rule of elements by implementing the compareTo() method in a custom class or by specifying the sorting rule through the constructor parameter Comparator during initialization. At the same time, the objects inserted into the queue must be comparable, that is, Comparable, otherwise a ClassCastException will be thrown.

Its take method will block when the queue is empty, but because it is an unbounded queue and will automatically expand, its queue will never be full. Therefore, its put method will never block, and the add operation will always succeed. Because of this, it only has one member variable:

private final Condition notEmpty;

This is in sharp contrast to the ArrayBlockingQueue mentioned earlier, which has two conditions (notEmpty and notFull). Our PriorityBlockingQueue does not need notFull because it will never be full. It is really “arbitrary if there is space”.

DelayQueue #

DelayQueue is a special queue with a “delay” capability. We can set a delay for the tasks in the queue, for example, execute after 10 seconds. This is widely used in scenarios such as “automatically cancel the order if it is not paid within 30 minutes” that require delayed execution.

It is an unbounded queue, and the elements placed in it must implement the Delayed interface, and the Delayed interface inherits the Comparable interface. Therefore, it naturally has the ability to compare and sort. The code is as follows:

public interface Delayed extends Comparable<Delayed> {
    long getDelay(TimeUnit unit);
}

As we can see, this Delayed interface inherits from Comparable, and there is a method that needs to be implemented, which is getDelay. The getDelay method returns “how long is the remaining delay time before it will be executed”. If it returns 0 or a negative number, it means that the task has expired.

Elements will be placed in different positions in the queue based on the length of the delay time, with those closer to the head of the queue expiring earlier.

DelayQueue internally uses PriorityQueue’s ability to perform sorting instead of rewriting it from scratch. We can learn from this approach in our work by reusing existing functionality, which not only reduces development effort but also avoids “reinventing the wheel”. More importantly, by applying the knowledge we have learned reasonably, we can make it more flexible and see connections with other things.

Summary #

The above is the content of this lesson, where we explain the characteristics of ArrayBlockingQueue, LinkedBlockingQueue, SynchronousQueue, PriorityBlockingQueue, and DelayQueue, which are common and commonly used blocking queues.