How do you pronounce deque

Java Queue, Deque and Stack: Ultimate Guide

Sooner or later Java developers have to deal with the data structures queue, deque and stack. This article explains the basic functions of these data structures and gives a detailed overview of all implementations available in the JDK. Numerous code examples should make it easier for you to understand.

The following questions are answered in detail:

  • How do the data structures queue, deque and stack work in general?
  • How are they different?
  • What does "bounded" or "unbounded" mean?
  • What does "blocking" or "non-blocking" mean?
  • What are the advantages of array-based implementations over linked lists?
  • Which queue, deque and stack implementations are there in the JDK?
  • Which of the numerous implementations are suitable for which purposes?
  • What are MPMC, MPSC, SPMC, SPSC Queues?

As always, you can find the code examples in my GitHub repository.

Data structures: what are queues, deques and stacks?

In this chapter I describe the general functionality of queues, deques and stacks. General means: independent of a specific programming language.

What is a queue?

A queue is a list of elements in which the elements are inserted on one side and removed in the same order on the other side:

A queue offers the following operations:

  • "Enqueue": Attachment of elements to the end ("back", "tail") of the queue
  • "Dequeue": Removing elements from the beginning ("front", "head") of the queue

(The corresponding methods of the Java queue implementations, however, have a different name, as you will see below.)

Since the order of the elements is retained, one also speaks of FIFO-List ("first-in-first-out").

What is a stack?

A stack is a list of elements in which the elements are inserted ("stacked") and again on the same page (in representations classically above) and again can be taken from:

The operations of the stack are:

  • "Push": adding elements to the stack
  • "Pop": Removing items from the top of the stack

Since the element that was added last is the first to be removed, one speaks of a LIFO-List ("last-in-first-out").

What is a deque?

A deque (D.ouble-ended queue, pronounced "deck" - there is no German translation) is a list of elements in which the elements can be inserted and removed on one side as well as on the other:

The operations are analogous to the queue on both sides "Enqueue" and "Dequeue":

  • "Enqueue at front": adding elements to the beginning of the deque
  • "Enqueue at back": adding elements to the end of the deque
  • "Dequeue at front": Removal of elements from the beginning of the deque
  • "Dequeue at back": removing elements from the end of the dequeue

(As with the queue, the corresponding methods of the Java implementations have different names for the deque, more on this below.)

A deque can be used both as a queue (FIFO) and as a stack (LIFO). It is not limited to this, however, as elements can be attached to and removed from any page at any time.

What is a bounded queue or an unbounded queue?

If a queue can only hold a limited number of elements, it is called a "bounded queue". The maximum number of elements is referred to as "capacity" and is set once via the constructor of the queue.

If the number of elements in the queue is not limited (or only by the available memory), one speaks of an "unbounded queue".

The same definition applies to deques and stacks.

What is a blocking queue or a non-blocking queue?

The following special cases can occur with the queue operations presented:

  • Insertion of an element into a bounded queue that has reached its capacity limit - or in other words: that is full.
  • Removing an element from an empty queue.

Depending on the implementation (more on this later), a non-blocking queue is returned with a certain return value (or) or an exception is thrown.

A blocking queue also offers the following blocking operations:

  • A method that, when inserted into a full bounded queue, waits until space has been freed by removing an element (by another thread).
  • A method that, when trying to remove an element from an empty queue, waits for an element to be inserted (by another thread).

Blocking methods are not automatically served in the order in which they were called. In some queue implementations, processing in the call sequence can be activated by an optional "fairness policy". However, this increases the overhead and thus reduces the throughput of the queue.

This definition also applies analogously to deques and stacks.

UML diagram: Java Queue, Deque, BlockingQueue, BlockingDeque

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

I will describe the interfaces in the following chapters and explain them using code examples.

Queues in Java

Since Java 5.0, the JDK contains the interface and several queue implementations that differ in various properties (such as bounded / unbounded, blocking / non-blocking, thread-safe / not thread-safe).

Queue interface

The interface (→ Javadoc) inherits from and extends it with methods to append and remove elements and to view the element at the head of the queue without removing it.

There are two methods for each of the three operations, which differ only in the way they handle errors: one method throws an exception in the event of an error, the other supplies a specific return value (or). Errors can occur, for example, when a bounded queue is full, or when an attempt is made to take an element from an empty queue.

Java Queue example

