Category: Algorithms and Data Structures

In the last part of the tutorial series, we implemented a queue using an array. In this final part of the series, I will show you how to implement a priority queue using a heap.

As a reminder: In a priority queue, the elements are not retrieved in FIFO order but according to their priority. The highest priority element is always at the head of the queue and is taken first – regardless of when it was inserted into the queue.

What Is a Heap?

A “heap” is a binary tree in which each node is either greater than or equal to its children (“max heap”) – or less than or equal to its children (“min-heap”).

For the priority queue in this article, we use a min heap because the highest priority is the one with the lowest number (priority 1 is usually higher than priority 2).

Here is an example of what such a min-heap might look like:

The element at each node of this tree is less than the elements of its two child nodes:

• 1 is less than 2 and 4;
• 2 is less than 3 and 7;
• 4 is less than 9 and 6;
• 3 is less than 8 and 5.

Array Representation of a Heap

We can store a heap in an array by mapping its elements row by row – from top left to bottom right – to the array:

Our example heap looks like this as an array:

In a min-heap, the smallest element is always at the top, i.e., in the array, it is always at the first position. This is why, when you print a Java PriorityQueue as a string, you see the smallest element on the left. What you see is the array representation of the min-heap underlying the PriorityQueue.

The following lines of code demonstrate this well:

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.addAll(List.of(4, 7, 3, 8, 2, 9, 6, 5, 1));
System.out.println("priorityQueue = " + priorityQueue);Code language: Java (java)

The output of the program is:

priorityQueue = [1, 2, 4, 3, 7, 9, 6, 8, 5]Code language: plaintext (plaintext)

The smallest element is on the far left. And if you look closely, you’ll see that the numbers are in the same order as in the graphical array representation above. The min-heap of the PriorityQueue created in the example is precisely the one I displayed at the beginning of the article.

Priority Queue Using a Min-Heap – The Algorithm

OK, the smallest element is always on the left. That tells how the peek() operation has to work: it simply has to return the first element of the array.

But how is such a heap constructed? How do enqueue() and dequeue() work?

Inserting into the Min-Heap: Sift Up

To insert an element into a heap, we proceed as follows:

1. We insert the new element as the last element in the tree, i.e.:
   • If the tree is empty, we insert the new element as the root.
   • If the lowest level of the tree is not complete, we insert the new element next to the last node of the lowest level.
   • If the lowest level is complete, we append the node under the first node of the lowest level.
2. As long as the parent node of the new element is less than the element itself (which would violate the min-heap rule), we swap the new node with its parent node.

Step 1 sounds complicated, but in the array representation, it simply means that the new element is placed in the first free position of the array. Step 2 ensures that, at the end of the operation, each element is again less than its children.

The example in the following section demonstrates the two steps.

Inserting into the Min-Heap: Example

In the following examples, I will show you step by step how to fill a min-heap-based priority queue with the sample values shown above (4, 7, 3, 8, 2, 9, 6, 5, 1). I’ll show the min-heap in its tree and array representations in each step.

1^st Element – Inserting the 4 into an Empty Priority Queue

The first element to be inserted becomes the root node of the tree; in the array, we place it at the first position:

2^nd Element – Inserting the 7

We append the 7 below the first node of the lowest level – that is, below the root on the left. In the array, we simply append it:

The 7 is greater than its parent node 4 – thus, the insertion operation is complete. The smallest element is still at the beginning of the priority queue.

3^rd Element – Inserting the 3

We append the 3 next to the last node of the lowest level, that is, as right child of the 4. In the array, it comes at the end:

The 3 is less than its parent node. The min-heap rules are, therefore, violated. We restore the min-heap by swapping the 3 with the 4:

We now have a valid min-heap again.

We skip 8, 2, 9, 6, and 5 (these are inserted analogously) and come to the…

9^th Element – Inserting the 1

Finally, we add the 1 to the end of the queue (and the array):

The 1 is greater than its parent node 5; thus, our tree is no longer a valid min-heap. To fix it, we first swap the 1 with the 5:

The 1 is also greater than its new parent node 3; thus, we swap again:

The 1 is also greater than the root 2, so we swap a third time:

Since the 1 has now reached the root, the operation is finished. The tree is again a min-heap. The smallest element is at the tree’s root (and at the beginning of the array).

This reaching up of the inserted element in the way just shown is called “sift up”.

Simplified Sift Up Algorithm

In fact, we don’t even need to bother inserting the new element at the end, then swapping it with its parent node step by step. Instead, we can remember the new element, move the greater parent elements down, and finally place the new element directly at its target position.

The following graphics show the insertion of the 1 according to the simplified algorithm.

The 1 is less than the empty node’s parent, the 5. We, therefore, move the 5 to the free node:

The 1 is also less than the 3; we move the 3 down:

The 1 is less than the 2; we also push the 2 down:

We can’t move any more elements down, so we put the element to be inserted, the 1, on the now-vacated root node (or the first field in the array):

This completes the sift up operation.

Inserting an element into the priority queue (or min-heap) may seem very complex the first time you read through it. If you don’t understand it, take a break and repeat the chapter before proceeding to the dequeue operation.

Removing from the Min-Heap: Sift Down

We know that the smallest element is always at the tree’s root (or at the beginning of the array).

To remove it, we proceed as follows:

1. We remove the root element from the tree.
2. We move the last node of the lowest level of the tree (which corresponds to the last field of the array) to the vacated root position.
3. As long as this node is greater than one of its children (which would violate the min-heap rule), we swap the node with its smallest child node.

Removing from the Min-Heap: Example

The following example shows how we remove the root element of the min-heap filled in the last chapter – and then restore the min-heap condition.

The first thing we do is take out the root element:

Second, we move the tree’s last element, the 5, to the now-vacated root node:

Since the new root element, 5, is greater than the smallest of its children, 2, we swap those two elements:

The 5 is still greater than the smallest of its children, the 3. We swap a second time:

The 5 is now greater than its only child; we have thus restored the min-heap condition.

The root of the min-heap (the first field of the array) now contains the 2, the new smallest element after removing the 1.

The reaching down of the element moved to the root is called “sift down”.

Simplified Sift Down Algorithm

We can also simplify the sift down algorithm. We don’t have to move the last element (the 5 in the example) to the root first and then gradually swap it with its children. We can instead move the greater elements up first and, in the end, move the last element directly to its final position.

The following illustrations show the passing down of the 5 (or rather: the free field on which the 5 is placed in the end) according to the simplified algorithm.

The 5 is greater than the smallest child node of the empty root, the 2. We move the 2 up:

The 5 is also greater than the smallest child of the now-vacant node, the 3. We also move the 3 up:

The 5 is not greater than the only child of the now-vacant node, the 8. So we have found the target node for the 5, and we push the 5 there:

We have restored the min-heap condition.

The sift up and sift down operations may seem complex, but we can implement them both in 10 lines of Java code or less. You’ll learn how in the next chapter.

Source Code for Priority Queue with Min-Heap

The following source code shows how to implement a priority queue with a min-heap (class HeapPriorityQueue in the GitHub repository). Due to the length of the class, I am going to divide it into sections.

Constructors

There are two constructors: one where you can specify the initial size of the array and a default constructor that sets the initial capacity to ten:

public class HeapPriorityQueue<E extends Comparable<? super E>> implements Queue<E> {

  private static final int DEFAULT_INITIAL_CAPACITY = 10;
  private static final int ROOT_INDEX = 0;

  private Object[] elements;
  private int numberOfElements;

  public HeapPriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY);
  }

  public HeapPriorityQueue(int capacity) {
    if (capacity < 1) {
      throw new IllegalArgumentException("Capacity must be 1 or higher");
    }

    elements = new Object[capacity];
  }
Code language: Java (java)

enqueue()

The enqueue() method first checks if the queue is full. If it is, it calls the grow() method, which copies the array into a new, larger array:

  @Override
  public void enqueue(E newElement) {
    if (numberOfElements == elements.length) {
      grow();
    }
    siftUp(newElement);
    numberOfElements++;
  }

  private void grow() {
    int newCapacity = elements.length + elements.length / 2;
    elements = Arrays.copyOf(elements, newCapacity);
  }Code language: Java (java)

I have depicted the grow() method in a very simplified way here since the focus should be on the siftUp() and siftDown() methods.

In the HeapPriorityQueue class in the GitHub repository, the grow() method increases the array by factor 2 up to a specific size (64 elements) and, after that, by factor 1.5. It also ensures that we don’t exceed a certain maximum size.

When we are sure that the array is large enough, we call the siftUp() method:

siftUp()

  private void siftUp(E newElement) {
    int insertIndex = numberOfElements;

    while (isNotRoot(insertIndex) && isParentGreater(insertIndex, newElement)) {
      copyParentDownTo(insertIndex);
      insertIndex = parentOf(insertIndex);
    }

    elements[insertIndex] = newElement;
  }

  private boolean isNotRoot(int index) {
    return index != ROOT_INDEX;
  }

  private boolean isParentGreater(int insertIndex, E element) {
    int parentIndex = parentOf(insertIndex);
    E parent = elementAt(parentIndex);
    return parent.compareTo(element) > 0;
  }

  private void copyParentDownTo(int insertIndex) {
    int parentIndex = parentOf(insertIndex);
    elements[insertIndex] = elements[parentIndex];
  }

  private int parentOf(int index) {
    return (index - 1) / 2;
  }
Code language: Java (java)

Note that I tried to implement the algorithm as readable as possible (and not as performant as possible). The parentOf() method is called three times in each iteration: once by isParentGreater(), once by copyParentDownTo() and once directly.

An optimized variant (OptimizedHeapPriorityQueue class in the GitHub repo, starting at line 74) shows a tweaked algorithm that calculates the parent index only once.

dequeue()

The dequeue() method retrieves the header element, removes the last element, and then calls siftDown(), which ultimately moves this last element to its new position.

  @Override
  public E dequeue() {
    E result = elementAtHead();
    E lastElement = removeLastElement();
    siftDown(lastElement);
    return result;
  }

  private E removeLastElement() {
    numberOfElements--;
    E lastElement = elementAt(numberOfElements);
    elements[numberOfElements] = null;
    return lastElement;
  }
Code language: Java (java)

siftDown()

siftDown() is the most complex method because it always has to compare a node with possibly two child nodes.

  private void siftDown(E lastElement) {
    int lastElementInsertIndex = ROOT_INDEX;
    while (isGreaterThanAnyChild(lastElement, lastElementInsertIndex)) {
      moveSmallestChildUpTo(lastElementInsertIndex);
      lastElementInsertIndex = smallestChildOf(lastElementInsertIndex);
    }

    elements[lastElementInsertIndex] = lastElement;
  }

  private boolean isGreaterThanAnyChild(E element, int parentIndex) {
    E leftChild = leftChildOf(parentIndex);
    E rightChild = rightChildOf(parentIndex);

    return leftChild != null && element.compareTo(leftChild) > 0
        || rightChild != null && element.compareTo(rightChild) > 0;
  }

  private E leftChildOf(int parentIndex) {
    int leftChildIndex = leftChildIndexOf(parentIndex);
    return exists(leftChildIndex) ? elementAt(leftChildIndex) : null;
  }

  private int leftChildIndexOf(int parentIndex) {
    return 2 * parentIndex + 1;
  }

  private E rightChildOf(int parentIndex) {
    int rightChildIndex = rightChildIndexOf(parentIndex);
    return exists(rightChildIndex) ? elementAt(rightChildIndex) : null;
  }

  private int rightChildIndexOf(int parentIndex) {
    return 2 * parentIndex + 2;
  }

  private boolean exists(int index) {
    return index < numberOfElements;
  }

  private void moveSmallestChildUpTo(int parentIndex) {
    int smallestChildIndex = smallestChildOf(parentIndex);
    elements[parentIndex] = elements[smallestChildIndex];
  }

  private int smallestChildOf(int parentIndex) {
    int leftChildIndex = leftChildIndexOf(parentIndex);
    int rightChildIndex = rightChildIndexOf(parentIndex);

    if (!exists(rightChildIndex)) {
      return leftChildIndex;
    }

    return smallerOf(leftChildIndex, rightChildIndex);
  }

  private int smallerOf(int leftChildIndex, int rightChildIndex) {
    E leftChild = elementAt(leftChildIndex);
    E rightChild = elementAt(rightChildIndex);
    return leftChild.compareTo(rightChild) < 0 ? leftChildIndex : rightChildIndex;
  }
Code language: Java (java)

Just like siftUp(), I wrote siftDown() with focus on readability, not on performance. Thus the positions of the child elements are calculated three times per iteration: in isGreaterThanAnyChild(), in moveSmallestChildUpTo() and again in smallestChildOf().

In the optimized class OptimizedHeapPriorityQueue, these positions are calculated only once. However, this also makes the code less easy to read.

peek(), isEmpty(), and Two Helper Methods

And finally, here are the peek() and isEmpty() methods and two helper methods used to read the element from the head of the queue or a specific position.

Since we store the elements in an Object array, we must cast the array elements to E. In order not to distribute the casts all over the source code, I have moved the casting to a central location, the method elementAt(), and suppressed the “unchecked” warning there once.

  @Override
  public E peek() {
    return elementAtHead();
  }

  private E elementAtHead() {
    E element = elementAt(0);
    if (element == null) {
      throw new NoSuchElementException();
    }
    return element;
  }

  private E elementAt(int child) {
    @SuppressWarnings("unchecked")
    E element = (E) elements[child];
    return element;
  }

  @Override
  public boolean isEmpty() {
    return numberOfElements == 0;
  }
}Code language: Java (java)

