Implementing Genric queue data structure in Java

Given the linked list implementation of a generic queue in Java.
We have already seen linked list implementation of Queue data structure in C++ earlier. In this post, we are going to give a similar implementation in Java.
Also, we want to keep our implementation generic so that we can store any type of data in the Queue. You can learn more about generics here…
In the linked list implementation of the queue, we keep two pointers (references in Java) front and rear. front points to the first node in the list and rear point to the last node of the list.

The Queue class will have the following data structure

• Definition of Node class
• front variable
• rear variable

class MyQueue
{
    // NODE OF THE LINKED LIST USED TO STORE QUEUE ELEMENTS
    class Node
    {
        int data;
        Node next;
        // CONSTRUCTOR
        Node(int x) { data = x; next = null; }
    }
    Node front, rear;
    // REST OF THE CLASS BODY
    ... ...
}

Note that we have added a constructor in the Node class. This is just to facilitate the easy creation of Node.
Initially both front and rear are NULL. This can be set inside the constructor of MyQueue class

class MyQueue
{
    ... ...
    public MyQueue()
    {
        front = rear = null;
    }
    ... ...
}

The check for Queue being empty or not is a simple check that checks the front (or rear) pointer.

class MyQueue
{
    ... ...
    public boolean isEmpty()
    {
        return (front == null);
    }
    ... ...
}

Now, let us write the two main function, insert and remove, that insert (and remove) element from the queue in First-In-First-Out order.
Insert function creates a new node with the given value and inserts that node at the end of the list (After rear node). If the list was initially empty (i.e front was NULL), then it also set the front to point to the first (and only) node of the list.

class MyQueue
{
    ... ...
    public void insert(int x)
    {
        Node temp = new Node(x);
        if(isEmpty())
        {
            front = rear = temp;
        }
        else
        {
            rear.next = temp; rear = temp;
        }
    }
    ... ...
}

Similarly, remove function will remove the first node from the list and will return the value of that node. If the list becomes empty after deleting the node (i.e there was only one node in the list). Then we also set the rear pointer to NULL.
What if the queue does not have any elements at all. Then remove function cannot remove anything from the list. Let us say, our implementation will print this information and return -1 to indicate that queue was empty (it also means that -1 cannot be a valid value in the queue).

class MyQueue
{
    ... ...
    public int remove(){
        if(isEmpty()){
            System.out.println("Queue Empty");
            return -1;
        }
        Node temp = front;
        front = front.next;
        if(front == null)
        {
            rear = null;
        }
        return temp.data;
    }
    ... ...
}

This is NOT A GOOD implementation. In the real world, we expect a queue to throw an exception when someone tries to remove the data from an empty queue. Let us define an exception, QueueEmptyException as below:

class QueueEmptyException extends Exception
{
    public String toString(){
        return ("QUEUE IS EMPTY : ");
    }
}

This is the most basic implementation of a user-defined Exception in Java. Let us now change our remove function:

class MyQueue
{
    ... ...
    public int remove() throws QueueEmptyException
    {
        if(isEmpty()){
            throw new QueueEmptyException();
        }
        Node temp = front;
        front = front.next;
        if(front == null)
        {
            rear = null;
        }
        return temp.data;
    }
    ... ...
}

The implementation of Queue, MyQueue looks good enough if we always want to store integers in the queue. But in the real world, the queue is not always used to store integers. If we want to have a queue that store double data, or some user-defined data, then this queue need to be changed and recompiled. The generics in Java can be used to define a generic queue that can be used for any data type. Below is the complete code of MyQueue class that is generic and use Linked list (self-defined) to store the data.
The queue has minimal functionality, but it is a good design.

class QueueEmptyException extends Exception{
    String str;
    public QueueEmptyException(){}
    public QueueEmptyException(String s)
    {
        str = s;
    }
    public String toString()
    {
        return ("Queue is Empty :"+str);
    }
}
class MyQueue<T>
{
    class Node
    {
        T data;
        Node next;
        Node(T x){
            data = x;
            next = null;
        }
    }
    Node front, rear;
    public MyQueue(){
        front = rear = null;
    }
    public boolean isEmpty(){
        return (front == null);
    }
    public T remove() throws QueueEmptyException{
        if(isEmpty())
            throw new QueueEmptyException("FROM REMOVE FUN");
        Node temp = front;
        front = front.next;
        return temp.data;
    }
    // INSERT AT THE REAR END
    public void insert(T data)
    {
        Node temp = new Node(data);
        if(isEmpty())
        {
            front = rear = temp;
        }
        else
        {
            rear.next = temp;
            rear = temp;
        }
    }
}

Let us not few things from above implementation:

1. The generic type of a class is also visible inside the child-classes.
2. All the three operations of MyQueue class takes constant time. This is true for array implementation of queue also. The insert and remove operation in a queue should take O(1) time in a good implementation.
3. Inside the remove and insert functions, we have called function isEmpty(), where ever we want to check if the queue is empty or not. If we put a hard-code check inside remove and insert functions, then we need to make changes at all the places, if the condition of the queue being empty is changed. Ideally, there should be only one place and one function responsible for each task.
4. We do not need to free (or delete) the memory in Java. The memory will be automatically free when the garbage collector runs the next time.