Here is a simple example (→ code in GitHub):

The program adds elements 1, 2 and 3 to the queue with, then outputs the first element with and then removes all elements with it. After all elements have been removed, it is called again and then.

The program outputs the following:

queue = [1, 2, 3] queue.peek () = 1 queue.poll () = 1 queue.poll () = 2 queue.poll () = 3 queue.poll () = null exception in thread "main" java.util.NoSuchElementException at [...]

As you can see, the elements are output in FIFO order, which is the same order in which they were inserted. You can also see the difference between and: While an empty queue returns the value, one throws.

Correspondingly, an empty queue would be returned and one would be thrown.

BlockingQueue Interface

The interface (→ Javadoc), which has also been available since Java 5.0, has been expanded to include additional blocking operations that wait for an element to be available when an element is removed from an empty queue or wait for free space when an element is inserted into a full queue is available.

There are two variants of both operations. One that waits indefinitely and one that gives up and / or returns after a specified waiting time has elapsed. There are no blocking methods that throw exceptions.

Java BlockingQueue example

Here is an example, which is significantly more complex than the first example due to the concurrency (→ Code in GitHub):

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 see blocking dequeue operations at the beginning. In addition, the enqueue operations take place at short intervals, so that the capacity limit of the queue is reached after a while and we 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-thre ad-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 = [])

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

After 3.5 s (after two reading threads are waiting in the queue) the program starts to write to the queue every second. You can see in the output how a reading thread is continued and the attached element is removed again immediately (at 3.5 and 4.5 s).

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

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

Deques in Java

The interface and various deque implementations were included in JDK 6.0. Like the queue implementations, these differ in terms of their properties bounded/unbounded, blocking/non-blocking and thread safe/not thread safe.

Deque interface

The interface (→ JavaDoc) inherits from and extends it with methods, with elements on the Beginning to append elements to the queue end from the queue and the element on end look at the queue without removing it.

These methods also differ in whether they throw an exception in the event of an error or supply a special return value.

For reasons of consistency, the operations that inherits from have been implemented again with a new name (for example, as and as). You can recognize these cases by the fact that two method names are given in the following table.

Java Deque example

Here is a code example that produces exactly the deque that was graphically displayed at the beginning of the article (→ code in GitHub):

The program fills the deque with several calls to and, issues it and then alternately removes elements from both sides until the deque is empty.

This is the output of the program:

dequeue = [27, 26, 22, 21, 20, 23, 24, 25] dequeue.offerLast (28) = true dequeue.offerFirst (29) = true dequeue = [29, 27, 26, 22, 21, 20, 23, 24, 25, 28] dequeue.pollFirst () = 29 dequeue.pollLast () = 28 dequeue = [27, 26, 22, 21, 20, 23, 24, 25] dequeue.pollFirst () = 27 dequeue. pollLast () = 25 dequeue = [26, 22, 21, 20, 23, 24] dequeue.pollFirst () = 26 dequeue.pollLast () = 24 dequeue = [22, 21, 20, 23] dequeue.pollFirst () = 22 dequeue.pollLast () = 23 dequeue = [21, 20] dequeue.pollFirst () = 21 dequeue.pollLast () = 20 dequeue = []

If you take a closer look, you will see that the elements are output in the reverse order (namely from header to end) than they were shown in the graphic at the beginning of the article and as they were output in the queue example of (from end to header).

BlockingDeque Interface

Analogous to (→ Javadoc) offers additional blocking operations that wait when removing an element from the deque until an element is available, or when inserting an element wait until space is available.

Again for reasons of consistency, the operations inherited from have been implemented again with a new name. You can recognize these cases by the fact that two method names are specified in a table field.

I have now divided the 30 methods into two tables.

Operations at the beginning (head) of the deque

Operations at the end of the Deque

Java BlockingDeque example

The code example is even longer than the previous ones. Therefore I will not print it here in the article. You can find it (like all of the other code samples in this article) in my GitHub repository.

The example is based on the previous example and adds elements to a random page or removes them from a random page of the deque.

Stacks in Java

The class that has existed since version 1.0 is just as old as Java (→ Javadoc). inherits from and adds the stack methods, and.

Exactly how is thread safe too: all methods are.

Java stack example

Here is a small example of how to use:

The output of this program is:

