CodeGym /Java Blog /Java Collections /Java Queue Interface and its implementations
Author
Oleksandr Miadelets
Head of Developers Team at CodeGym

Java Queue Interface and its implementations

Published in the Java Collections group
Here we are going to discuss the Java Queue interface. You’ll find out what Queue data structure is, how it is represented in Java, what methods are the most important for all queues. Also, what implementations of Queue are in Java language. After that, we take a closer look at the most important implementations and learn them with examples.

Queue data structure

A Queue is a linear abstract data structure with the particular order of performing operations — First In First Out (FIFO). That means you can add an element (or enqueue, put in the queue) only at the end of the structure, and take an element (dequeue or remove from the queue) only from its beginning. You may imagine Queue data structure very easily. It seems like a queue or a line of customers in real life. The customer that came first, is going to be served first as well. If you have four people in line in McDonalds or elsewhere, the first to line up will be the first to get the store. If the new customer comes, he/she will be the 5th in line to get hamburgers. Java Queue Interface and its implementations - 1So, while working with a queue, new elements are added to the end, and if you want to get an element, it will be taken from the beginning. This is the main principle of classical queue data structure work.

Queue in Java

Queue in Java is an interface. According to Oracle documentation, Queue interface has 2 superinterfaces, 4 different interfaces that inherit from the queue, and an extremely impressive list of classes.

Superinterfaces:

Collection<E>, Iterable<E>

All Known Subinterfaces:

BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

All Known Implementing Classes:

AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue

What does it mean? First of all, Java Queue is a part of the Collection Framework and implements Collection interface. So it supports all methods of Collection interface such as insertion, deletion and so on. Queue implements Iterable interface, that allows an object to be the target of the "for-each loop" statement.

Queue Methods Java

The Queue declares a number of methods. As interface’s methods they should be represented in all classes that implement Queue. The most important Queue Methods, Java:
  • Boolean offer() – inserts a new element into the queue if it is possible
  • Boolean add(E e) – inserts a new element into the queue if it is possible. Returns true in case of success and throws an IllegalStateException if there is no space.
  • Object poll() – retrieves and removes an element from the head of the. Returns null if the queue is empty.
  • Object remove() – retrieves and removes an element from the head of the queue.
  • Object peek() – retrieves, but doesn’t remove an element from the head of the queue. Returns null if the queue is empty.
  • Object element() – retrieves, but doesn’t remove an element from the head of the queue.

Subinterfaces of Java Queue

Queue interface is inherited by 4 subinterfaces – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>. You may divide them into 3 groups: Deques, Blocking Queues and Transfer Queues with BlockingDeque belonging to the two first. Let's take a glimpse at these groups.

Deques

Deque means Double-Ended Queue and supports addition or removal from either tail of the data as a queue (first-in-first-out/FIFO) or from the head as another popular data structure called stack (last-in-first-out/LIFO). Classes that implement Deque Interface: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.

Blocking Queues

A blocking queue is a queue that blocks a thread in two cases:
  • thread is trying to get elements from an empty queue
  • thread is trying to put elements in the full queue
When a thread tries to get items from an empty queue, it waits until some other thread puts the items into the queue. Similarly, when a thread tries to put elements into a full queue, it waits until some other thread takes the elements out of the queue to get free space for the elements. Sure, the concept of "full queue" implies that the queue has a limited size, which is usually specified in the constructor. Standard Blocking Queues include LinkedBlockingQueue, SynchronousQueue, and ArrayBlockingQueue. Implementing classes of BlockingQueue interface: ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDeque is a subinterface for BlockingQueue. BlockingDeque such as BlockingQueue is a blocking queue, but bidirectional. So it inherits the properties of the Deque interface. It is oriented to multi-threaded execution, doesn’t allow zero elements and capacity could be limited. Implementations of the BlockingDeque interface block the operation of getting elements if the queue is empty, and adding an element into the queue if it is full.

Transfer Queues

TransferQueue interface extends BlockingQueue interface. However unlike the implementation of BlockingQueue interface queues, where threads can be blocked if the queue is empty (reading), or if the queue is full (writing), TransferQueue interface queues block the write stream until another stream retrieves the element. Use a transfer method for this. In other words, the implementation of BlockingQueue guarantees that the element created by the Producer must be in the queue, while the implementation of TransferQueue guarantees that the Producer element is "received" by the Consumer. There is only one official Java implementation of TransferQueue interface — LinkedTransferQueue.

Java Queue Implementations