If your head isn’t spinning yet, feel free to look at the source code of the JDK’s PriorityQueue class. It can sort elements not only by their natural order – but also by a comparator passed to the constructor.

Conclusion

This concludes the tutorial series about queues. In this series you learned how a queue works, what bounded and unbounded, blocking and non-blocking queues are, which queue implementations exist in the JDK and how you can implement queues yourself in different ways.

If you liked the series, please leave me a comment, or share the articles using the share buttons at the end. If you still have questions, please ask them via the comment function.

Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.

The last part of the tutorial series was about implementing a queue with a linked list. In this part, we implement a queue with an array – first a bounded queue (i.e., one with a fixed capacity) – and then an unbounded queue (i.e., one whose capacity can change).

Let’s start with the simple variant, the bounded queue.

Implementing a Bounded Queue with an Array

We create an empty array and fill it from left to right (i.e., ascending from index 0) with the elements inserted into the queue.

The following image shows a queue with an array called elements, which can hold eight elements. So far, six elements have been inserted into the queue. tailIndex always indicates the next insertion position:

When dequeuing the elements, we also read them from left to right and remove them from the array. headIndex always shows the next read position:

The following illustration shows the queue after we have retrieved the first four of the six elements:

Now that we are near the end of the array, we could (without additional logic) write only two more elements to the queue. To fill up the queue to eight elements again, there are two possible solutions:

1. We move the remaining elements to the left, to the beginning of the array. This operation is costly, especially for large arrays.
2. The better solution is a circular array. This means that when we reach the end of the array, we continue at its beginning. This applies to both the enqueue and dequeue operations.

Circular Array

To illustrate how a ring buffer works, I have rendered the array from the example as a circle:

We insert additional elements clockwise. In the following example, we add “mango”, “fig”, “pomelo”, and “apricot” to positions 6, 7 – and then 0 and 1:

Back in the “flat” representation, the array now looks like this:

Both in the circle representation and this one, it is easy to see that the element “fig” at index 7 is followed by the element “pomelo” at index 0.

Dequeueing the elements works in the same way. With each dequeue operation, headIndex moves one position to the right, where 7 is not followed by 8 but by 0.

Full Queue vs. Empty Queue

tailIndex and headIndex are in the same position for both an empty and a full queue. To be able to recognize when the queue is full, we also store the number of elements.

This is what a full queue might look like:

And so an empty one (e.g., after all eight elements have been taken from the queue just shown):

Storing the number of elements is not the only – but a very simple – way to distinguish a full queue from an empty one. Alternatives are, for example:

• Storing (besides the number of elements) only the tailIndex or the headIndex; then calculating the other from the number of elements (this, however, makes the code much more complex).
• Not storing the number of elements and detecting a full queue by checking that tailIndex is equal to headIndex and that the array does not contain any element at the tailIndex position.
• You do not fill the queue completely, but always leave at least one field empty.

Source Code for the Bounded Queue Using an Array

Implementing a bounded queue with an array is quite simple. You can also find the following code in the BoundedArrayQueue class in the GitHub repository.

public class BoundedArrayQueue<E> implements Queue<E> {

  private final Object[] elements;
  private int headIndex;
  private int tailIndex;
  private int numberOfElements;

  public BoundedArrayQueue(int capacity) {
    if (capacity < 1) {
      throw new IllegalArgumentException("Capacity must be 1 or higher");
    }

    elements = new Object[capacity];
  }

  @Override
  public void enqueue(E element) {
    if (numberOfElements == elements.length) {
      throw new IllegalStateException("The queue is full");
    }
    elements[tailIndex] = element;
    tailIndex++;
    if (tailIndex == elements.length) {
      tailIndex = 0;
    }
    numberOfElements++;
  }

  @Override
  public E dequeue() {
    final E element = elementAtHead();
    elements[headIndex] = null;
    headIndex++;
    if (headIndex == elements.length) {
      headIndex = 0;
    }
    numberOfElements--;
    return element;
  }

  @Override
  public E peek() {
    return elementAtHead();
  }

  private E elementAtHead() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }

    @SuppressWarnings("unchecked")
    E element = (E) elements[headIndex];

    return element;
  }

  @Override
  public boolean isEmpty() {
    return numberOfElements == 0;
  }
}Code language: Java (java)

Note that BoundedArrayQueue does not implement the java.util.Queue interface, but a custom one that defines only the four methods enqueue(), dequeue(), peek(), and isEmpty() (see Queue in the GitHub repository):

public interface Queue<E> {
  void enqueue(E element);
  E dequeue();
  E peek();
  boolean isEmpty();
}Code language: Java (java)

Find out how to use BoundedArrayQueue (and all other implementations of the Queue interface) in the QueueDemo program.

Implementing an Unbounded Queue with an Array

Implementing an unbounded queue, i.e., a queue with no size limit, is somewhat more complex. An array cannot grow. And even if it did – it could not grow at the end but would have to create free space at precisely the location where tailIndex and headIndex are pointing.

Let’s look again at the full queue from the end of the previous example:

To insert another element, we need to increase the queue’s capacity by increasing the size of the array.

(For reasons of space in the graphical representation, we increase the capacity by only two elements. In reality, you usually find increases by a factor of 1.5 or 2.0).

However, we would have to create this free space between the tail and head of the queue, i.e., in the middle of the array:

This is not possible without further ado. An array cannot grow – and certainly not in the middle. Instead, we have to create a new array and copy the existing elements into it.

But if we have to recopy the elements anyway, we can copy them in the correct order to the beginning of the new array, like this:

The code for this is not that complicated, as you will see in the next section.

Source Code for the Unbounded Queue Using an Array

The following code shows the ArrayQueue class from the tutorial GitHub repository.

There are two constructors: one that lets you specify the initial size of the array and a default constructor that sets the initial capacity to ten.

Each time the enqueue() method is called, it checks whether the array is full. If it is, it invokes the grow() method.

The grow() method first calls calculateNewCapacity() to calculate the new size of the array. I have printed this method here in simplified form: it multiplies the current size by 1.5.

The calculateNewCapacity() method in the GitHub repository has a more sophisticated algorithm and ensures that a specific maximum size is not exceeded. However, the focus of this article should not be on determining the new size but on the actual expansion of the array.

Therefore, the growToNewCapacity() method creates the new array, copies the elements to the appropriate positions in the new array, and resets headIndex and tailIndex.

public class ArrayQueue<E> implements Queue<E> {

  private static final int DEFAULT_INITIAL_CAPACITY = 10;

  private Object[] elements;
  private int headIndex;
  private int tailIndex;
  private int numberOfElements;

  public ArrayQueue() {
    this(DEFAULT_INITIAL_CAPACITY);
  }

  public ArrayQueue(int capacity) {
    if (capacity < 1) {
      throw new IllegalArgumentException("Capacity must be 1 or higher");
    }

    elements = new Object[capacity];
  }

  @Override
  public void enqueue(E element) {
    if (numberOfElements == elements.length) {
      grow();
    }
    elements[tailIndex] = element;
    tailIndex++;
    if (tailIndex == elements.length) {
      tailIndex = 0;
    }
    numberOfElements++;
  }

  private void grow() {
    int newCapacity = calculateNewCapacity(elements.length);
    growToNewCapacity(newCapacity);
  }

  private int calculateNewCapacity(int currentCapacity) {
    return currentCapacity + currentCapacity / 2;
  }

  private void growToNewCapacity(int newCapacity) {
    Object[] newArray = new Object[newCapacity];

    // Copy to the beginning of the new array: tailIndex to end of the old array
    int oldArrayLength = elements.length;
    int numberOfElementsAfterTail = oldArrayLength - tailIndex;
    System.arraycopy(elements, tailIndex, newArray, 0, numberOfElementsAfterTail);

    // Append to the new array: beginning to tailIndex of the old array
    if (tailIndex > 0) {
      System.arraycopy(elements, 0, newArray, numberOfElementsAfterTail, tailIndex);
    }

    // Adjust head and tail
    headIndex = 0;
    tailIndex = oldArrayLength;
    elements = newArray;
  }

  // dequeue(), peek(), elementAtHead(), isEmpty() are the same as in BoundedArrayQueue

}Code language: Java (java)

The methods dequeue(), peek(), elementAtHead(), and isEmpty() are the same as in the BoundedArrayQueue from the section above. I have therefore not printed them again.

You may have noticed that the queue can grow but not shrink again. Perhaps our queue only needs to store a high number of elements during peak loads and would then occupy memory with a mostly empty array. We could extend the queue to copy its contents back to a smaller array after a certain grace period.

I leave this extension to you as a practice task.

Outlook

In the next and last part of this tutorial series, I will show you how to implement a PriorityQueue yourself, based on a min-heap.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.

In the last part of this tutorial series, I showed you how to implement a queue with stacks. In this part, we will implement a queue using a linked list.

The Algorithm – Step by Step

Our queue consists of two references to list nodes: head and tail.

The head reference points to a list node containing the queue’s head element and a next pointer to a second list node. The second node, in turn, contains the second element and a pointer to the third list node, and so on.

The last node is referenced by both the next pointer of the second-to-last element and the tail pointer. It contains the last queue element, and its next reference points to null.

The following image shows an example queue in which the elements “banana”, “cherry”, and “grape” (in this order) have been inserted:

How do we reach this state?

Enqueue Algorithm

We start with an empty queue. Both head and tail references are null:

We insert the first element into the queue by wrapping it in a list node and having both head and tail point to that node:

We insert more elements as follows:

1. We wrap the element to be inserted in a new list node.
2. We let the next pointer of the last node, i.e., tail.next, point to the new node.
3. We also let tail point at the new node.

In the following image, you can see how to insert a second element, “cherry”, into the example queue:

Dequeue Algorithm

Retrieving the head element with dequeue() then works as follows:

1. We remember the element of the node referenced by head (in the example, that would be “banana”).
2. We let head point to head.next (in the example to the node that wraps “cherry”). If head is null afterward (i.e., the queue is empty), we also set tail to null.
3. We return the element remembered in step 1 (in the example, “banana”).
4. In a programming language with a garbage collector (such as Java), the GC will delete the node that is no longer referenced; in other languages (such as C++), we would have to delete it manually.

The following image illustrates the four steps:

The dashed border around the “banana” node in steps 2 and 3 represents that this node is no longer referenced at this time.

Source Code for the Queue with a Linked List

The following code shows the implementation of a queue with a linked list (LinkedListQueue in the GitHub repo). The class for the nodes, Node, can be found at the very end as a static inner class.

public class LinkedListQueue<E> implements Queue<E> {

  private Node<E> head;
  private Node<E> tail;

  @Override
  public void enqueue(E element) {
    Node<E> newNode = new Node<>(element);
    if (isEmpty()) {
      head = tail = newNode;
    } else {
      tail.next = newNode;
      tail = newNode;
    }
  }

  @Override
  public E dequeue() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    E element = head.element;
    head = head.next;
    if (head == null) {
      tail = null;
    }
    return element;
  }

  @Override
  public E peek() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    return head.element;
  }

  @Override
  public boolean isEmpty() {
    return head == null;
  }

  private static class Node<E> {
    final E element;
    Node<E> next;

    Node(E element) {
      this.element = element;
    }
  }
}
Code language: Java (java)

You can see how to use the LinkedListQueue class in the QueueDemo program.

Outlook

In the next part of the tutorial, I will show you how to implement a queue using an array.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.

In this part of the tutorial series, I’ll show you how to implement a queue using a stack (more precisely, using two stacks).

This variant has no practical use but is primarily an exercise task. As such, it is the counterpart to implementing a stack with a queue.

As a reminder, a stack is a data structure where elements are retrieved in the reverse order of insertion, i.e., a last-in-first-out (LIFO) data structure.

How can we use it to implement a queue, that is, a first-in-first-out (FIFO) data structure?

The Solution – Step by Step

We put the first element that we insert into the queue on a stack (in the example: “banana”). To remove it from the queue, we take it from the stack again:

That will no longer work with the second element since the stack works according to the LIFO principle. If, for example, “banana” and “cherry” are on the stack, we would have to take “cherry” first:

In a queue, however, we want the first element inserted (i.e., “banana”) to be the first to be removed.

With a stack alone, this is not possible.

Instead, we proceed as follows when inserting an element into the queue:

1. We create a temporary stack (shown in orange in the image below) and move all the elements of the original stack to the temporary stack.
2. We put the new element on the original stack.
3. We move all elements back from the temporary stack to the original stack. The temporary stack is then no longer needed.

The following illustration shows these three steps:

After that, the elements are on the stack in such a way that we can take the first inserted element, “banana”, first and then the second inserted element, “cherry”.

That works not only with two elements but with any number of elements. The following image shows how we insert the third element, “grape”, into the queue:

After that, we can take the elements out of the queue in first-in-first-out order, so first, the “banana”, which we inserted first, then the “cherry”, and finally the “grape” inserted last.

Source Code for the Queue with Stacks

The source code for this algorithm requires only a few lines of code.

As a stack, I use the ArrayStack class presented in the Stack tutorial. You could just as well use the JDK class Stack or any Deque implementation, e.g., an ArrayDeque.

You can find the code in the StackQueue class in the tutorial’s GitHub repository.

public class StackQueue<E> implements Queue<E> {

  private final Stack<E> stack = new ArrayStack<>();

  @Override
  public void enqueue(E element) {
    // 1. Move elements from main stack to a temporary stack
    Stack<E> temporaryStack = new ArrayStack<>();
    while (!stack.isEmpty()) {
      temporaryStack.push(stack.pop());
    }

    // 2. Push new element on the main stack
    stack.push(element);

    // 3. Move elements back from temporary stack to main stack
    while (!temporaryStack.isEmpty()) {
      stack.push(temporaryStack.pop());
    }
  }

