Queue

Java Queue Example (with video)

In this article, we feature a comprehensive Java Queue Example and we explain what a Priority Queue in Java is. With the Java Queue, we can keep and handle elements before processing. Except for the methods that Collection provides, it also supports some basic operations in order to simulate the classic queue structure. Each of these operations exists in two forms:

  • if a method fails, an exception is thrown. This form includes add(), remove() and element() methods.
  • if a method fails, a special value is returned (null or false). This form contains offer(), poll() and peek() operations.

You can also check this tutorial in the following video:

Java Queue Example – Video

It is worth to mention that FIFO (first-in-first-out) is the most common way to order the elements in the Java Queue. In order to visualize the structure of the Queue please consider the snapshot below,

Java Queue - Data Structure
Queue Data Structure

The above snapshot shows that the queue is merely acting as a buffer which can be filled from one end, with operation enqueue, and emptied from the other end, with operation dequeue.

Queue data structure implementation comes baked in Java Collections Framework, the following diagram shows the place of the Queue implementation class within the hierarchy of the java collections framework.

Java Queue - UML Diagram
UML Diagram for Queue Data Structure

In the following section, we are going to show the operations to manage a queue.

1. Explanation of Queue operations

First of all, let’s see analytically the basic operations that exist in two different forms.

1.1. Throws exception

  • add(E e): inserts the element e to the tail of the queue. If there is no space available because of capacity restrictions, IllegalStateException is thrown.
  • remove(): removes and returns the head (the first element) of the queue. If the queue is empty, NoSuchElementException is thrown.
  • element(): just returns the head of the queue, without removing it. If the queue is empty, again NoSuchElementException is thrown.

1.2. Returns special value

  • offer(E e): adds the element e to the tail of the queue. If the insertion is successful the method returns true, otherwise, it returns false. Generally, if there are capacity bounds, it is preferred to use add method instead.
  • poll(): like remove() function, it retrieves and removes the head of the queue. The only difference from remove() is that poll() operation returns null when the queue is empty.
  • peek(): just like element() operation it retrieves and returns the head of the queue, without removing it. In this situation when the queue is empty, it returns null.

2. Queue’s Interfaces

The Queue interface does not define the blocking queue methods, which are common in concurrent programming. These methods, which wait for elements to appear or for space to become available, are defined in the BlockingQueue interface, which extends this interface

  • Deque: abstracts a queue that has two heads. A deque allows adding or removing elements at both ends.
  • BlockingQueue: abstracts a type of queues that waits for the queue to be non-empty when retrieving an element, and waits for space to become available in the queue when storing an element.
  • BlockingDeque: is similar to BlockingQueue, but for double-ended queues. It is a sub-interface of the BlockingQueue.
  • TransferQueue is a specialized BlockingQueue, in which producers can wait for consumers to receive elements.

3. Queue’s Implementations

Queue implementations generally do not allow insertion of null elements, although some implementations, such as LinkedList, do not prohibit insertion of null. Even in the implementations that permit it, null should not be inserted into a Queue, as null is also used as a special return value by the poll method to indicate that the queue contains no elements.

Queue implementations generally do not define element-based versions of methods equals and hashCode but instead inherit the identity-based versions from class Object, because element-based equality is not always well-defined for queues with the same elements but different ordering properties.

3.1. General-purpose Queue implementations:

  • LinkedList: this class implements both List and Deque interface, thus having hybrid characteristics and behaviors of list and queue. Consider using a LinkedList when you want fast adding and fast removing elements at both ends, plus accessing elements by index.
  • PriorityQueue: the priority queue in Java orders elements according to their natural ordering, or by a Comparator provided at construction time. Consider using a Priority Queue when you want to take advantage of natural ordering and fast adding elements to the tail and fast removing elements at the head of the queue in Java program.
  • AbstractQueue: This class provides skeletal implementations of some Queue operations. The implementations in this class are appropriate when the base implementation does not allow null elements. Methods add, remove, and element are based on offer, poll, and peek, respectively, but throw exceptions instead of indicating failure via false or null returns. 

3.2. Concurrent Queue implementations:

  • LinkedBlockingQueue: an optionally bounded FIFO blocking queue backed by linked nodes
  • ArrayBlockingQueue: a bounded FIFO blocking queue backed by an array
  • PriorityBlockingQueue: an unbounded blocking priority queue backed by a heap in a Java program
  • DelayQueue: a time-based scheduling queue backed by a heap
  • SynchronousQueue: a simple rendezvous mechanism that uses the BlockingQueue interface
  • LinkedTransferQueue: an unbounded TransferQueue based on linked nodes
  • ConcurrentLinkedQueue: An unbounded thread-safe queue based on linked nodes.

4. Deque’s Implementations

The Deque interface, pronounced as “deck”, represents a double-ended queue. The Deque interface can be implemented as various types of Collections. The Deque interface implementations are grouped into general-purpose and concurrent implementations.