There are many classes that implement Queue interface:
  • AbstractQueue according to Queue Java 8 docs, this abstract class provides basic implementations of some Queue operations. It doesn’t allow null elements. There are 3 more methods add, remove, and element based on Queue classical offer, poll, and peek, respectively. However they throw exceptions instead of indicating failure via false or null returns.
  • ArrayBlockingQueue — a fixed size FIFO blocking queue backed by an array
  • ArrayDeque — resizable array implementation of the Deque interface
  • ConcurrentLinkedDeque — an unbounded concurrent deque based on linked nodes.
  • ConcurrentLinkedQueue — an unbounded thread-safe queue based on linked nodes.
  • DelayQueue — a time-based scheduling queue backed by a heap
  • LinkedBlockingDeque — the concurrent implementation of the Deque interface.
  • LinkedBlockingQueue — an optionally bounded FIFO blocking queue backed by linked nodes
  • LinkedList — doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null)
  • LinkedTransferQueue — an unbounded TransferQueue based on linked nodes
  • PriorityBlockingQueue — an unbounded blocking priority queue backed by a heap
  • PriorityQueue — a priority queue based on the heap data structure
  • SynchronousQueue — a blocking queue where each insert operation must wait for a corresponding remove operation by another thread, and vice versa.
The most popular implementations are LinkedList, ArrayBlockingQueue and PriorityQueue. Let’s look at them and do some examples for better understanding.

LinkedList

Class LinkedList in Java implements List and Deque interfaces. So, it is a combination of List and Deque, a two-way queue, that supports adding and removing elements from both sides. In Java LinkedList is doubly-linked List: every element of List calls Node and contains an object and references to two neighboring objects — the previous and the next. Java Queue Interface and its implementations - 2You may say that LinkedList isn’t very effective in terms of using memory. That’s true, but this data structure can be useful in case of the insert and delete operations performance. However it happens only if you use iterators for them (in this case it occurs in constant time). Access operations by index are performed by searching from the beginning of the end (whichever is closer) to the desired element. However, don’t forget about additional costs for storing references between elements. So, LinkedList is the most popular queue implementation in Java. It is an implementation of List and Deque as well and it allows us to create a bidirectional queue consisting of any objects including null. LinkedList is a collection of elements.
More about LinkedList: LinkedList Java Data Structure

LinkedList Constructors

LinkedList() without parameters is used to construct an empty list. LinkedList(Collection<? extends E> c) is for creating a list containing the elements of the specified collection, in order, they are returned by the collection's iterator.

Main LinkedList Methods:

  • add(E element) Appends the specified element to the end of this list;
  • add(int index, E element) Inserts the element at the specified position index;
  • get(int index) Returns the element at the specified position in this list;
  • remove(int index) Removes the element that is at position index;
  • remove(Object o) Removes the first occurrence of ?o element from this list if it is there.
  • remove() Retrieves and removes the first element of the list.
  • addFirst(), addLast() add an element to the beginning/end of a list
  • clear() removes all elements from the list
  • contains(Object o) returns true if the list contains the o element.
  • indexOf(Object o) returns the index of the first occurrence of the o element, or -1 if it isn’t in the list.
  • set(int index, E element) replaces the element at index position with the element
  • size()Returns the quantity of elements in the list.
  • toArray() returns an array containing all list’s elements from first to the last element.
  • pop() that pops an element from the stack (represented by the list)
  • push(E e) that pushes an element onto the stack (represented by this list)
Java Queue Example — LinkedList (putting and removing elements in different ways)

import java.util.*;
 
public class LinkedListTest {
 
       public static void main(String args[]){
 
           LinkedList<Integer> myLinkedList= new LinkedList<Integer>();
           myLinkedList.add(1);
           myLinkedList.add(2);
           myLinkedList.add(4);
           System.out.println("three added elements: " + myLinkedList);
           //put one element into the head, not to the tail:
           myLinkedList.push(5);
           System.out.println("The new element last in will be the first: " + myLinkedList);
           //add new element at the specified position:
           myLinkedList.add(4,3);
           //put one element into the head, not to the tail (same as push):
           myLinkedList.addFirst(6);
           System.out.println(myLinkedList);
           //now remove element no 2 (it is 1):
           myLinkedList.remove(2);
           System.out.println(myLinkedList);
           //now remove the head of the list
           myLinkedList.pop();
           System.out.println(myLinkedList);
           //remove with the other method
           myLinkedList.remove();
           System.out.println(myLinkedList);
           //and with one more
           myLinkedList.poll();
           System.out.println(myLinkedList);
       }
       }

PriorityQueue

PriorityQueue is not exactly the queue in FIFO general meaning. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. However it is not an order like it could be in linear structure such as list (from the biggest to the smallest or vice versa). A priority queue based on a priority min heap. Heap is a data structure based on binary tree. The priority of each parent is greater than the priorities of its children. A tree is called complete binary if each parent has no more than two children, and the filling of the levels goes from top to bottom (from the same level — from left to right). Binary heap reorganises itself every time a new element is added or removed from it. In case of min-heap, the smallest element goes to the root regardless of the order of its insertion. Priority queue based on this min-heap, so if we have a PriorityQueue of integers, its first element will be the smallest of these numbers. If you delete the root, the next smallest becomes a root.