  @Override
  public E dequeue() {
    return stack.pop();
  }

  @Override
  public E peek() {
    return stack.peek();
  }

  @Override
  public boolean isEmpty() {
    return stack.isEmpty();
  }
}Code language: Java (java)

Note that we do not implement the java.util.Queue interface here. That interface inherits from java.util.Collection, so we would have to implement many more methods.

Instead, I wrote a custom Queue interface for this tutorial that defines only the enqueue(), dequeue(), peek(), and isEmpty() methods:

public interface Queue<E> {
  void enqueue(E element);
  E dequeue();
  E peek();
  boolean isEmpty();
}Code language: Java (java)

Outlook

In the next part of the tutorial, you will learn how to implement a queue with a linked list.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.

This article provides an overview of all Queue implementations available in the JDK, including their characteristics, as well as a decision support for which implementation is best suited for which purpose.

The class names in the following table are linked to that article of the tutorial series in which the respective Queue implementation is explained in detail.

For an explanation of the terms blocking, non-blocking, fairness policy, bounded, and unbounded, see the article about the BlockingQueue interface.

¹ Weakly consistent: All elements that exist when the iterator is created are traversed by the iterator exactly once. Changes that occur after this can, but do not need to, be reflected by the iterator.

² Fail-fast: The iterator throws a ConcurrentModificationException if elements are added to or removed from the queue during iteration.

When Should You Use Which Queue Implementation?

Using the characteristics of the queue implementations described in the respective articles and summarized in the table above, you can find the proper queue for each use case.

For day-to-day use of general queue implementations, I make the following recommendations:

• ArrayDeque for single-threaded applications.
• ConcurrentLinkedQueue as a thread-safe, non-blocking, and unbounded queue.
• ArrayBlockingQueue as a thread-safe, blocking, bounded queue if you expect low to medium contention between producer and consumer threads.
• LinkedBlockingQueue as a thread-safe, blocking, bounded queue if you expect high contention between producer and consumer threads (best to test which implementation is more performant for your use case).

Here is the process in the form of a decision tree:

Optimized MPMC, MPSC, SPMC, and SPSC Queues

All thread-safe queue implementations provided by the JDK can be used in multi-producer-multi-consumer environments. This means that one or more writing threads and one or more reading threads can access the JDK queues concurrently.

With special mechanisms, it is possible to optimize queues so that the overhead for maintaining thread safety is minimized when there is a restriction to one reading and/or one writing thread.

Accordingly, the following four cases are distinguished:

• Multi-producer-multi-consumer (MPMC)
• Multi-producer-single-consumer (MPSC)
• Single-producer-multi-consumer (SPMC)
• Single-producer-single-consumer (SPSC)

The open-source library JCTools provides highly optimized queue implementations for all four cases.

Summary and Outlook

This article has provided an overview of all Queue implementations available in Java, as well as a decision aid for which cases to use which queue.

In the next parts of this series, I’ll show you how to implement queues yourself, starting with implementing a queue with a stack.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.

In this article, you will learn about a very special queue: LinkedTransferQueue. This article describes its characteristics and shows you how to use this queue with an example.

We are now at the lowest point of the queue class hierarchy:

TransferQueue Interface

As you can see in the class diagram, java.util.concurrent.LinkedTransferQueue is the only class that implements the TransferQueue interface.

TransferQueue defines additional enqueue methods that can only be executed successfully if another thread takes over the transferred item using take() or poll():

• transfer(E e) – passes the element to a thread that is waiting for an element with take() or poll(). If such a thread does not exist, the method blocks until another thread calls take() or poll().
• tryTransfer(E e) – passes the element to a thread that is waiting for an element using take() or poll(). If such a thread does not exist, the method immediately returns false.
• tryTransfer(E e, long timeout, TimeUnit unit) – passes the element to a thread that is waiting for an element using take() or poll(). If such a thread does not exist and does not appear within the waiting time, the method returns false.

LinkedTransferQueue Characteristics

LinkedTransferQueue is an unbounded blocking queue, i.e., the regular enqueue operations put() and offer() cannot block (since the queue can grow to any size). Blocking, however, can:

• the dequeue operations (when the queue is empty),
• and the transfer() or tryTransfer() methods of the TransferQueue interface until the respective elements are retrieved.

LinkedTransferQueue is based on a singly linked list. As a result, the time complexity of the size() method is O(n) (and not O(1) as in the array-based queues)¹, since the entire list must be traversed to determine its length.

Thread safety is achieved through non-blocking compare-and-set (CAS) operations, ensuring high performance with low to moderate contention (access conflicts through multiple threads).

The characteristics in detail:

¹ You can learn about time complexity in the article “Big O Notation and Time Complexity – Easily Explained“.

² Weakly consistent: All elements that exist when the iterator is created are traversed by the iterator exactly once. Changes that occur after this can, but do not need to, be reflected by the iterator.

Recommended Use Case

LinkedTransferQueue is not used in the JDK. Initially, it was implemented for the fork/join framework introduced in JDK 7 but was not used for it after all. Therefore, the probability of bugs is relatively high, so you should refrain from using this class.

LinkedTransferQueue Example

In the following example (→ code on GitHub), we start two threads that call LinkedTransferQueue.transfer(). After that, one element is written directly to the queue. Then, we create two more threads that call transfer(). Finally, we remove elements from the queue until it is empty again.

public class LinkedTransferQueueExample {
  public static void main(String[] args) throws InterruptedException {
    TransferQueue<Integer> queue = new LinkedTransferQueue<>();

    // Start 2 threads calling queue.transfer(),
    startTransferThread(queue, 1);
    startTransferThread(queue, 2);

    // ... then put one element directly,
    enqueueViaPut(queue, 3);

    // ... then start 2 more threads calling queue.transfer().
    startTransferThread(queue, 4);
    startTransferThread(queue, 5);

    // Now take all elements until the queue is empty
    while (!queue.isEmpty()) {
      dequeueViaTake(queue);
    }
  }

  private static void startTransferThread(TransferQueue<Integer> queue, int element)
      throws InterruptedException {
    new Thread(() -> enqueueViaTransfer(queue, element)).start();

    // Wait a bit to let the thread enqueue the element
    Thread.sleep(100);
    log("                            --> queue = " + queue);
  }

  private static void enqueueViaTransfer(TransferQueue<Integer> queue, int element) {
    log("Calling queue.transfer(%d)...", element);
    try {
      queue.transfer(element);
      log("queue.transfer(%d) returned  --> queue = %s", element, queue);
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }

  private static void enqueueViaPut(TransferQueue<Integer> queue, int element)
      throws InterruptedException {
    log("Calling queue.put(%d)...", element);
    queue.put(element);
    log("queue.put(%d) returned       --> queue = %s", element, queue);
  }

  private static void dequeueViaTake(TransferQueue<Integer> queue)
      throws InterruptedException {
    log("    Calling queue.take() (queue = %s)...", queue);
    Integer e = queue.take();
    log("    queue.take() returned %d --> queue = %s", e, queue);

    // Wait a bit to get the log output in a readable order
    Thread.sleep(10);
  }

  private static void log(String format, Object... args) {
    System.out.printf(
        Locale.US, "[%-8s] %s%n",
        Thread.currentThread().getName(),
        String.format(format, args));
  }
}Code language: Java (java)

Below you can see the output of the program:

[Thread-0] Calling queue.transfer(1)...
[main    ]                             --> queue = [1]
[Thread-1] Calling queue.transfer(2)...
[main    ]                             --> queue = [1, 2]
[main    ] Calling queue.put(3)...
[main    ] queue.put(3) returned       --> queue = [1, 2, 3]
[Thread-2] Calling queue.transfer(4)...
[main    ]                             --> queue = [1, 2, 3, 4]
[Thread-3] Calling queue.transfer(5)...
[main    ]                             --> queue = [1, 2, 3, 4, 5]
[main    ]     Calling queue.take() (queue = [1, 2, 3, 4, 5])...
[main    ]     queue.take() returned 1 --> queue = [2, 3, 4, 5]
[Thread-0] queue.transfer(1) returned  --> queue = [2, 3, 4, 5]
[main    ]     Calling queue.take() (queue = [2, 3, 4, 5])...
[main    ]     queue.take() returned 2 --> queue = [3, 4, 5]
[Thread-1] queue.transfer(2) returned  --> queue = [3, 4, 5]
[main    ]     Calling queue.take() (queue = [3, 4, 5])...
[main    ]     queue.take() returned 3 --> queue = [4, 5]
[main    ]     Calling queue.take() (queue = [4, 5])...
[main    ]     queue.take() returned 4 --> queue = [5]
[Thread-2] queue.transfer(4) returned  --> queue = [5]
[main    ]     Calling queue.take() (queue = [5])...
[main    ]     queue.take() returned 5 --> queue = []
[Thread-3] queue.transfer(5) returned  --> queue = []Code language: plaintext (plaintext)

You can see nicely how, in the beginning, transfer() is called twice (but does not return), how then put() is called once (and returns), and how transfer() is called two more times (and does not return).

After that, we see how the first element is taken, and subsequently transfer(1) returns as well.

Then the second element is taken, and transfer(2) returns.

The removal of the 3 does not lead to any further action, since it was written to the queue with put().

After removing the 4 and the 5, you can again see nicely how the respective transfer() call returns.

Summary and Outlook

In this article, you learned about the TransferQueue interface and LinkedTransferQueue implementation and saw how to use them with an example.

In the next part of this tutorial series, you will find a summary of all queue implementations of the JDK and an overview of in which cases you should use which implementation.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.

This article is about a special queue – SynchronousQueue – and its properties and applications. An example will show you how to use SynchronousQueue.

Here we are in the class hierarchy:

SynchronousQueue Characteristics

The word “Synchronous” in the java.util.concurrent.SynchronousQueue class is not to be confused with “synchronized”. Instead, it means that each enqueue operation must wait for a corresponding dequeue operation, and each dequeue operation must wait for an enqueue operation.

A SynchronousQueue never contains elements, even if enqueue operations are currently waiting for dequeue operations. Similarly, the size of a SynchronousQueue is always 0, and peek() always returns null.

SynchronousQueue and ArrayBlockingQueue are the only queue implementations that offer a fairness policy. There is a peculiarity here: If the fairness policy is not activated, blocking calls are served in unspecified order according to the documentation. In fact, however, they are served precisely in reverse order (i.e., in LIFO order) since internally, SynchronousQueue uses a stack.

The characteristics of SynchronousQueue in detail:

Recommended Use Case

Like DelayQueue and LinkedTransferQueue, I have never used SynchronousQueue directly in my own projects.

If its characteristics fit your requirements, you can use it without hesitation. In the JDK, SynchronousQueue is used in Executors.newCachedThreadPool() as a “work queue” for the executor, so the likelihood of bugs is extremely low.

SynchronousQueue Example

In the following example (→ code on GitHub), three threads are started that call SynchronousQueue.put(), then six threads that call SynchronousQueue.take(), and then another three threads that execute SynchronousQueue.put():

public class SynchronousQueueExample {
  private static final boolean FAIR = false;

  public static void main(String[] args) throws InterruptedException {
    BlockingQueue<Integer> queue = new SynchronousQueue<>(FAIR);

    // Start 3 producing threads
    for (int i = 0; i < 3; i++) {
      int element = i; // Assign to an effectively final variable
      new Thread(() -> enqueue(queue, element)).start();
      Thread.sleep(250);
    }

    // Start 6 consuming threads
    for (int i = 0; i < 6; i++) {
      new Thread(() -> dequeue(queue)).start();
      Thread.sleep(250);
    }

    // Start 3 more producing threads
    for (int i = 3; i < 6; i++) {
      int element = i; // Assign to an effectively final variable
      new Thread(() -> enqueue(queue, element)).start();
      Thread.sleep(250);
    }
  }

