Queue

A queue is a collection with limited access to elements: elements are inserted at the end of it and removed from the beginning. The collection follows the first-in-first-out (FIFO) principle. Queues are designed for holding elements prior to processing: tasks, events, or something else.

An excellent real-life example of a queue is a line of students in the food court. New additions to a line made to the back of the queue, while removal (or serving) happens in the front.

Implementations of Queue

In Java, all queues are represented by the Queue<E> interface. However, the hierarchy of queues is more complex than it seems at first glance. The primary implementations of the Queue<E> are LinkedList<E> and ArrayDeque<E>. There is also a PriorityQueue which we will consider in a separate topic.

Both of the primary implementations inherit the Deque<E> interface which extends Queue<E> and represents a double-ended queue that supports FIFO and LIFO access principles. At the same time, the LinkedList<E> class also implements the List<E> interface, so it can be used as a queue and as a list depending on the task.

The Queue interface

The Queue<E> interface extends Collection<E> and adds some new methods:

• boolean offer(E e) inserts the specified element into the queue if it is possible to do so immediately without violating capacity restrictions; it returns true / false depending on the result of this operation;
• E remove() retrieves and removes the head of this queue; if it's empty, the method throws NoSuchElementException;
• E poll() retrieves and removes the head of this queue, or returns null if this queue is empty;
• E element() retrieves, but does not remove, the head of the queue; if it's empty, the method throws NoSuchElementException;
• E peek() retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

The differences between some of these methods and methods inherited from Collection may not be so obvious. Let's see:

• the add(E e) method does the same as offer(E e) but throws IllegalStateException if no space is currently available;
• remove() and element() throws NoSuchElementException where the queue is empty, but poll() and peek() just return null in this case.

Deque

As we mentioned before, Deque<E> extends Queue<E> and represents a queue where you can insert and remove elements from both ends. It combines access rules provided by queue (FIFO) and stack (LIFO) together.

The Deque interface provides methods for working with the first and the last element of a queue. Some of the methods throw an exception, while others just return a special value (null). Check out the table:

Since ArrayDeque and LinkedList implement this interface, they both can work as a queue (FIFO), a stack (LIFO), or a deque.

We will consider an example of how to use it further.

Using ArrayDeque as a queue

Let's consider an example of how to use ArrayDeque as a queue (FIFO).

Queue<String> q = new ArrayDeque<>();

q.offer("first");
q.offer("second");
q.offer("third");

System.out.println(q.peek()); // first
System.out.println(q.peek()); // first
System.out.println(q.poll()); // first,

System.out.println(q.peek()); // second
System.out.println(q.poll()); // second
System.out.println(q.poll()); // third

System.out.println(q.isEmpty()); // true

Just remember, peek() returns the current head element, but does not remove it from the queue, whereas poll() does it. The use of the LinkedList as a Queue is similar.

Conclusion

We've considered the Queue interface, its subtype Deque interfaces as well as two of its implementations.

If you need to work with a queue (FIFO), try to use ArrayDeque via the standard Queue interface. This implementation is quite efficient, and the interface provides all the required operations. If you need to work with a stack (LIFO) or deque (FIFO+LIFO), try to use ArrayDeque via the Deque interface which provides operations for both ends of a queue. The LinkedList can also be used as an implementation, but it is considered less memory efficient when working with a large number of elements.