stack = [1, 2, 3] stack.peek () = 3 stack.pop () = 3 stack.pop () = 2 stack.pop () = 1 exception in thread "main" java.util.EmptyStackException at java .base / java.util.Stack.peek (Stack.java:101) at java.base / java.util.Stack.pop (Stack.java:83) at eu.happycoders.cds.stack.StackExample.main (StackExample .java: 16)

Both and throw one if there are no elements in the stack.

Why not use Stack

The Java developers recommend that you no longer use Stack. The Javadoc states: "A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class."

What exactly does that mean? In my opinion it should not be used for the following reasons:

  1. The use of is not a particularly high-performance means of making a data structure thread-safe. Better methods are s and CAS ("Compare-and-swap") operations, as can be found in the queue and deque implementations.
  2. The extension of provides operations that have no place in a stack, such as access to elements via their index and the insertion and deletion of elements at any position.
  3. does not implement an interface. With the use of you commit yourself to a certain implementation.

Instead, the Java developers recommend using one of the Deque implementations such as. In fairness it should be said that Deques also offer operations that a stack should not actually provide, such as inserting and removing elements at the bottom of the stack.

A better stack implementation

A clean stack implementation consists of a stack interface and one or more implementations - there is nothing to prevent it from being used as an adapter for an existing deque implementation.

Stack interface (→ code in GitHub):

Non-thread-safe stack implementation based on (→ Code in GitHub):

Array- vs. Linked List-based queues and deques

Before we come to the queue and deque implementations and their properties, here is a brief digression on the underlying data structures: Arrays and linked lists.

Array-based data structures in Java usually deliver significantly better performance.

On the one hand, the memory requirement for an array is significantly lower *:

  • Array (e.g.): 4 bytes per entry.
  • Doubly linked list (e.g.): 24 bytes per entry - each entry requires an object, and these each require 12 bytes for the object header + 3 × 4 bytes for the -, - and references.
  • Simply linked list: also 24 bytes per entry - the nodes do not need any references, but 4 pad bytes are inserted for each object, since objects always have to occupy a multiple of 8 bytes of memory.

On the other hand, arrays have the advantage that their elements are located at consecutive memory addresses, so that when the main memory is accessed, all array elements that are on the same memory page are loaded into the CPU cache at the same time.

The nodes of a linked list, on the other hand, can be distributed across the heap, so that when iterating over a linked list, in the worst case scenario, a new memory page has to be loaded into the CPU cache for each element.

A third disadvantage of linked lists is that they represent more work for the garbage collector than arrays, since the GC has to follow all nodes of the list in the "reachability analysis" in order to mark reachable objects.

In principle, one should therefore prefer array-based data structures. However, depending on the type of use and the implementation of thread safety, queues / deques based on linked lists can also be faster. I will go into this in more detail in the description of the individual queue / deque implementations.