  private static void enqueue(BlockingQueue<Integer> queue, int element) {
    log("Calling queue.put(%d) (queue = %s)...", element, queue);
    try {
      queue.put(element);
      log("queue.put(%d) returned (queue = %s)", element, queue);
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }

  private static void dequeue(BlockingQueue<Integer> queue) {
    log("    Calling queue.take() (queue = %s)...", queue);
    try {
      Integer element = queue.take();
      log("    queue.take() returned %d (queue = %s)", element, queue);
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }

  private static void log(String format, Object... args) {
    System.out.printf(
        Locale.US,
        "[%-9s] %s%n",
        Thread.currentThread().getName(),
        String.format(format, args));
  }
}
Code language: Java (java)

The output shows how the first three calls to put() (by threads 0, 1, and 2) block until the inserted elements are retrieved with take() (by threads 3, 4, and 5) in reverse order.

After that, the three following calls to take() (threads 6, 7, 8) block until three more elements have been written to the queue with put() (threads 9, 10, 11).

The queue remains empty for the entire time.

[Thread-0 ] Calling queue.put(0) (queue = [])...
[Thread-1 ] Calling queue.put(1) (queue = [])...
[Thread-2 ] Calling queue.put(2) (queue = [])...
[Thread-3 ]     Calling queue.take() (queue = [])...
[Thread-3 ]     queue.take() returned 2 (queue = [])
[Thread-2 ] queue.put(2) returned (queue = [])
[Thread-4 ]     Calling queue.take() (queue = [])...
[Thread-4 ]     queue.take() returned 1 (queue = [])
[Thread-1 ] queue.put(1) returned (queue = [])
[Thread-5 ]     Calling queue.take() (queue = [])...
[Thread-5 ]     queue.take() returned 0 (queue = [])
[Thread-0 ] queue.put(0) returned (queue = [])
[Thread-6 ]     Calling queue.take() (queue = [])...
[Thread-7 ]     Calling queue.take() (queue = [])...
[Thread-8 ]     Calling queue.take() (queue = [])...
[Thread-9 ] Calling queue.put(3) (queue = [])...
[Thread-9 ] queue.put(3) returned (queue = [])
[Thread-8 ]     queue.take() returned 3 (queue = [])
[Thread-10] Calling queue.put(4) (queue = [])...
[Thread-10] queue.put(4) returned (queue = [])
[Thread-7 ]     queue.take() returned 4 (queue = [])
[Thread-11] Calling queue.put(5) (queue = [])...
[Thread-11] queue.put(5) returned (queue = [])
[Thread-6 ]     queue.take() returned 5 (queue = [])Code language: plaintext (plaintext)

If you set the FAIR constant to true, you will see the elements being taken in FIFO order rather than LIFO order.

Summary and Outlook

In this article, you learned about SynchronousQueue – a queue that never contains elements but passes them directly from the enqueuing threads to the dequeuing threads.

The next part is about the last queue implementation of this tutorial series: LinkedTransferQueue.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.

This and the following parts of this tutorial series are about queues for particular purposes. We will start with DelayQueue, a queue that sorts the elements by expiration time.

We are here in the class hierarchy:

DelayQueue Characteristics

The java.util.concurrent.DelayQueue class – just like the PriorityQueue it uses internally – is not a FIFO queue. It does not take out the element that has been in the queue the longest. Instead, an element can be taken when a wait time (“delay”) assigned to that element has expired.

Therefore, the elements must implement the interface java.util.concurrent.Delayed and its getDelay() method. This method returns the remaining waiting time that must elapse before the element can be removed from the queue.

DelayQueue is blocking but unbounded, so it can hold any number of elements and blocks only on removal (until the wait time expires), not on insertion.

Thread safety is achieved by pessimistic locking via a single ReentrantLock.

The characteristics in detail:

¹ Weakly consistent: All elements that exist when the iterator is created are traversed by the iterator exactly once. Changes that occur after this can, but do not need to, be reflected by the iterator.

Recommended Use Case

I have never needed DelayQueue and cannot recommend it for any practical purpose that I know of. It is used only once in the JDK (in an old Swing class that could have been implemented more elegantly with a ScheduledExecutorService). Therefore, it may contain undiscovered bugs.

DelayQueue Example

In the following example (→ code on GitHub), we fill a DelayQueue with instances of the DelayedElement class. Those instances contain a random number and a random initial delay between 100 and 1,000 ms. Then we call poll() until the queue is empty again.

public class DelayQueueExample {
  public static void main(String[] args) {
    BlockingQueue<DelayedElement<Integer>> queue = new DelayQueue<>();
    ThreadLocalRandom random = ThreadLocalRandom.current();
    long startTime = System.currentTimeMillis();

    // Enqueue random numbers with random initial delays
    for (int i = 0; i < 7; i++) {
      int randomNumber = random.nextInt(10, 100);
      int initialDelayMillis = random.nextInt(100, 1000);
      DelayedElement<Integer> element = 
          new DelayedElement<>(randomNumber, initialDelayMillis);
      queue.offer(element);
      System.out.printf(
          "[%3dms] queue.offer(%s)   --> queue = %s%n",
          System.currentTimeMillis() - startTime, element, queue);
    }

    // Dequeue all elements
    while (!queue.isEmpty()) {
      try {
        DelayedElement<Integer> element = queue.take();
        System.out.printf(
            "[%3dms] queue.poll() = %s --> queue = %s%n",
            System.currentTimeMillis() - startTime, element, queue);
      } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
      }
    }
  }
}Code language: Java (java)

And here is the corresponding DelayedElement class (→ code on GitHub). In order not to make the code even longer, the sorting is not stable. I.e., if two elements with the same waiting time are inserted into the queue, they will be removed in random order relative to each other.

public class DelayedElement<E extends Comparable<E>> implements Delayed {
  private final E e;
  private final long initialDelayMillis;
  private final long expiration;

  public DelayedElement(E e, long initialDelayMillis) {
    this.e = e;
    this.initialDelayMillis = initialDelayMillis;
    this.expiration = System.currentTimeMillis() + initialDelayMillis;
  }

  @Override
  public long getDelay(TimeUnit unit) {
    long remainingDelayMillis = expiration - System.currentTimeMillis();
    return unit.convert(remainingDelayMillis, TimeUnit.MILLISECONDS);
  }

  @Override
  public int compareTo(Delayed o) {
    DelayedElement<?> other = (DelayedElement<?>) o;
    return Long.compare(expiration, other.expiration);
  }

  @Override
  public String toString() {
    return "{%s, %dms}".formatted(e, initialDelayMillis);
  }
}
Code language: Java (java)

Here is an example output of the program. It is good to see how the queue is not sorted¹, but the element with the shortest waiting time is always at the head (left) and that the elements are taken (approximately) after their respective waiting times have expired:

[  1ms] queue.offer({19, 713ms})   --> queue = [{19, 713ms}]
[ 28ms] queue.offer({15, 643ms})   --> queue = [{15, 643ms}, {19, 713ms}]
[ 29ms] queue.offer({35, 253ms})   --> queue = [{35, 253ms}, {19, 713ms}, {15, 643ms}]
[ 29ms] queue.offer({11, 781ms})   --> queue = [{35, 253ms}, {19, 713ms}, {15, 643ms}, {11, 781ms}]
[ 29ms] queue.offer({17, 844ms})   --> queue = [{35, 253ms}, {19, 713ms}, {15, 643ms}, {11, 781ms}, {17, 844ms}]
[ 29ms] queue.offer({40, 490ms})   --> queue = [{35, 253ms}, {19, 713ms}, {40, 490ms}, {11, 781ms}, {17, 844ms}, {15, 643ms}]
[ 30ms] queue.offer({39, 119ms})   --> queue = [{39, 119ms}, {19, 713ms}, {35, 253ms}, {11, 781ms}, {17, 844ms}, {15, 643ms}, {40, 490ms}]
[151ms] queue.poll() = {39, 119ms} --> queue = [{35, 253ms}, {19, 713ms}, {40, 490ms}, {11, 781ms}, {17, 844ms}, {15, 643ms}]
[283ms] queue.poll() = {35, 253ms} --> queue = [{40, 490ms}, {19, 713ms}, {15, 643ms}, {11, 781ms}, {17, 844ms}]
[520ms] queue.poll() = {40, 490ms} --> queue = [{15, 643ms}, {19, 713ms}, {17, 844ms}, {11, 781ms}]
[673ms] queue.poll() = {15, 643ms} --> queue = [{19, 713ms}, {11, 781ms}, {17, 844ms}]
[716ms] queue.poll() = {19, 713ms} --> queue = [{11, 781ms}, {17, 844ms}]
[811ms] queue.poll() = {11, 781ms} --> queue = [{17, 844ms}]
[874ms] queue.poll() = {17, 844ms} --> queue = []Code language: plaintext (plaintext)

¹ In fact, you can see the order of the elements in the array representation of the min-heap.

Summary and Outlook

In this article, you have learned everything about DelayQueue, its characteristics, and how to use it.

In the next part of this series, I will introduce you to another special queue – one that never contains any elements: SynchronousQueue.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.

In this article, you will learn how PriorityBlockingQueue works and what characteristics it has. An example will show you how to use it.

Here we are in the class hierarchy:

PriorityBlockingQueue Characteristics

The java.util.concurrent.PriorityBlockingQueue is a thread-safe and blocking variant of the PriorityQueue. In the linked article, you will also learn what a priority queue is.

As with PriorityQueue, the elements are stored in an array representing a min-heap. The iterator iterates through the elements in the corresponding order.

A single ReentrantLock ensures thread safety.

PriorityBlockingQueue is not bounded, so it has no capacity limit. That means that put(e) and offer(e, time, unit) never block. Only the dequeue operations take() and poll(time, unit) block when the queue is empty.

The characteristics in detail:

¹ Weakly consistent: All elements that exist when the iterator is created are traversed by the iterator exactly once. Changes that occur after this can, but do not need to, be reflected by the iterator.

Recommended Use Case

PriorityBlockingQueue is not used in the JDK, and therefore we cannot exclude the possibility that it contains bugs. If you need a queue with appropriate characteristics and use PriorityBlockingQueue, make sure you test your application intensively.

PriorityBlockingQueue Example

The following example shows how to create a PriorityBlockingQueue and how multiple threads read and write to it (→ code on GitHub).

Reading threads run every 3 seconds, starting immediately after the queue is created.

Writing threads start after 3.5 seconds (so that two reading threads are already waiting) and write a random value to the queue every second.

public class PriorityBlockingQueueExample {
  private static final long startTime = System.currentTimeMillis();

  public static void main(String[] args) throws InterruptedException {
    BlockingQueue<Integer> queue = new PriorityBlockingQueue<>();
    ScheduledExecutorService pool = Executors.newScheduledThreadPool(10);

    // Start reading from the queue immediately, every 3 seconds
    for (int i = 0; i < 8; i++) {
      int delaySeconds = i * 3;
      pool.schedule(() -> dequeue(queue), delaySeconds, TimeUnit.SECONDS);
    }

    // Start writing to the queue after 3.5 seconds (so there are already 2 threads
    // waiting), every 1 seconds (so that the queue fills faster than it's emptied,
    // so that we see some more elements and their order in the queue)
    for (int i = 0; i < 8; i++) {
      int delayMillis = 3500 + i * 1000;
      pool.schedule(() -> enqueue(queue), delayMillis, TimeUnit.MILLISECONDS);
    }

    pool.shutdown();
    pool.awaitTermination(1, TimeUnit.MINUTES);
  }

  private static void enqueue(BlockingQueue<Integer> queue) {
    int element = ThreadLocalRandom.current().nextInt(10, 100);
    log("Calling queue.put(%d) (queue = %s)...", element, queue);
    try {
      queue.put(element);
      log("queue.put(%d) returned (queue = %s)", element, queue);
    } catch (InterruptedException ex) {
      Thread.currentThread().interrupt();
    }
  }

  private static void dequeue(BlockingQueue<Integer> queue) {
    log("    Calling queue.take() (queue = %s)...", queue);
    try {
      Integer element = queue.take();
      log("    queue.take() returned %d (queue = %s)", element, queue);
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }

  private static void log(String format, Object... args) {
    System.out.printf(
        Locale.US,
        "[%4.1fs] [%-16s] %s%n",
        (System.currentTimeMillis() - startTime) / 1000.0,
        Thread.currentThread().getName(),
        String.format(format, args));
  }
}Code language: Java (java)

Below you can see an example output of the program:

[ 0.0s] [pool-1-thread-1 ]     Calling queue.take() (queue = [])...
[ 3.0s] [pool-1-thread-2 ]     Calling queue.take() (queue = [])...
[ 3.5s] [pool-1-thread-6 ] Calling queue.put(87) (queue = [])...
[ 3.5s] [pool-1-thread-6 ] queue.put(87) returned (queue = [])
[ 3.5s] [pool-1-thread-1 ]     queue.take() returned 87 (queue = [])
[ 4.5s] [pool-1-thread-9 ] Calling queue.put(89) (queue = [])...
[ 4.5s] [pool-1-thread-9 ] queue.put(89) returned (queue = [])
[ 4.5s] [pool-1-thread-2 ]     queue.take() returned 89 (queue = [])
[ 5.5s] [pool-1-thread-7 ] Calling queue.put(31) (queue = [])...
[ 5.5s] [pool-1-thread-7 ] queue.put(31) returned (queue = [31])
[ 6.0s] [pool-1-thread-4 ]     Calling queue.take() (queue = [31])...
[ 6.0s] [pool-1-thread-4 ]     queue.take() returned 31 (queue = [])
[ 6.5s] [pool-1-thread-5 ] Calling queue.put(71) (queue = [])...
[ 6.5s] [pool-1-thread-5 ] queue.put(71) returned (queue = [71])
[ 7.5s] [pool-1-thread-8 ] Calling queue.put(15) (queue = [71])...
[ 7.5s] [pool-1-thread-8 ] queue.put(15) returned (queue = [15, 71])
[ 8.5s] [pool-1-thread-10] Calling queue.put(33) (queue = [15, 71])...
[ 8.5s] [pool-1-thread-10] queue.put(33) returned (queue = [15, 71, 33])
[ 9.0s] [pool-1-thread-3 ]     Calling queue.take() (queue = [15, 71, 33])...
[ 9.0s] [pool-1-thread-3 ]     queue.take() returned 15 (queue = [33, 71])
[ 9.5s] [pool-1-thread-6 ] Calling queue.put(58) (queue = [33, 71])...
[ 9.5s] [pool-1-thread-6 ] queue.put(58) returned (queue = [33, 71, 58])
[10.5s] [pool-1-thread-1 ] Calling queue.put(19) (queue = [33, 71, 58])...
[10.5s] [pool-1-thread-1 ] queue.put(19) returned (queue = [19, 33, 58, 71])
[12.0s] [pool-1-thread-9 ]     Calling queue.take() (queue = [19, 33, 58, 71])...
[12.0s] [pool-1-thread-9 ]     queue.take() returned 19 (queue = [33, 71, 58])
[15.0s] [pool-1-thread-2 ]     Calling queue.take() (queue = [33, 71, 58])...
[15.0s] [pool-1-thread-2 ]     queue.take() returned 33 (queue = [58, 71])
[18.0s] [pool-1-thread-7 ]     Calling queue.take() (queue = [58, 71])...
[18.0s] [pool-1-thread-7 ]     queue.take() returned 58 (queue = [71])
[21.0s] [pool-1-thread-4 ]     Calling queue.take() (queue = [71])...
[21.0s] [pool-1-thread-4 ]     queue.take() returned 71 (queue = [])Code language: plaintext (plaintext)

What can we see in this sample output?

First of all, you see how after 0.0 s and 3.0 s, threads 1 and 2 block when calling take() because the queue is empty.

After 3.5 s, thread 6 writes the 87 into the queue. Immediately afterward, the previously blocked thread 1 wakes up again and takes the 87.

After 4.5 s, thread 9 writes the 89 into the queue, which is immediately taken out again by thread 2.

After 5.5 s, the 31 is written into the queue, which is taken out again after 6.0 s.

After 6.5 s, 7.5 s, and 8.5 s, the 71, the 15, and the 33 are written into the queue. You can see how the smallest element is always at the head (left) of the queue.

After 9.0 s, the smallest element, the 15, is removed. The next smallest element, 33, is then placed at the head of the queue.

After 9.5 s and 10.5 s, two more elements, 58 and 19, are written to the queue. Again, you can see how the smallest element is at the queue’s head.

The queue now contains four elements. No other elements are written to the queue, and the existing elements are taken according to their priority.

Summary and Outlook

In this article, you learned about the characteristics of the PriorityBlockingQueue and how to use it.

Starting with the next part of the tutorial series, I will introduce you to some queue implementations for special cases, beginning with the DelayQueue.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.

This article is about the ArrayBlockingQueue and its properties. You will see how the ArrayBlockingQueue is used with an example. I will also give you a recommendation in which cases you should use this queue.

Here we are in the class hierarchy:

ArrayBlockingQueue Characteristics

The class java.util.concurrent.ArrayBlockingQueue is based on an array and – like most queue implementations – is thread-safe (see below). It is bounded (has a maximum capacity), accordingly blocking, and provides a fairness policy (i.e., blocking methods are served in the order they were called).

The characteristics at a glance:

¹ Weakly consistent: All elements that exist when the iterator is created are traversed by the iterator exactly once. Changes that occur after this can, but do not need to, be reflected by the iterator.

Recommended Use Case

Due to the possibly high contention with simultaneous read and write access, you should – if you need a blocking, thread-safe queue – test whether a LinkedBlockingQueue is more performant for your specific purpose. While this queue is based on a linked list, it uses two separate ReentrantLocks for writing and reading, which reduces access conflicts.

ArrayBlockingQueue Example

In the following example, we create an ArrayBlockingQueue with capacity 3. Then we have a ScheduledExecutorService write and read elements to and from the queue at specified intervals (→ code on GitHub):

public class ArrayBlockingQueueExample {
  private static final long startTime = System.currentTimeMillis();