4.1 General-purpose Queue implementations:

  • ArrayDeque: a simple implementation of the Deque interface. Consider using an ArrayDeque when you want to utilize features of a double ended queue without list-based ones (simpler than a LinkedList).
  • LinkedList: Implements all optional list operations, and permits all elements (including null).

4.2 Concurrent Queue implementations:

  • LinkedBlockingDeque: is the concurrent implementation of the Deque interface.
  • ConcurrentLinkedDeque: An unbounded concurrent deque based on linked nodes.

While Deque implementations are not strictly required to prohibit the insertion of null elements, they are strongly encouraged to do so. Users of any Deque implementations that do allow null elements are strongly encouraged not to take advantage of the ability to insert nulls. This is so because null is used as a special return value by various methods to indicate that the deque is empty.

Deque implementations generally do not define element-based versions of the equals and hashCode methods, but instead inherit the identity-based versions from class Object.

5. Example of Java Queue

Now, we are going to show in the code how to use the operations we explained above. So, create a new java file with the name QueueClass and paste the following code.

QueueClass.java

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package com.javacodegeeks.core.queue;
 
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;
 
public class QueueClass {
 
    public static void main(String[] args) {
         
        Queue myQueue = new LinkedList();
 
        // add elements in the queue using offer() - return true/false
        myQueue.offer("Monday");
        myQueue.offer("Thursday");
        boolean flag = myQueue.offer("Wednesday");
         
        System.out.println("Wednesday inserted successfully? "+flag);
         
        // add more elements using add() - throws IllegalStateException
        try {
            myQueue.add("Thursday");
            myQueue.add("Friday");
            myQueue.add("Weekend");
        } catch (IllegalStateException e) {
            e.printStackTrace();
        }
         
        System.out.println("Pick the head of the queue: " + myQueue.peek());
         
        String head = null;
        try {
            // remove head - remove()
            head = myQueue.remove();
            System.out.print("1) Push out " + head + " from the queue ");
            System.out.println("and the new head is now: "+myQueue.element());
        } catch (NoSuchElementException e) {
            e.printStackTrace();
        }
         
        // remove the head - poll()
        head = myQueue.poll();
        System.out.print("2) Push out " + head + " from the queue");
        System.out.println("and the new head is now: "+myQueue.peek());
         
        // find out if the queue contains an object
        System.out.println("Does the queue contain 'Weekend'? " + myQueue.contains("Weekend"));
        System.out.println("Does the queue contain 'Monday'? " + myQueue.contains("Monday"));
    }
 
}

As you can see in the code above, in order to create a queue we should assign LinkedList instance to the Queue object. In addition, you can notice how we call and use the functions we explained before. Also, it is worth to mention that you can use more methods that Queue inherits from Collection, such as contains() method.

You can see the output of the execution of the above code.

Output

Wednesday inserted successfully? true
Pick the head of the queue: Monday
1) Push out Monday from the queue and the new head is now: Thursday
2) Push out Thursday from the queue and the new head is now: Wednesday
Does the queue contain 'Weekend'? true
Does the queue contain 'Monday'? false

In this next example of java queue, we will discuss the Java BlockingQueue. Java BlockingQueue implementations are thread-safe. All queuing methods are atomic in nature and use internal locks or other forms of concurrency control. Java BlockingQueue interface is part of java collections framework and it’s primarily used for implementing the producer-consumer problem. In the code example shown below, we will be using the ArrayBlockingQueue concrete class, which is one of the implementations of BlockingQueue Interface.

First we will define the structure of the object which will be passed between the Producer and Consumer.

MessageClass.java

public class MessageClass {
    private String messageString;

    public MessageClass(String passedString) {
        this.messageString = passedString;
    }

    public String getMessageString() {
        return messageString;
    }

}

Next, we will define the Producer class and Consumer class.

ProducerClass.java

import java.util.concurrent.BlockingQueue;

public class ProducerClass implements Runnable {

    private BlockingQueue<MessageClass> queue;

    public ProducerClass(BlockingQueue<MessageClass> q) {
        this.queue = q;
    }