(* I'm assuming a 64-bit JVM with activated Compressed Oops when looking at the memory.)

Java queue and deque implementations (non-blocking)

In the following sections you will find descriptions and the most important properties of all queue and deque implementations available in the JDK - first the non-blocking variants, followed by the blocking variants.

I recommend sensible purposes for each implementation.

ArrayDeque

The class (→ JavaDoc) is based - as the name suggests - on an array. A circular buffer is implemented on this basis. You can read exactly how this works in this Wikipedia article.

The ring buffer has the advantage that elements do not have to be moved within the array on either side of the deque when inserting or removing elements. So here we get the flexibility of a linked list without its performance disadvantages.

The array grows as needed, but it does not automatically shrink, nor can it be shrunk manually.

The other properties of:

  • Non-blocking
  • Unbounded
  • Not thread-safe
  • The iterator is neither fail-fast (i.e. he doesn't throw any) yet weakly consistent (i.e. no guarantees are made with regard to the consistency in the case of concurrent changes).
  • Time complexity of: O (1)

Recommended use

This is a good choice for (and only for) single-threaded applications. The fact that the underlying array cannot be shrunk should be kept in mind.

ArrayDeque example

You can find a code example above in the section "Java Deque Example".

LinkedList

The class (→ Javadoc) implements a classic doubly linked list. It has existed in the JDK since version 1.2, i.e. significantly longer than the interface. The deque methods were added with the introduction of this interface in JDK 6.0.

The other properties of are:

  • Non-blocking
  • Unbounded
  • Not thread-safe
  • The iterator is fail-fast, d. H. he throws a change at the same time.
  • Time complexity of: O (1) - the size is stored in a field of, i.e. H. to determine the size must Not iterated over the complete list (which would result in a time complexity of O (n)).

Recommended use

I generally advise against using the. If you need a list, one of the above Better choice for performance reasons; if you need a non-thread-safe queue or a non-thread-safe deque, then use a.

LinkedList example

To experiment with the, you can copy the "Java Deque Example" presented above and the line

by

replace.

ConcurrentLinkedQueue and ConcurrentLinkedDeque

We come to the first thread-safe queue and deque implementations.

The class (→ Javadoc) is based on a singly linked list; (→ Javadoc) on a doubly linked list.

Both implementations guarantee thread safety through non-blocking CAS ("Compare-and-swap") operations on VarHandles, which results in a significant gain in performance compared to the use of locks such as.

The other properties of and:

  • Non-blocking
  • Unbounded
  • The iterator is weakly consistent, d. H. all queue / deque elements that exist at the time the interator is generated are run through by the iterator exactly once. Changes that occur after this can, but do not have to, be taken into account by the iterator.
  • Time complexity of: O (n), since all elements of the queue are iterated to determine the size. If queue items are added or removed during the determination of the size, the result may be inaccurate.

Recommended use

and are a good choice if a non-blocking, unbounded and thread-safe queue (or a corresponding deque) is required.

Despite my general recommendation, this is preferable to array-based data structures. It's not thread-safe. And the one described in the next chapter is on the one hand bounded and on the other hand, thread safety is implemented via a single one, which is much less performing than compare-and-swap on VarHandles.

ConcurrentLinkedQueue example

We have already used this in the first code example in the section "Java Queue Example".

ConcurrentLinkedDeque example

The following example demonstrates the thread safety of the. Four writing and three reading threads concurrently add and remove elements on random pages of the Deque (→ code in GitHub):

An example output:

deque.offerFirst (388) -> deque = [388] deque.offerLast (900) -> deque = [388, 900] deque.pollFirst () = 388 -> deque = [900] deque.offerLast (906 ) -> deque = [900, 906] deque.pollLast () = 906 -> deque = [900] deque.pollFirst () = 900 -> deque = [] deque.offerLast (727) -> deque = [727] deque.offerFirst (720) -> deque = [720, 727] deque.pollLast () = 727 -> deque = [720] deque.offerFirst (415) -> deque = [415, 720 ] deque.offerLast (614) -> deque = [415, 720, 614] deque.offerFirst (130) -> deque = [130, 415, 720, 614]

PriorityQueue

The class (→ Javadoc) is not a queue in the classic sense, since the elements are not taken in FIFO order, but according to their natural order or according to a s passed to the constructor.

The smallest element is located at the head of the queue. The sorting is not stable, i. H. two elements that are in the same position according to the sorting order are not necessarily removed in the same order as they were inserted into the queue.

The other properties of are:

  • Non-blocking
  • Unbounded
  • Array-based
  • Not thread-safe
  • The iterator is fail-fast, d. H. he throws a change at the same time.
  • Internally, the elements are stored in an array that represents a min heap; the iterator iterates through the elements in the appropriate order.
  • Time complexity of: O (1)

Recommended use

This can be used precisely when a non-thread-safe queue with the dequeue order described above is required.

However, it should be noted that the JDK is only used in very few places and therefore there is a certain probability of the presence of bugs (what is little used is also little tested).

PriorityQueue example

Here is a small example in which ten random numbers are written into one and then removed again (→ code in GitHub):

The following is an exemplary output of the program, which clearly shows how the elements in the queue are not displayed in any particular order (only the smallest element is always at the front) and how they are ultimately removed in ascending order:

queue.offer (44) -> queue = [44] queue.offer (18) -> queue = [18, 44] queue.offer (58) -> queue = [18, 44, 58] queue. offer (98) -> queue = [18, 44, 58, 98] queue.offer (45) -> queue = [18, 44, 58, 98, 45] queue.offer (83) -> queue = [18, 44, 58, 98, 45, 83] queue.offer (31) -> queue = [18, 44, 31, 98, 45, 83, 58] queue.offer (21) -> queue = [18, 21, 31, 44, 45, 83, 58, 98] queue.offer (22) -> queue = [18, 21, 31, 22, 45, 83, 58, 98, 44] queue. offer (19) -> queue = [18, 19, 31, 22, 21, 83, 58, 98, 44, 45] queue.poll () = 18 -> queue = [19, 21, 31, 22 , 45, 83, 58, 98, 44] queue.poll () = 19 -> queue = [21, 22, 31, 44, 45, 83, 58, 98] queue.poll () = 21 -> queue = [22, 44, 31, 98, 45, 83, 58] queue.poll () = 22 -> queue = [31, 44, 58, 98, 45, 83] queue.poll () = 31 - -> queue = [44, 45, 58, 98, 83] queue.poll () = 44 -> queue = [45, 83, 58, 98] queue.poll () = 45 -> queue = [58 , 83, 98] queue.poll () = 58 -> queue = [83, 98] queue.poll () = 83 -> queue = [98] queue.poll () = 98 -> queue = []

Java queue and deque implementations (blocking)

In the following sections I describe all of the blocking queue and deque implementations of the JDK. H. those classes that implement the interfaces respectively.

ArrayBlockingQueue

The class (→ Javadoc) is based - like that - on an array, but is

  • thread safe,
  • bounded (has a maximum capacity),
  • is accordingly blocking
  • and offers a fairness policy (remember: blocking methods are served in the order in which they were called).

Thread safety is guaranteed by a single one, so that simultaneous write and read access can lead to a high number of access conflicts ("thread contention").

The other properties of the are:

  • The iterator is weakly consistent (Here again the definition: All queue / deque elements that exist at the time the interator is created are run through by the iterator exactly once. Changes that occur afterwards can, but do not have to be taken into account by the iterator).
  • Time complexity of: O (1)

Recommended use

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

ArrayBlockingQueue example

To try them out, you can copy the "Java BlockingQueue Example" from above and

by

replace.

LinkedBlockingQueue and LinkedBlockingDeque

The classes (→ Javadoc) and (→ Javadoc) are based - just like and - on linked lists, but are - just like -

  • thread safe,
  • bounded (have a maximum capacity)
  • and blocking.

In contrast to the, thread safety is not guaranteed with one, but with two separate s - one for write and one for read access. This reduces the access conflicts between producer and consumer threads.

The other properties of and are:

  • no fairness policy available
  • The iterator is weakly consistent (Definition see above).
  • Time Complexity of: O (1) - the implementations use an internally to keep the size available (as opposed to and, which have to iterate over all elements when querying the size).

Recommended use

I recommend and when you need blocking, thread-safe queues / deques.

The class is used by and as a "work queue" for the executor. It is therefore used intensively, which keeps the likelihood of bugs extremely low.

LinkedBlockingQueue and LinkedBlockingDeque examples

Code examples for and can be found in the sections "Java BlockingQueue Example" and "Java BlockingDeque Example" above.

PriorityBlockingQueue

The (→ Javadoc) is a thread-safe and blocking variant of the.

Thread safety is ensured by a single one.

In contrast to all the blocking implementations presented so far, it is not bounded, so it has no capacity limit. This means that the method does not throw an exception, never returns and and never blocks. Only block or return dequeue operations when the queue is empty.

The other properties of:

  • Array-based
  • no fairness policy available
  • The iterator is weakly consistent (Definition see above).
  • As with the, the elements are stored in an array that represents a min heap; the iterator iterates through the elements in the appropriate order.
  • Time complexity of: O (1)

Recommended use

It is not used in the JDK. So there is a certain possibility that it contains bugs. If you need a queue with appropriate properties and use them, you should test intensively.

PriorityBlockingQueue example

As an example for this, I have slightly modified the code from the section "Java BlockingQueue Example": The is used instead of one; and instead of the numbers 0 to 9, random numbers are written into the queue.

I am not printing the example here due to the minimal code changes. You can find it here in my GitHub repository. If you let it run, you will see that - just like with the - the smallest element is always at the head of the queue and is the next to be removed.

DelayQueue

Finally, we come to a couple of very special queue implementations of the JDK.

The class (→ Javadoc) is - like the one it uses internally - not a FIFO queue. Instead, elements can only be removed when a waiting time ("delay") assigned to the element has expired.

To do this, the elements must implement the interface (→ Javadoc) and its method. With each call, this returns the remaining waiting time that has to expire before the element can be removed from the queue.

Just like that, the blocking is unbounded, so it can accommodate any number of elements and only blocks when it is removed.

Thread safety is ensured by a single one.

The other properties of:

  • no fairness policy available
  • The iterator is weakly consistent (Definition see above).
  • Time complexity of: O (1) as with the underlying.

Recommended use

I have never needed it and cannot recommend it for any useful purpose that I know of. It is only used once in the JDK (in an old Swing class that could probably have been implemented with a more elegant one), so it cannot be ruled out that it contains errors.

DelayQueue example

In the following example (→ Code in GitHub), one is filled with objects of the class that contain a random number and a random initial delay between 100 and 1,000 ms. It is then called repeatedly until the queue is empty again.

And here the associated class (→ code in GitHub). The sorting is - so as not to make the code any longer - not stable, i. H. if two elements are queued with the same waiting time, they are removed again in random order.

Here is an exemplary output of the program. It is easy to see how the queue is not sorted, but the element with the shortest waiting time is always at the front (left) and that the elements are removed 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 = []

LinkedTransferQueue

Another special queue is the (→ Javadoc). It is - like that - an unbounded blocking queue, i. H. only the dequeue operations can lead to errors or block.

is based on a linked list, and thread safety is achieved just as with and through non-blocking compare-and-swap operations.

The special thing about this queue is that it provides additional and methods that block until the element attached via / has been removed from the queue (in contrast to: until space in the queue is free). For the details of these methods, I refer to the Javadoc linked above.

The other properties of:

  • no fairness policy available
  • The iterator is weakly consistent (Definition see above).
  • Time complexity of: O (n) - the entire queue is iterated to determine the size.

Recommended use

This is not used in the JDK. It was originally implemented for the fork / join framework introduced in JDK 7, but has not yet been used for it. The probability of bugs is therefore quite high, so this class should not be used.

LinkedTransferQueue example

In the following example (→ Code in GitHub) five threads are started that call. Elements are then removed from the queue until it is empty again.

The output of the example clearly shows how the calls initially block and a call always returns when the value passed by has been taken:

[Thread-0] Calling queue.transfer (0) (queue = []) ... [Thread-1] Calling queue.transfer (1) (queue = [0]) ... [Thread-2] Calling queue .transfer (2) (queue = [0, 1]) ... [Thread-3] Calling queue.transfer (3) (queue = [0, 1, 2]) ... [Thread-4] Calling queue .transfer (4) (queue = [0, 1, 2, 3]) ... [main] queue = [0, 1, 2, 3, 4] [main] Calling queue.take () (queue = [ 0, 1, 2, 3, 4]) ... [main] queue.take () returned 0 (queue = [1, 2, 3, 4]) [Thread-0] queue.transfer (0) returned ( queue = [1, 2, 3, 4]) [main] Calling queue.take () (queue = [1, 2, 3, 4]) ... [main] queue.take () returned 1 (queue = [2, 3, 4]) [Thread-1] queue.transfer (1) returned (queue = [2, 3, 4]) [main] Calling queue.take () (queue = [2, 3, 4] ) ... [main] queue.take () returned 2 (queue = [3, 4]) [Thread-2] queue.transfer (2) returned (queue = [3, 4]) [main] Calling queue. take () (queue = [3, 4]) ... [main] queue.take () returned 3 (queue = [4]) [Thread-3] queue.transfer (3) ret urned (queue = [4]) [main] Calling queue.take () (queue = [4]) ... [main] queue.take () returned 4 (queue = []) [Thread-4] queue. transfer (4) returned (queue = [])

SynchronousQueue

We come to the last blocking special queue, the (→ Javadoc). “Synchronous” is not to be confused with “synchronized”. Rather, it means that every enqueue operation has to wait for a corresponding dequeue operation and every dequeue operation has to wait for an enqueue operation.

One never contains elements, not even if enqueue operations are currently waiting for dequeue operation. Similarly, the size of a is always 0 and always returns.

In addition to this, this is the second queue implementation that offers a fairness policy. There is a special feature here: If the fairness policy is not activated, blocking calls are served in an unspecified order according to the documentation. In fact, however, these are served in exactly the opposite order (i.e. in LIFO order), since a stack is used internally.

The other properties of:

  • Unbounded
  • is based on a linked list
  • thread-safe thanks to compare-and-swap operations on VarHandles
  • The iterator is always empty.
  • Time complexity of: O (1) - always returns 0.

Recommended use

Just like them, I've never used them directly in my own projects.

If their properties match your requirements, you can use them without hesitation. In the JDK, the