  public static void main(String[] args) throws InterruptedException {
    BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(3);
    ScheduledExecutorService pool = Executors.newScheduledThreadPool(10);

    // Start reading from the queue immediately, every 3 seconds
    for (int i = 0; i < 10; i++) {
      int delaySeconds = i * 3;
      pool.schedule(() -> dequeue(queue), delaySeconds, TimeUnit.SECONDS);
    }

    // Start writing to the queue after 3.5 seconds (so there are already 2 threads 
    // waiting), every 1 seconds (so that the queue fills faster than it's emptied, 
    // so that we see a full queue soon)
    for (int i = 0; i < 10; i++) {
      int element = i; // Assign to an effectively final variable
      int delayMillis = 3500 + i * 1000;
      pool.schedule(() -> enqueue(queue, element), delayMillis, TimeUnit.MILLISECONDS);
    }

    pool.shutdown();
    pool.awaitTermination(1, TimeUnit.MINUTES);
  }

  private static void enqueue(BlockingQueue<Integer> queue, int element) {
    log("Calling queue.put(%d) (queue = %s)...", element, queue);
    try {
      queue.put(element);
      log("queue.put(%d) returned (queue = %s)", element, queue);
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }

  private static void dequeue(BlockingQueue<Integer> queue) {
    log("    Calling queue.take() (queue = %s)...", queue);
    try {
      Integer element = queue.take();
      log("    queue.take() returned %d (queue = %s)", element, queue);
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }

  private static void log(String format, Object... args) {
    System.out.printf(
        Locale.US,
        "[%4.1fs] [%-16s] %s%n",
        (System.currentTimeMillis() - startTime) / 1000.0,
        Thread.currentThread().getName(),
        String.format(format, args));
  }
}Code language: Java (java)

We try to read an element from the queue every three seconds, starting immediately. We write the elements every second but do not start until 3.5 s have passed. At this point, two reading threads should have already blocked and are waiting for elements to be written to the queue.

Since we write faster than we read, the queue should soon reach its capacity limit. The writing threads should block from that moment until the reading threads have caught up.

Here is a sample output:

[ 0.0s] [pool-1-thread-1 ]     Calling queue.take() (queue = [])...
[ 3.0s] [pool-1-thread-2 ]     Calling queue.take() (queue = [])...
[ 3.5s] [pool-1-thread-3 ] Calling queue.put(0) (queue = [])...
[ 3.5s] [pool-1-thread-3 ] queue.put(0) returned (queue = [])
[ 3.5s] [pool-1-thread-1 ]     queue.take() returned 0 (queue = [])
[ 4.5s] [pool-1-thread-9 ] Calling queue.put(1) (queue = [])...
[ 4.5s] [pool-1-thread-9 ] queue.put(1) returned (queue = [])
[ 4.5s] [pool-1-thread-2 ]     queue.take() returned 1 (queue = [])
[ 5.5s] [pool-1-thread-7 ] Calling queue.put(2) (queue = [])...
[ 5.5s] [pool-1-thread-7 ] queue.put(2) returned (queue = [2])
[ 6.0s] [pool-1-thread-8 ]     Calling queue.take() (queue = [2])...
[ 6.0s] [pool-1-thread-8 ]     queue.take() returned 2 (queue = [])
[ 6.5s] [pool-1-thread-5 ] Calling queue.put(3) (queue = [])...
[ 6.5s] [pool-1-thread-5 ] queue.put(3) returned (queue = [3])
[ 7.5s] [pool-1-thread-4 ] Calling queue.put(4) (queue = [3])...
[ 7.5s] [pool-1-thread-4 ] queue.put(4) returned (queue = [3, 4])
[ 8.5s] [pool-1-thread-10] Calling queue.put(5) (queue = [3, 4])...
[ 8.5s] [pool-1-thread-10] queue.put(5) returned (queue = [3, 4, 5])
[ 9.0s] [pool-1-thread-6 ]     Calling queue.take() (queue = [3, 4, 5])...
[ 9.0s] [pool-1-thread-6 ]     queue.take() returned 3 (queue = [4, 5])
[ 9.5s] [pool-1-thread-3 ] Calling queue.put(6) (queue = [4, 5])...
[ 9.5s] [pool-1-thread-3 ] queue.put(6) returned (queue = [4, 5, 6])
[10.5s] [pool-1-thread-1 ] Calling queue.put(7) (queue = [4, 5, 6])...
[11.5s] [pool-1-thread-9 ] Calling queue.put(8) (queue = [4, 5, 6])...
[12.0s] [pool-1-thread-2 ]     Calling queue.take() (queue = [4, 5, 6])...
[12.0s] [pool-1-thread-2 ]     queue.take() returned 4 (queue = [5, 6, 7])
[12.0s] [pool-1-thread-1 ] queue.put(7) returned (queue = [5, 6, 7])
[12.5s] [pool-1-thread-7 ] Calling queue.put(9) (queue = [5, 6, 7])...
[15.0s] [pool-1-thread-8 ]     Calling queue.take() (queue = [5, 6, 7])...
[15.0s] [pool-1-thread-8 ]     queue.take() returned 5 (queue = [6, 7, 8])
[15.0s] [pool-1-thread-9 ] queue.put(8) returned (queue = [6, 7, 8])
[18.0s] [pool-1-thread-5 ]     Calling queue.take() (queue = [6, 7, 8])...
[18.0s] [pool-1-thread-5 ]     queue.take() returned 6 (queue = [7, 8, 9])
[18.0s] [pool-1-thread-7 ] queue.put(9) returned (queue = [7, 8, 9])
[21.0s] [pool-1-thread-4 ]     Calling queue.take() (queue = [7, 8, 9])...
[21.0s] [pool-1-thread-4 ]     queue.take() returned 7 (queue = [8, 9])
[24.0s] [pool-1-thread-10]     Calling queue.take() (queue = [8, 9])...
[24.0s] [pool-1-thread-10]     queue.take() returned 8 (queue = [9])
[27.0s] [pool-1-thread-6 ]     Calling queue.take() (queue = [9])...
[27.0s] [pool-1-thread-6 ]     queue.take() returned 9 (queue = [])Code language: plaintext (plaintext)

As predicted, the first two read attempts block at 0.0 s and 3.0 s because no elements have yet been written to the queue.

After 3.5 s, the first element is written, which wakes up the first thread and removes this element again. After 4.5 s, the second element is written, waking up the second thread to remove the element.

Since the program writes faster than it reads, after 10.5 s, thread 1 blocks, after 11.5 s, thread 9 blocks, and after 12.5 s, thread 7 blocks when trying to write additional elements into the queue, which is full at that time.

After 12.0 s, an element is removed, and thread 1 can continue writing. After 15.0 s, another element is taken, and thread 9 can continue. After 18.0 s, thread 7 can continue.

Since no other elements are written to the queue, it empties again towards the end.

Is ArrayBlockingQueue Thread-Safe?

Yes, ArrayBlockingQueue is thread-safe.

A single ReentrantLock maintains ArrayBlockingQueue‘s thread-safety. It is used for the queue’s head and tail simultaneously so that access conflicts (“thread contention”) between producer and consumer threads can occur in case of simultaneous read and write accesses.

Explicit locks such as ReentrantLock are mainly suitable for high-contention applications. Optimistic locking is better for low to moderate thread contention.

Differences from other queues:

• With LinkedBlockingQueue, thread safety is provided by not one but two locks. Thus, producer and consumer threads cannot block each other.
• With ConcurrentLinkedQueue, thread safety is provided by optimistic locking via compare-and-set, resulting in better performance with low to moderate contention.

Summary and Outlook

This article has introduced you to the ArrayBlockingQueue. This queue is thread-safe, blocking, and bounded. With an example, you have seen how you can use ArrayBlockingQueue.

As the name suggests, this queue is based on an array. The linked list-based counterpart – LinkedBlockingQueue – was covered in the previous part of the series.

The next part of the series is about PriorityBlockingQueue – a thread-safe and blocking variant of the PriorityQueue presented previously.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.

This part of the tutorial series is about LinkedBlockingQueue. You will get to know its unique characteristics and see how to use this queue with an example. You will also learn when exactly you should use this queue.

Here we are in the class hierarchy:

LinkedBlockingQueue Characteristics

The class java.util.concurrent.LinkedBlockingQueue is – just like ConcurrentLinkedQueue – based on a linked list, but is – like ArrayBlockingQueue presented in the next part – thread-safe (see below), bounded, and blocking.

Unlike ArrayBlockingQueue, LinkedBlockingQueue does not provide a fairness policy. (Fairness policy means that blocking methods are served in the order they were called.)

The queue’s characteristics in detail:

¹ Weakly consistent: All elements that exist when the iterator is created are traversed by the iterator exactly once. Changes that occur after this can, but do not need to, be reflected by the iterator.

Recommended Use Case

I recommend LinkedBlockingQueue if you need a blocking, thread-safe queue.

By the way, the LinkedBlockingQueue class is used by Executors.newFixedThreadPool() and Executors.newSingleThreadedExecutor() as a “work queue” for the executor. It is, therefore, used intensively, which keeps the probability of bugs extremely low.

LinkedBlockingQueue Example

The following example shows how to use LinkedBlockingQueue. We create a queue with a capacity of 3. Immediately afterward, we start reading elements from the queue at intervals of three seconds. After 3.5 seconds, we begin writing elements to the queue at intervals of one second each (→ code on GitHub).

public class LinkedBlockingQueueExample {
  private static final long startTime = System.currentTimeMillis();

  public static void main(String[] args) throws InterruptedException {
    BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(3);
    ScheduledExecutorService pool = Executors.newScheduledThreadPool(10);

    // Start reading from the queue immediately, every 3 seconds
    for (int i = 0; i < 10; i++) {
      int delaySeconds = i * 3;
      pool.schedule(() -> dequeue(queue), delaySeconds, TimeUnit.SECONDS);
    }

    // Start writing to the queue after 3.5 seconds (so there are already 2 threads 
    // waiting), every 1 seconds (so that the queue fills faster than it's emptied, 
    // so that we see a full queue soon)
    for (int i = 0; i < 10; i++) {
      int element = i; // Assign to an effectively final variable
      int delayMillis = 3500 + i * 1000;
      pool.schedule(() -> enqueue(queue, element), delayMillis, TimeUnit.MILLISECONDS);
    }

    pool.shutdown();
    pool.awaitTermination(1, TimeUnit.MINUTES);
  }

  private static void enqueue(BlockingQueue<Integer> queue, int element) {
    log("Calling queue.put(%d) (queue = %s)...", element, queue);
    try {
      queue.put(element);
      log("queue.put(%d) returned (queue = %s)", element, queue);
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }

  private static void dequeue(BlockingQueue<Integer> queue) {
    log("    Calling queue.take() (queue = %s)...", queue);
    try {
      Integer element = queue.take();
      log("    queue.take() returned %d (queue = %s)", element, queue);
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }

  private static void log(String format, Object... args) {
    System.out.printf(
        Locale.US,
        "[%4.1fs] [%-16s] %s%n",
        (System.currentTimeMillis() - startTime) / 1000.0,
        Thread.currentThread().getName(),
        String.format(format, args));
  }
}Code language: Java (java)

Below you can see the output of the sample program:

[ 0.0s] [pool-1-thread-1 ]     Calling queue.take() (queue = [])...
[ 3.0s] [pool-1-thread-4 ]     Calling queue.take() (queue = [])...
[ 3.5s] [pool-1-thread-8 ] Calling queue.put(0) (queue = [])...
[ 3.5s] [pool-1-thread-1 ]     queue.take() returned 0 (queue = [])
[ 3.5s] [pool-1-thread-8 ] queue.put(0) returned (queue = [])
[ 4.5s] [pool-1-thread-5 ] Calling queue.put(1) (queue = [])...
[ 4.5s] [pool-1-thread-4 ]     queue.take() returned 1 (queue = [])
[ 4.5s] [pool-1-thread-5 ] queue.put(1) returned (queue = [])
[ 5.5s] [pool-1-thread-3 ] Calling queue.put(2) (queue = [])...
[ 5.5s] [pool-1-thread-3 ] queue.put(2) returned (queue = [2])
[ 6.0s] [pool-1-thread-7 ]     Calling queue.take() (queue = [2])...
[ 6.0s] [pool-1-thread-7 ]     queue.take() returned 2 (queue = [])
[ 6.5s] [pool-1-thread-9 ] Calling queue.put(3) (queue = [])...
[ 6.5s] [pool-1-thread-9 ] queue.put(3) returned (queue = [3])
[ 7.5s] [pool-1-thread-6 ] Calling queue.put(4) (queue = [3])...
[ 7.5s] [pool-1-thread-6 ] queue.put(4) returned (queue = [3, 4])
[ 8.5s] [pool-1-thread-2 ] Calling queue.put(5) (queue = [3, 4])...
[ 8.5s] [pool-1-thread-2 ] queue.put(5) returned (queue = [3, 4, 5])
[ 9.0s] [pool-1-thread-10]     Calling queue.take() (queue = [3, 4, 5])...
[ 9.0s] [pool-1-thread-10]     queue.take() returned 3 (queue = [4, 5])
[ 9.5s] [pool-1-thread-1 ] Calling queue.put(6) (queue = [4, 5])...
[ 9.5s] [pool-1-thread-1 ] queue.put(6) returned (queue = [4, 5, 6])
[10.5s] [pool-1-thread-8 ] Calling queue.put(7) (queue = [4, 5, 6])...
[11.5s] [pool-1-thread-4 ] Calling queue.put(8) (queue = [4, 5, 6])...
[12.0s] [pool-1-thread-5 ]     Calling queue.take() (queue = [4, 5, 6])...
[12.0s] [pool-1-thread-5 ]     queue.take() returned 4 (queue = [5, 6, 7])
[12.0s] [pool-1-thread-8 ] queue.put(7) returned (queue = [5, 6, 7])
[12.5s] [pool-1-thread-3 ] Calling queue.put(9) (queue = [5, 6, 7])...
[15.0s] [pool-1-thread-7 ]     Calling queue.take() (queue = [5, 6, 7])...
[15.0s] [pool-1-thread-7 ]     queue.take() returned 5 (queue = [6, 7, 8])
[15.0s] [pool-1-thread-4 ] queue.put(8) returned (queue = [6, 7, 8])
[18.0s] [pool-1-thread-9 ]     Calling queue.take() (queue = [6, 7, 8])...
[18.0s] [pool-1-thread-3 ] queue.put(9) returned (queue = [7, 8, 9])
[18.0s] [pool-1-thread-9 ]     queue.take() returned 6 (queue = [7, 8, 9])
[21.0s] [pool-1-thread-6 ]     Calling queue.take() (queue = [7, 8, 9])...
[21.0s] [pool-1-thread-6 ]     queue.take() returned 7 (queue = [8, 9])
[24.0s] [pool-1-thread-2 ]     Calling queue.take() (queue = [8, 9])...
[24.0s] [pool-1-thread-2 ]     queue.take() returned 8 (queue = [9])
[27.0s] [pool-1-thread-10]     Calling queue.take() (queue = [9])...
[27.0s] [pool-1-thread-10]     queue.take() returned 9 (queue = [])Code language: plaintext (plaintext)

Since we start writing only after two threads already call take(), these first two read attempts block at 0.0 and 3.0 s (threads 1 and 4).

After 3.5 s, the first element is written (thread 8). This wakes up thread 1, and the take() method immediately removes this element from the queue again.

After 4.5 s, the second element is written (thread 5). Thread 4 is woken up and takes this element from the queue again.

The program writes faster than it reads. After 10.5 s, a writing thread (thread 8) blocks for the first time when trying to write 7 into the queue, which is full at that time. After 11.5 s, thread 4 also blocks the attempt to write 8 into the queue.

After 12.0 s, thread 5 removes an element from the queue, which frees up space. Thread 8 is woken up and writes 7 into the queue.

See if you can read and understand the rest of the issues yourself.

Is LinkedBlockingQueue Thread-Safe?

Yes, LinkedBlockingQueue is thread-safe.

Thread safety of LinkedBlockingQueue is guaranteed by pessimistic locking using two separate ReentrantLocks for write and read operations. This prevents contention (access conflicts) between producer and consumer threads.

Differences from other queues:

• With ConcurrentLinkedQueue, thread safety is provided by optimistic locking via compare-and-set, resulting in better performance with low to moderate contention.
• ArrayBlockingQueue is protected with only one ReentrantLock, so access conflicts between producer and consumer threads are possible.

LinkedBlockingQueue Time Complexity

As with all queues, the time required for enqueue and dequeue operations is independent of the length of the queue. The time complexity is, therefore, O(1).

That also applies to the size() method. Unlike ConcurrentLinkedQueue, which is also based on a linked list and runs through the complete list to count the elements each time size() is called, LinkedBlockingQueue uses an AtomicInteger internally, which is updated on insertion and removal, and thus keeps the size available with constant time.

Summary and Outlook

In this article, you have learned about LinkedBlockingQueue – a thread-safe, blocking, bounded queue. You saw an example of how you can use LinkedBlockingQueue, and you also learned in which cases you should use it.

LinkedBlockingQueue is based on a linked list. The next part of the tutorial is about the array-based counterpart – ArrayBlockingQueue.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.

In this part of the tutorial series, I will introduce you to a queue that, strictly speaking, is not a queue at all: the PriorityQueue.

We are here in the class hierarchy:

What Is a Priority Queue?

A priority queue is not a queue in the classical sense. The reason is that the elements are not retrieved in FIFO order but according to their priority. The element with the highest priority is always taken first – regardless of when it was inserted into the queue.

The following example shows a priority queue with elements of priority 10 (highest priority), 20, etc., to 80 (lowest priority). Another element with priority 45 is inserted into the queue. The queue then automatically ensures that this element is removed after the element with priority 40 and before the element with priority 50.

Which Data Structure Is Used to Implement a Priority Queue?

Priority queues are usually implemented with a heap.

In the last part of this tutorial series, I will show you how to implement a priority queue using a heap yourself.

Java PriorityQueue Characteristics

With the java.util.PriorityQueue class, the dequeue order results either from the elements’ natural order¹ or according to a comparator¹ passed to the constructor. The underlying data structure is a min-heap, i.e., the smallest element is always at the head of the queue.

The sort order is not stable, i.e., two elements that are in the same position according to the sort order are not necessarily removed in the same order as they were inserted into the queue.

PriorityQueue is neither thread-safe nor blocking. A thread-safe, blocking counterpart is the PriorityBlockingQueue.

The queue’s characteristics are:

By the way, PriorityQueue does not violate the Liskov substitution principle (LSP). After all, the Queue interface’s documentation says: “Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner.”

¹ You can read all about the “natural order” of objects and sorting-by-comparator in the “Comparing Java Objects” article.

² Fail-fast: The iterator throws a ConcurrentModificationException if elements are added to or removed from the queue during iteration.

Recommended Use Case

You can use PriorityQueue when a non-thread-safe queue with a dequeue order as described above is required.

However, be aware that PriorityQueue is used in very few places in the JDK and, thus, there is a certain probability of the presence of bugs (what is little used is little tested).

PriorityQueue Example

The following example shows how to create a priority queue in Java and how to write several random numbers into the queue and then take them out again (→ code on GitHub).

We do not specify a comparator, i.e. the integer elements are sorted according to their natural order.

public class PriorityQueueExample {
  public static void main(String[] args) {
    Queue<Integer> queue = new PriorityQueue<>();

    // Enqueue random numbers
    for (int i = 0; i < 8; i++) {
      int element = ThreadLocalRandom.current().nextInt(100);
      queue.offer(element);
      System.out.printf("queue.offer(%2d)    -->  queue = %s%n", element, queue);
    }

    // Dequeue all elements
    while (!queue.isEmpty()) {
      Integer element = queue.poll();
      System.out.printf("queue.poll() = %2d  -->  queue = %s%n", element, queue);
    }
  }
}Code language: Java (java)

The following is an example output of the program:

queue.offer(80)    -->  queue = [80]
queue.offer(14)    -->  queue = [14, 80]
queue.offer(10)    -->  queue = [10, 80, 14]
queue.offer(50)    -->  queue = [10, 50, 14, 80]
queue.offer( 9)    -->  queue = [9, 10, 14, 80, 50]
queue.offer(58)    -->  queue = [9, 10, 14, 80, 50, 58]
queue.offer(41)    -->  queue = [9, 10, 14, 80, 50, 58, 41]
queue.offer( 1)    -->  queue = [1, 9, 14, 10, 50, 58, 41, 80]
queue.poll() =  1  -->  queue = [9, 10, 14, 80, 50, 58, 41]
queue.poll() =  9  -->  queue = [10, 41, 14, 80, 50, 58]
queue.poll() = 10  -->  queue = [14, 41, 58, 80, 50]
queue.poll() = 14  -->  queue = [41, 50, 58, 80]
queue.poll() = 41  -->  queue = [50, 80, 58]
queue.poll() = 50  -->  queue = [58, 80]
queue.poll() = 58  -->  queue = [80]
queue.poll() = 80  -->  queue = []Code language: plaintext (plaintext)

You can see clearly:

• how eight elements are inserted into the priority queue,
• how the elements in the priority queue are shown in supposedly random order (in fact, it is the array representation of the min-heap),
• that the smallest element is always at the head of the queue (left),
• how the elements are removed in ascending order.

PriorityQueue with a Comparator

In the previous example, we created a PriorityQueue using the default constructor. This causes the elements to be sorted according to their natural order.

However, we can also specify a custom comparator for the priority queue. In the following example, we create tasks with a name and a priority, and these tasks are to be retrieved sorted by priority.

We define the comparator for this simply as:

Comparator<Task> comparator = Comparator.comparing(Task::name);Code language: Java (java)

If you are not familiar with this notation – it creates a comparator that sorts tasks by priority. This notation is much more readable than the following comparator defined with a lambda:

Comparator<Task> comparator =
    (task1, task2) -> Integer.compare(task1.priority(), task2.priority());Code language: Java (java)

Here is the full example code (PriorityQueueWithCustomComparatorExample class on GitHub):

public class PriorityQueueWithCustomComparatorExample {
  public static void main(String[] args) {
    Comparator<Task> comparator = Comparator.comparingInt(Task::priority);
    Queue<Task> queue = new PriorityQueue<>(comparator);

    // Enqueue tasks with random priorities
    for (int i = 0; i < 5; i++) {
      String name = "Task " + (i + 1);
      int priority = ThreadLocalRandom.current().nextInt(10, 100);
      Task task = new Task(name, priority);
      queue.offer(task);
      System.out.printf("queue.offer(%s)    -->  queue = %s%n", task, queue);
    }

    // Dequeue all elements
    while (!queue.isEmpty()) {
      System.out.printf("queue.poll() = %s  -->  queue = %s%n", queue.poll(), queue);
    }
  }

  private record Task(String name, int priority) {
    @Override
    public String toString() {
      return name + " (prio " + priority + ")";
    }
  }
}Code language: Java (java)

An example output looks as follows:

queue.offer(Task 1 (prio 93))    -->  queue = [Task 1 (prio 93)]
queue.offer(Task 2 (prio 76))    -->  queue = [Task 2 (prio 76), Task 1 (prio 93)]
queue.offer(Task 3 (prio 92))    -->  queue = [Task 2 (prio 76), Task 1 (prio 93), Task 3 (prio 92)]
queue.offer(Task 4 (prio 51))    -->  queue = [Task 4 (prio 51), Task 2 (prio 76), Task 3 (prio 92), Task 1 (prio 93)]
queue.offer(Task 5 (prio 35))    -->  queue = [Task 5 (prio 35), Task 4 (prio 51), Task 3 (prio 92), Task 1 (prio 93), Task 2 (prio 76)]
queue.poll() = Task 5 (prio 35)  -->  queue = [Task 4 (prio 51), Task 2 (prio 76), Task 3 (prio 92), Task 1 (prio 93)]
queue.poll() = Task 4 (prio 51)  -->  queue = [Task 2 (prio 76), Task 1 (prio 93), Task 3 (prio 92)]
queue.poll() = Task 2 (prio 76)  -->  queue = [Task 3 (prio 92), Task 1 (prio 93)]
queue.poll() = Task 3 (prio 92)  -->  queue = [Task 1 (prio 93)]
queue.poll() = Task 1 (prio 93)  -->  queue = []
Code language: plaintext (plaintext)

We can clearly see how the tasks are taken according to priority (priority 51 first, priority 93 last).

To retrieve the tasks sorted alphabetically by name, we would only need to change the comparator to:

Comparator<Task> comparator = Comparator.comparing(Task::name);Code language: Java (java)

PriorityQueue Time Complexity

The time required for enqueue and dequeue operations in the Java PriorityQueue is equal to the time required to insert and extract from a heap.

Thus, the time complexity for both operations is: O(n log n)

By using a heap, the element with the highest priority is always automatically at the head of the queue and can be taken out in constant time.

Thus, the time complexity for the peek operation is: O(1)

(Here, you can find an introduction to time complexity.)

Summary and Outlook

This article has explained what a priority queue is in general, the characteristics of the Java PriorityQueue, when to use it, how to specify the dequeue order with a custom comparator, and the time complexities of the priority queue operations are.

In the following article, we come to the first blocking queue: LinkedBlockingQueue.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.

In this article, you will learn everything about ConcurrentLinkedQueue, its characteristics and usage scenarios. An example will show you how to use ConcurrentLinkedQueue.

Here we are in the class hierarchy:

ConcurrentLinkedQueue Characteristics

The class java.util.concurrent.ConcurrentLinkedQueue is based on a singly linked list and is – like most queue implementations – thread-safe (see below).

(The only non-thread-safe queue is PriorityQueue – and the deques ArrayDeque and LinkedList, which also implement the Queue interface. More about this in the next tutorial series on “Deques”.)

Since the length of a linked list is difficult to determine, ConcurrentLinkedQueue is unbounded. ConcurrentLinkedQueue also does not provide blocking operations.

The characteristics in detail:

¹ Weakly consistent: All elements that exist when the iterator is created are traversed by the iterator exactly once. Changes that occur after this can, but do not need to, be reflected by the iterator.

Recommended Use Case

ConcurrentLinkedQueue is a good choice when a thread-safe, non-blocking, unbounded queue is needed.

This applies despite my general recommendation to prefer array-based data structures over those implemented with linked lists.

Array-based alternatives are:

• The ArrayDeque described in the following tutorial about deques – this is, however, not thread-safe.
• The ArrayBlockingQueue described later in this tutorial – firstly, it is bounded, and secondly, it implements thread safety via a single ReentrantLock. This is, for most use cases (with low to medium contention), less performant than optimistic locking.

ConcurrentLinkedQueue Example

The following example demonstrates the thread safety of ConcurrentLinkedDeque. Four writing and three reading threads concurrently add and remove elements from the queue (→ code on GitHub):

public class ConcurrentLinkedQueueExample {

  private static final int NUMBER_OF_PRODUCERS = 4;
  private static final int NUMBER_OF_CONSUMERS = 3;
  private static final int NUMBER_OF_ELEMENTS_TO_PUT_INTO_QUEUE_PER_THREAD = 5;
  private static final int MIN_SLEEP_TIME_MILLIS = 500;
  private static final int MAX_SLEEP_TIME_MILLIS = 2000;

  private static final int POISON_PILL = -1;

  public static void main(String[] args) throws InterruptedException {
    Queue<Integer> queue = new ConcurrentLinkedQueue<>();

    // Start producers
    CountDownLatch producerFinishLatch = new CountDownLatch(NUMBER_OF_PRODUCERS);
    for (int i = 0; i < NUMBER_OF_PRODUCERS; i++) {
      createProducerThread(queue, producerFinishLatch).start();
    }

    // Start consumers
    for (int i = 0; i < NUMBER_OF_CONSUMERS; i++) {
      createConsumerThread(queue).start();
    }

    // Wait until all producers are finished
    producerFinishLatch.await();

    // Put poison pills on the queue (one for each consumer)
    for (int i = 0; i < NUMBER_OF_CONSUMERS; i++) {
      queue.offer(POISON_PILL);
    }

    // We'll let the program end when all consumers are finished
  }

  private static Thread createProducerThread(
      Queue<Integer> queue, CountDownLatch finishLatch) {
    return new Thread(
        () -> {
          ThreadLocalRandom random = ThreadLocalRandom.current();
          for (int i = 0; i < NUMBER_OF_ELEMENTS_TO_PUT_INTO_QUEUE_PER_THREAD; i++) {
            sleepRandomTime();

            Integer element = random.nextInt(1000);
            queue.offer(element);
            System.out.printf(
                "[%s] queue.offer(%3d)        --> queue = %s%n",
                Thread.currentThread().getName(), element, queue);
          }

          finishLatch.countDown();
        });
  }

  private static Thread createConsumerThread(Queue<Integer> queue) {
    return new Thread(
        () -> {
          while (true) {
            sleepRandomTime();

            Integer element = queue.poll();
            System.out.printf(
                "[%s]     queue.poll() = %4d --> queue = %s%n",
                Thread.currentThread().getName(), element, queue);

            // End the thread when a poison pill is detected
            if (element != null && element == POISON_PILL) {
              break;
            }
          }
        });
  }

  private static void sleepRandomTime() {
    ThreadLocalRandom random = ThreadLocalRandom.current();
    try {
      Thread.sleep(random.nextInt(MIN_SLEEP_TIME_MILLIS, MAX_SLEEP_TIME_MILLIS));
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }
}

Code language: Java (java)

Here are the first ten lines of an exemplary output:

[Thread-1] queue.offer(982)        --> queue = [982]
[Thread-6]     queue.poll() =  982 --> queue = []
[Thread-5]     queue.poll() = null --> queue = []
[Thread-0] queue.offer(917)        --> queue = [917]
[Thread-3] queue.offer(224)        --> queue = [917, 224]
[Thread-2] queue.offer(932)        --> queue = [917, 224, 932]
[Thread-6]     queue.poll() =  917 --> queue = [224, 932]
[Thread-4]     queue.poll() =  224 --> queue = [932]
[Thread-5]     queue.poll() =  932 --> queue = []
[Thread-0] queue.offer(607)        --> queue = [607]
[Thread-1] queue.offer( 87)        --> queue = [607, 87]
[Thread-3] queue.offer(264)        --> queue = [607, 87, 264]
[Thread-4]     queue.poll() =  607 --> queue = [87, 264]
[Thread-0] queue.offer(348)        --> queue = [87, 264, 348]
[Thread-2] queue.offer(728)        --> queue = [87, 264, 348, 728]
Code language: plaintext (plaintext)

We can see very nicely how the seven threads insert and remove elements. In the third line, we see that thread 5 received null from the call to queue.poll() because the queue was empty at that time.

ConcurrentLinkedQueue Performance

This section discusses thread the safety and time complexity of ConcurrentLinkedQueue.

Ist ConcurrentLinkedQueue Thread-Safe?

The thread-safety of ConcurrentLinkedQueue is achieved by optimistic locking. More precisely: by non-blocking compare-and-set (CAS) operations on separate VarHandles for the queue’s head and tail.

When accessing queues, low to moderate contention (access conflicts due to multiple threads) is usually to be expected. A thread usually does not access the queue continuously but must first create the element to be set or process the element to be taken.

With low to moderate contention, optimistic locking achieves a significant performance gain over pessimistic locking through implicit or explicit locks.

Differences from other queues:

• With LinkedBlockingQueue, thread safety is provided by pessimistic locking via two ReentrantLocks, leading to better performance with high contention.
• With ArrayBlockingQueue, thread safety is provided by a single ReentrantLock.

ConcurrentLinkedQueue Time Complexity

As with all queues, the overhead for the enqueue and dequeue operations is independent of the queue length. The time complexity is, therefore, O(1).

However, this does not apply to the size() method. To determine the length of the queue, you must iterate over all elements of the linked list. The longer the queue, the longer it takes to calculate the length. Therefore, the time complexity for size() is O(n).

(Here, you can find an introduction to the topic of time complexity.)

Summary and Outlook

In this part of the tutorial series, I introduced you to the concrete Queue implementation ConcurrentLinkedQueue and its characteristics.

The following part will be about the PriorityQueue, which has some surprises in store.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.

In this article, you will learn about the java.util.concurrent.BlockingQueue interface. BlockingQueue extends Java’s Queue interface discussed in the previous part of this tutorial series with methods for blocking access.

Before we clarify what “blocking access” means, we first need to talk about the term “bounded queue”.

What Is a Bounded Queue?

If a queue can only hold a limited number of elements, it is referred to as a “bounded queue”. The maximum number of elements is referred to as “capacity” and is specified when the queue is created.

For example, the following line of code creates an ArrayBlockingQueue limited to 100 elements:

Queue<Integer> queue = new ArrayBlockingQueue<>(100);Code language: Java (java)

IOn the other hand, if the number of elements in the queue is not limited (or is limited only by the available memory), we speak of an “unbounded queue”.

(By the way, the same definition applies to all data structures, e.g., also to stacks and deques.)

What Is a Blocking Queue?

Two special cases can occur with the “Enqueue” and “Dequeue” queue operations:

• We could try to insert an element into a bounded queue that has reached its capacity limit – in other words, that is full.
• We could try to take an element from an empty queue.

A non-blocking queue returns a specific return value or throws an exception in such cases (see section “Queue Methods” in the article about Java queues).

A blocking queue, on the other hand, provides additional methods that wait for the desired operation to be executed:

• Enqueue methods that, when inserting into a full bounded queue, wait until the queue has free capacity again (this requires another thread to take an element).
• Dequeue methods that, when taking an element from an empty queue, wait for the queue to become non-empty (this requires another thread to insert an element).

These additional methods are defined in the BlockingQueue interface. I will explain them in the following chapter.

Fairness Policy

Blocking methods are not automatically processed in the order they were called. You can activate the processing in call order in some queue implementations through an optional “fairness policy”. However, this increases the overhead and thus massively reduces the throughput of the queue. As a rule, it is not necessary to activate the fairness policy.

BlockingQueue Interface

The blocking enqueue and dequeue operations each come in two variants. The first variant waits indefinitely. The second variant gives up after a specified waiting time and returns false or null.

In the first two columns, the following table shows the non-blocking methods that BlockingQueue inherits from Queue (and that we discussed in the previous part of the tutorial). In the third and fourth columns, you will find the added blocking methods:

The following section describes the BlockingQueue methods in detail.

BlockingQueue Methods

BlockingQueue.put()

The put() method inserts an element into the queue if space is available. However, if the queue’s capacity limit is reached, the method blocks until space is freed.

BlockingQueue.offer() with Timeout

Also, the offer() method inserts an element if there is still space in the queue. Otherwise, the method waits for the specified time. If a space becomes available during this time, the element is inserted, and the method returns true. If, on the other hand, the waiting time expires without any space being freed, the method returns false.

BlockingQueue.take()

This method takes an element from the head of the queue, provided the queue is not empty. If the queue is empty, take() blocks until an element becomes available and then returns it.

BlockingQueue.poll() with Timeout

Also, poll() takes an element from the queue’s head if the queue is not empty. If the queue is empty, the method waits for the specified time. If an element becomes available during the waiting time, it is returned. If the wait time expires without result, the method returns null.

InterruptedException for Blocking Methods

All blocking methods throw an InterruptedException when the interrupt() method is called on the waiting thread. With interrupt(), blocked threads should be terminated when waiting is no longer necessary.

This is the case, for example, when the application is being shut down. In this case, the event for which the blocking method is waiting may no longer occur. However, the method would still wait for the event to occur and thus prevent a regular shutdown of the application. Canceling the waiting threads with interrupt() allows a clean shutdown.

Java BlockingQueue Example

The following source code shows an example that is significantly more complex than the example with a non-blocking queue due to concurrency (→ Code on GitHub):

public class BlockingQueueExample {
  private static final long startTime = System.currentTimeMillis();

  public static void main(String[] args) throws InterruptedException {
    BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(3);
    ScheduledExecutorService pool = Executors.newScheduledThreadPool(10);

    // Start reading from the queue immediately, every 3 seconds
    for (int i = 0; i < 10; i++) {
      int delaySeconds = i * 3;
      pool.schedule(() -> dequeue(queue), delaySeconds, TimeUnit.SECONDS);
    }

    // Start writing to the queue after 3.5 seconds (so there are already 2
    // threads waiting), every 1 seconds (so that the queue fills faster than
    // it's emptied, so that we see a full queue soon)
    for (int i = 0; i < 10; i++) {
      int element = i; // Assign to an effectively final variable
      int delayMillis = 3500 + i * 1000;
      pool.schedule(() -> enqueue(queue, element), delayMillis, TimeUnit.MILLISECONDS);
    }

    pool.shutdown();
    pool.awaitTermination(1, TimeUnit.MINUTES);
  }

  private static void enqueue(BlockingQueue<Integer> queue, int element) {
    log("Calling queue.put(%d) (queue = %s)...", element, queue);
    try {
      queue.put(element);
      log("queue.put(%d) returned (queue = %s)", element, queue);
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }

  private static void dequeue(BlockingQueue<Integer> queue) {
    log("    Calling queue.take() (queue = %s)...", queue);
    try {
      Integer element = queue.take();
      log("    queue.take() returned %d (queue = %s)", element, queue);
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }

  private static void log(String format, Object... args) {
    System.out.printf(
        Locale.US,
        "[%4.1fs] [%-16s] %s%n",
        (System.currentTimeMillis() - startTime) / 1000.0,
        Thread.currentThread().getName(),
        String.format(format, args));
  }
}Code language: Java (java)

In this example, we create a blocking, bounded queue with a capacity of 3 and schedule ten enqueue and ten dequeue operations each.

The enqueue operations start later, so we can see blocking dequeue operations at the beginning. Also, the enqueue operations happen in shorter intervals so that the queue’s capacity limit is reached after a while, and we can see blocking enqueue operations.

Here is the output of the program:

[ 0.0s] [pool-1-thread-1 ]     Calling queue.take() (queue = [])...
[ 3.0s] [pool-1-thread-3 ]     Calling queue.take() (queue = [])...
[ 3.5s] [pool-1-thread-2 ] Calling queue.put(0) (queue = [])...
[ 3.5s] [pool-1-thread-2 ] queue.put(0) returned (queue = [])
[ 3.5s] [pool-1-thread-1 ]     queue.take() returned 0 (queue = [])
[ 4.5s] [pool-1-thread-10] Calling queue.put(1) (queue = [])...
[ 4.5s] [pool-1-thread-10] queue.put(1) returned (queue = [])
[ 4.5s] [pool-1-thread-3 ]     queue.take() returned 1 (queue = [])
[ 5.5s] [pool-1-thread-8 ] Calling queue.put(2) (queue = [])...
[ 5.5s] [pool-1-thread-8 ] queue.put(2) returned (queue = [2])
[ 6.0s] [pool-1-thread-9 ]     Calling queue.take() (queue = [2])...
[ 6.0s] [pool-1-thread-9 ]     queue.take() returned 2 (queue = [])
[ 6.5s] [pool-1-thread-5 ] Calling queue.put(3) (queue = [])...
[ 6.5s] [pool-1-thread-5 ] queue.put(3) returned (queue = [3])
[ 7.5s] [pool-1-thread-6 ] Calling queue.put(4) (queue = [3])...
[ 7.5s] [pool-1-thread-6 ] queue.put(4) returned (queue = [3, 4])
[ 8.5s] [pool-1-thread-7 ] Calling queue.put(5) (queue = [3, 4])...
[ 8.5s] [pool-1-thread-7 ] queue.put(5) returned (queue = [3, 4, 5])
[ 9.0s] [pool-1-thread-4 ]     Calling queue.take() (queue = [3, 4, 5])...
[ 9.0s] [pool-1-thread-4 ]     queue.take() returned 3 (queue = [4, 5])
[ 9.5s] [pool-1-thread-2 ] Calling queue.put(6) (queue = [4, 5])...
[ 9.5s] [pool-1-thread-2 ] queue.put(6) returned (queue = [4, 5, 6])
[10.5s] [pool-1-thread-1 ] Calling queue.put(7) (queue = [4, 5, 6])...
[11.5s] [pool-1-thread-10] Calling queue.put(8) (queue = [4, 5, 6])...
[12.0s] [pool-1-thread-3 ]     Calling queue.take() (queue = [4, 5, 6])...
[12.0s] [pool-1-thread-3 ]     queue.take() returned 4 (queue = [5, 6, 7])
[12.0s] [pool-1-thread-1 ] queue.put(7) returned (queue = [5, 6, 7])
[12.5s] [pool-1-thread-8 ] Calling queue.put(9) (queue = [5, 6, 7])...
[15.0s] [pool-1-thread-9 ]     Calling queue.take() (queue = [5, 6, 7])...
[15.0s] [pool-1-thread-9 ]     queue.take() returned 5 (queue = [6, 7, 8])
[15.0s] [pool-1-thread-10] queue.put(8) returned (queue = [6, 7, 8])
[18.0s] [pool-1-thread-5 ]     Calling queue.take() (queue = [6, 7, 8])...
[18.0s] [pool-1-thread-5 ]     queue.take() returned 6 (queue = [7, 8, 9])
[18.0s] [pool-1-thread-8 ] queue.put(9) returned (queue = [7, 8, 9])
[21.0s] [pool-1-thread-6 ]     Calling queue.take() (queue = [7, 8, 9])...
[21.0s] [pool-1-thread-6 ]     queue.take() returned 7 (queue = [8, 9])
[24.0s] [pool-1-thread-7 ]     Calling queue.take() (queue = [8, 9])...
[24.0s] [pool-1-thread-7 ]     queue.take() returned 8 (queue = [9])
[27.0s] [pool-1-thread-4 ]     Calling queue.take() (queue = [9])...
[27.0s] [pool-1-thread-4 ]     queue.take() returned 9 (queue = [])Code language: plaintext (plaintext)

In the beginning, the queue is empty, so the first two read attempts block (after 0 and 3 s).

After 3.5 s (after two reading threads are waiting at the queue), the program starts writing to the queue every second. The output shows nicely how a reading thread is woken up in each case and immediately removes the attached element again (at 3.5 and 4.5 s).

Since the program writes to the queue three times as fast as it reads from it, the attempt to write a 7 to the queue blocks after 10.5 s since the queue has reached its capacity limit of 3 with the elements [4, 5, 6].

Only after the 4 has been removed from the queue after 12 s, the 7 can be inserted. For the 8 and the 9, we see a corresponding behavior.

BlockingQueue Implementations

There are five implementations of the BlockingQueue interface in the JDK, each with specific characteristics. In the following UML class diagram, I’ve highlighted them together with their interface:

I will discuss each of the implementations in separate articles in the tutorial. There, I’ll present their characteristics and explain, on their basis, under which conditions you should use the respective implementation. The following links lead to the corresponding articles:

• LinkedBlockingQueue
• ArrayBlockingQueue
• PriorityBlockingQueue
• DelayQueue
• SynchronousQueue

You can also access these articles at any time via the tutorial navigation in the right margin.

Summary and Outlook

This article first explained the differences between bounded/unbounded and blocking/non-blocking queues. After that, you learned about the BlockingQueue interface and its methods put(), offer(), take(), and poll().

In the following parts of this series, we will look at all Queue and BlockingQueue implementations and their characteristics.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.

Since Java 5.0, the JDK contains the interface java.util.Queue and several queue implementations, which differ in various properties (bounded/unbounded, blocking/non-blocking, thread-safe/non-thread-safe).

I will discuss all of these characteristics in the remaining part of this tutorial.

Java Queue Class Hierarchy

Before I present the Java queue in detail, I would like to give an overview in the form of a UML class diagram:

I will describe the BlockingQueue interface in the next part of the tutorial.

The concrete queue classes ConcurrentLinkedQueue, PriorityQueue, ArrayBlockingQueue, DelayQueue, LinkedBlockingQueue, PriorityBlockingQueue, and SynchronousQueue follow. Finally, I will explain the TransferQueue interface together with the LinkedTransferQueue.

You can jump to the corresponding parts at any time using the tutorial navigation on the right margin.

The grayed-out interfaces Deque and BlockingDeque and their implementations are covered in the tutorial series on deques.

Java Queue Methods

The Queue interface defines six methods for inserting, removing, and viewing elements. For each of the three queue operations “Enqueue”, “Dequeue”, and “Peek”, the interface defines two methods: one that throws an exception in case of an error and one that returns a special value (false or null).

Methods for Inserting into the Queue

First, a graphical overview of the enqueue methods:

Queue.add()

This method is already defined in the Collection interface and inserts an element into the queue. On success, the method returns true. If a bounded (size-restricted) queue is full, this method throws an IllegalStateException.

Queue.offer()

offer(), like add(), adds an element to the queue and returns true on success. If a bounded queue is full, this method returns false instead of throwing an IllegalStateException.

Methods for Removing from the Queue

Also for the dequeue methods, first a graphical overview:

Queue.remove()

remove() removes the element from the queue’s head. If the queue is empty, the method throws a NoSuchElementException.

Queue.poll()

poll(), too, removes the element at the head of the queue. Unlike remove(), the method does not throw an exception if the queue is empty but returns null.

Methods for Viewing the Head Element

And again, first an overview of methods:

Queue.element()

The element() method returns the element from the head of the queue without removing it from the queue. If the queue is empty, a NoSuchElementException is thrown.

Queue.peek()

Like element(), peek() also returns the head element without removing it from the queue. However, if the queue is empty, this method returns null, just like poll().

Queue Methods – Summary

The following table shows the six methods again grouped by operation and type of error handling:

How to Create a Queue?

java.util.Queue is an interface. An interface cannot be instantiated because it only describes what methods a class offers but does not contain implementations of those methods.

What happens if you still try?

public class QueueTest {
  public static void main(String[] args) {
    Queue<Integer> queue = new Queue<>(); // <-- Don't do this!
  }
}Code language: Java (java)

When trying to compile this code, you would see the following error message:

QueueTest.java:5: error: Queue is abstract; cannot be instantiated
    Queue<Integer> queue = new Queue<>(); // <-- Don't do this!
                           ^
1 errorCode language: plaintext (plaintext)

Therefore, you must select one of the concrete queue implementations, e.g., ConcurrentLinkedQueue:

Queue<Integer> queue = new ConcurrentLinkedQueue<>();Code language: Java (java)

(I will explain the different queue classes in later parts of this tutorial. In the last part, you will find a decision guide on when to use which implementation.)

Example: How to Use a Queue?

The following example shows how to create a queue, fill it with some values, and retrieve the values. You can also find the example code on GitHub.

public class JavaQueueDemo {
  public static void main(String[] args) {
    // 1.
    Queue<Integer> queue = new ConcurrentLinkedQueue<>();

    // 2.
    for (int i = 1; i <= 5; i++) {
      queue.offer(i);
      System.out.println("queue.offer(" + i + ") --> queue = " + queue);
    }

    System.out.println();

    // 3.
    System.out.println("queue.peek() = " + queue.peek());

    System.out.println();

    // 4.
    while (!queue.isEmpty()) {
      System.out.println("queue.poll() = " + queue.poll() + " --> queue = " + queue);
    }

    System.out.println();

    // 5.
    System.out.println("queue.poll() = " + queue.poll());
    System.out.println("queue.peek() = " + queue.peek());
  }
}
Code language: Java (java)

The program does the following (the numbering refers to the comments in the source code):

1. It creates a queue. Which one you use is irrelevant for this example since it doesn’t require any special queue properties. We will use ConcurrentLinkedQueue.
2. Using Queue.offer(), we write the values 1 to 5 to the queue. And we display the queue’s content after each insertion.
3. We look at the queue’s head element using Queue.peek().
4. As long as the queue contains elements (we check this with the isEmpty() method, which the Queue interface inherits from Collection), we retrieve these elements with Queue.poll() and display them. After that, we show the entire content of the queue again.
5. After the queue has been emptied, we once again display the return values of poll() and peek().

The program prints the following:

queue.offer(1) --> queue = [1]
queue.offer(2) --> queue = [1, 2]
queue.offer(3) --> queue = [1, 2, 3]
queue.offer(4) --> queue = [1, 2, 3, 4]
queue.offer(5) --> queue = [1, 2, 3, 4, 5]

queue.peek() = 1

queue.poll() = 1 --> queue = [2, 3, 4, 5]
queue.poll() = 2 --> queue = [3, 4, 5]
queue.poll() = 3 --> queue = [4, 5]
queue.poll() = 4 --> queue = [5]
queue.poll() = 5 --> queue = []

queue.poll() = null
queue.peek() = nullCode language: plaintext (plaintext)

You can see very nicely how the elements are taken out in the same order as they were inserted (First-in-first-out – FIFO).

Summary and Outlook

In this part of the tutorial, you have learned about Java’s Queue interface. Using an example, you have seen how to use the queue.

In the next part, we will look at the BlockingQueue interface. I will also explain the difference between bounded and unbounded or blocking and non-blocking queues.

After that, we will look at all of the JDK’s queue implementations individually. Based on their unique characteristics, I will explain when to use which implementation.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.

In this tutorial, you will learn everything about the abstract data type “queue”:

• How does a queue work?
• What are the applications for queues?
• Which queue interfaces and classes are available in the JDK?
• What are blocking, non-blocking, bounded, and unbounded queues?
• How to implement a queue in Java?

What Is a Queue?

A queue is a list of elements where the elements are inserted on one side and taken out in the same order on the other side.

You can think of it as a queue at checkout or a government office:

Arriving customers queue up at the end of the line (right in the picture). Once a customer has been processed, the next customer from the head of the queue (left) takes their turn.

Therefore, the person who has queued first also gets the first turn. That is why we speak of the first-in-first-out (FIFO) principle.

Fifo Principle for Queues

With the abstract data type “queue”, this can look like the following example:

The graphic shows a queue containing the elements 6, 7, 8, etc., to 13. The 5 has just been taken from the front of the queue (also called “head”, on the left of the picture). And the 14 was just inserted at the back of the queue (also called “tail” or “rear”, on the right of the picture).

Queue Operations: Enqueue and Dequeue

We refer to the queue’s operations as follows:

• “Enqueue”: Inserting new elements at the back of the queue
• “Dequeue”: Removing elements from the head of the queue
• “Peek” or “Front”: Viewing the element at the head without removing it (optional)

(By the way, the corresponding methods of the Java queue implementations are called differently; more about this in the next part of the tutorial, “Java Queue Interface“.)

Applications for Queues

One application area of queues we all know is the printer queue. Various programs place print jobs there, and usually, there is only one printer, which then processes the jobs one after the other.

A technical application example is the processing of HTTP requests in a web server. A web server usually works with a thread pool for processing requests simultaneously. If more requests come in than can be processed at the same time, the thread pool is at capacity. Additional requests are then queued and processed in first-in-first-out order as soon as more threads are available.

Time Complexity of Queue Operations

You can find an introduction to time complexity in the article “Big O Notation and Time Complexity – Easily Explained“.

Queues are usually implemented with arrays or linked lists. In both variants, the overhead for the enqueue and dequeue operations is constant, i.e., the overhead does not change with the length of the queue.

Therefore, the time complexity of these operations is O(1).

For practice purposes, you can also implement a queue with stacks (more on this in a later part of the tutorial). However, the time complexity is then higher.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.