    @Override
    public void run() {
        for (int i = 0; i < 5; i++) {
            MessageClass msg = new MessageClass("" + i);
            try {
                Thread.sleep(i);
                queue.put(msg);
                System.out.println("Produced " + msg.getMessageString());
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        MessageClass msg = new MessageClass("exit");
        try {
            queue.put(msg);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

}

ConsumerClass.java

import java.util.concurrent.BlockingQueue;

public class ConsumerClass implements Runnable {

    private BlockingQueue<MessageClass> queue;

    public ConsumerClass(BlockingQueue<MessageClass> q) {
        this.queue = q;
    }

    @Override
    public void run() {
        try {
            MessageClass msg;
            while ((msg = queue.take()).getMessageString() != "exit") {
                Thread.sleep(10);
                System.out.println("Consumed " + msg.getMessageString());
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

Finally, we will define the driver class for the application.

BlockingQueueExample.java

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

public class BlockingQueueExample {
    public static void main(String[] args) {
        BlockingQueue<MessageClass> queue = new ArrayBlockingQueue<>(10);
        ProducerClass producer = new ProducerClass(queue);
        ConsumerClass consumer = new ConsumerClass(queue);
        new Thread(producer).start();
        new Thread(consumer).start();
        System.out.println("BlockingQueue Example");
        System.out.println("Producer and Consumer has been started");
    }
}

This driver class initiates both the Producer and Consumer class objects. Producer will start producing in a thread safe way and Consumer consumes in similar manner as producer. Output of the BlockingQueueExample.java is shown in the snapshot below.

Java Queue - BlockingQueueExample.java
Output of BlockingQueueExample.java

This next example is about the BlockingDeque in Java. The BlockingDeque interface in the java.util.concurrent class represents a deque which is thread safe to put into, and take instances from. The BlockingDeque class is a Deque which blocks threads tring to insert or remove elements from the deque, in case it is either not possible to insert or remove elements from the deque. The LinkedBlockingDeque class implements the BlockingDeque interface. The LinkedBlockingDeque is a Deque which will block if a thread attempts to take elements out of it while it is empty, regardless of what end the thread is attempting to take elements from.

The code snippet showing the BlockingDeque in action is shown below.

BlockingDequeExample.java

import java.util.concurrent.BlockingDeque;
import java.util.concurrent.LinkedBlockingDeque;

public class BlockingDequeExample {
    public static void main(String[] args) {
        System.out.println("Blocking DeQueue Example");
        BlockingDeque<Integer> LBD
                = new LinkedBlockingDeque<>();

        LBD.add(7855642);
        LBD.add(35658786);
        LBD.add(5278367);
        LBD.add(74381793);

        System.out.println("Blocking Deque1: "
                + LBD);
        System.out.println("Size of Blocking Deque1: "
                + LBD.size());

        BlockingDeque<Integer> LBD1
                = new LinkedBlockingDeque<>(3);

        LBD1.add(7855642);
        LBD1.add(35658786);
        LBD1.add(5278367);

        try {
            LBD1.add(74381793);
        }
        catch (Exception e) {
            System.out.println("Exception: " + e);
        }

        System.out.println("Blocking Deque2: "
                + LBD1);
        System.out.println("Size of Blocking Deque2: "
                + LBD1.size());

        BlockingDeque<Integer> LBD2
                = new LinkedBlockingDeque<>(LBD1);

        System.out.println("Blocking Deque3: "
                + LBD2);
    }
}

In this code snippet, we are trying to add the elements to the blocking double ended queue and handle the exception when the count of elements exceeds the capacity of the deque. Output of BlockingDequeExample.java is shown below.

Java Queue - Output
Output of BlockingDequeExample.java

In this last example of java queue we will discuss the TransferQueue.

TransferQueue allows us to create programs according to the producer-consumer pattern, and coordinate messages passing from producers to consumers.

The implementation is actually similar to the BlockingQueue – but gives us the new ability to implement a form of back-pressure. This means that, when the producer sends a message to the consumer using the transfer() method, the producer will stay blocked until the message is consumed.

The LinkedTransferQueue class in Java is a part of the Java Collection Framework and implements the TransferQueue Interface.

The code snippet showing the TransferQueue in action is shown below.

TransferQueueExample.java

import java.util.concurrent.LinkedTransferQueue;
import java.util.concurrent.TransferQueue;

public class TransferQueueExample {
    public static void main(String[] args) {
        System.out.println("Transfer Queue Example");
        TransferQueue<Integer> LTQ
                = new LinkedTransferQueue<>();

        LTQ.add(7855642);
        LTQ.add(35658786);
        LTQ.add(5278367);
        LTQ.add(74381793);

        System.out.println("Transfer Queue1: "
                + LTQ);

        TransferQueue<Integer> LTQ2
                = new LinkedTransferQueue<>(LTQ);

        System.out.println("Transfer Queue2: "
                + LTQ2);
    }
}

Output of TransferQueueExample.java is shown in the snapshot below.

TransferQueueExample.java
Output of TransferQueueExample.java

7. Download the Source Code

That was an example of Java Queue and Priority queue in Java.

Download
You can download the full source code of this example here: Java Queue Example

Last updated on May 03rd, 2021

Abhinav Nath Gupta

Abhinav holds a Master degree in Computer Science and Engineering from the National Institute of Technology Karnataka. He has finished his graduation from Information Technology Department in the Anand Engineering College, Agra. During his studies he has been involved with a large number of projects ranging from Networking and Cryptography. He works as a software development engineer at a software development firm in bengaluru where he is mainly involved with projects based on Nodejs. He is interested in cryptography, data security, cryptocurrency and cloud computing, and published articles regarding these topics. He can be reached at abhi.aec89@gmail.com.
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Back to top button