Main PriorityQueue Methods:

  • boolean add(object) inserts the specified element into the priority queue. Returns true in case of success. If the queue is full, the method throws an exception.
  • boolean offer(object) inserts the specified element into this priority queue. If the queue is full, the method returns false.
  • boolean remove(object) removes a single instance of the specified element from this queue, if it is present.
  • Object poll() retrieves and removes the head of this queue. Returns null if the queue is empty.
  • void clear() removes all elements from the priority queue.
  • Object element() retrieves the head of this queue without removing it. Throws NoSuchElementException if the queue is empty.
  • Object peek() retrieves the head of the queue without removing it. Returns null if the queue is empty.
  • boolean contains(Object o) returns true if the queue contains the o element.
  • int size() returns the number of elements in this queue.

Example of PriorityQueue


import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5
It is important to understand that priority queues are based on binary heaps, so they do not keep elements in linear sorted order. Every way from the root to the leaf is ordered, but different ways from the root are not. That means you can get the minimal element of the queue very quickly. If you delete the head every time, you’ll print a sorted structure.

ArrayBlockingQueue

Internal data structure of ArrayBlockingQueue is based on a circular array to store elements. It is a typical queue (FIFO) in case new elements are inserted at the tail of the queue, and extraction operations return an element from the head of the queue.Once created queue capacity cannot be changed. Attempts to insert (put) an element into a full queue lead to blocking the flow; trying to take an element from an empty queue also blocks the thread. As we said before, this array is circular. That means that the first and the last elements of the array are treated logically adjacent. The queue advances the indices of the head and tail elements every time you put the elemento into the queue or remove it from the queue. If some index advances the last element of the array, it restarts from 0. Hence, the queue doesn’t have to shift all the elements in case of the head removing (as in usual array). However, in case of removing an element from the middle (using Iterator.remove), the elements are shifted. ArrayBlockingQueue supports an additional fairness policy with fair parameter in the constructor to order the work of waiting flows of producers (inserting elements) and consumers (extracting elements). By default, the order is not guaranteed. However if the queue is created with "fair == true", the implementation of the ArrayBlockingQueue class provides thread access in FIFO order. Equity typically reduces bandwidth, but also reduces volatility and prevents running out of resources.

ArrayBlockingQueue Class сonstructors

  • ArrayBlockingQueue (int capacity) creates a queue of fixed capacity and with a default access policy.
  • ArrayBlockingQueue (int capacity, boolean fair) creates a queue with a fixed capacity and a specified access policy.
  • ArrayBlockingQueue (int capacity, boolean fair, Collection <? extends E> c) creates a queue with a fixed capacity specified by the access policy and includes elements in the queue.
Here we’ve got the BlockingQueueExample example. We create a queue of the ArrayBlockingQueue with a capacity of one element and a fair flag. Two threads are started. The first of them, Producer thread, queues messages from the messages array using the put method. The second one, Consumer, thread reads elements from the queue using take method and displays them in the console. The order of elements is the natural one for the queue.

import java.util.concurrent.*;
 
public class ArrayBlockingQueueExample {
 
   private BlockingQueue<Integer> blockingQueue;
   private final Integer[]  myArray = {1,2,3,4,5};
  
       public ArrayBlockingQueueExample ()
       { blockingQueue = new ArrayBlockingQueue<Integer>(1, true);
           (new Thread(new Producer())).start();
           (new Thread(new Consumer())).start();
       }
 
       class Producer implements Runnable
       {
           public void run() {
               try {
                   int counter = 0;
                   for (int i=0; i < myArray.length; i++) {
                       blockingQueue.put(myArray[i]);
                       if (counter++ < 2)
                           Thread.sleep(3000);
                   } blockingQueue.put(-1);
               }
               catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }
 
       class Consumer implements Runnable
       {
           public void run() {
               try {
                   Integer message = 0;
                   while (!((message = blockingQueue.take()).equals(-1)))
                       System.out.println(message);
               } catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }
 
       public static void main(String[] args) {
           new ArrayBlockingQueueExample();
       }
   }
The output is the queue in natural order; the first two elements appear with a delay. To reinforce what you learned, we suggest you watch a video lesson from our Java Course

Conclusions

  • The Queue is used to insert elements at the end of the queue and removes from the beginning of the queue. It follows the FIFO concept.
  • Java Queue is a part of the Collection Framework and implements Collection interface. So it supports all methods of Collection interface such as insertion, deletion and so on.
  • The most frequently used implementations of Queue are LinkedList, ArrayBlockingQueue and PriorityQueue.
  • The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.
  • If any null operation is performed on BlockingQueues, NullPointerException is thrown.
Comments (1)
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION
Andrei Level 41
13 January 2021
Good, tough lesson, but quite a few grammatical errors which sometimes make the article difficult to understand. Could use a makeover. Nice, anyway.