Custom Queue Implementation in Java

In this article, we will create a custom implementation of Queue data structure in Java. In the course, we will perform different queue operations such as enQueue(), deQueue(), etc. We will also check the time complexity of these different operations.

What is Queue

A queue is an ordered list in which insertions are done at one end(rear) and deletions are done at the other end(front). The element which is inserted first is the first element that is deleted. Hence, it is called First in First out(FIFO).

Queue Operations

enQueue(): Inserts an element at the end of the Queue.

deQueue(): Removes and returns the element at the front of the Queue.

front(): Returns the element at front without removing it.

queueSize(): Returns the number of elements stored in the queue.

isEmpty(): Indicates whether no elements are stored in the queue or not.

Queue Implementation

We will be using linked list for the implementation of our custom queue. Below are the advantages of using linked list for queue implementation:

• Grows and shrinks gracefully.
• Every operation takes constant time O(1).
• Every operation uses extra space and time to deal wih references.

While using linked list for the queue implementation, EnQueue operation is implemented by inserting element at the end of the list and DeQueue operation is implemented by deleting an element from the beginning of the list.

You can visit my previous article for custom implementation of linked list in Java.

The front of Q is the head and rear of the Q is tail due to the remove operation. Removal of an element happens from the front of the Q and if the linked list tail is the front of a queue then how we going to remove the front element of a Q(the tail of linked list) as the linked list does not allow to remove the tail of it at a constant time O(1). once we remove the tail then there is no way to point to the element that was before a tail in a singly linked list unless we have an extra pointer.

Queue Class Template

Let us define our class template for the Queue implementation.

public class CustomQueue {

    private int length;
    private Node front, rear;

    public CustomQueue(){
        length = 0;
        front = rear = null;
    }

    public void enqueue(int data){
        
    }

    public int dequeue() throws Exception {
        
    }

    public int first() throws Exception {
        
    }

    public  boolean isEmpty(){
        return length == 0;
    }

    public int size(){
        return length;
    }
}

front and rear instance variable are the linked list node that holds the data and a reference to the next node.

public class Node {

    private int data;
    private Node nextNode;

    public Node(int data){
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNextNode() {
        return nextNode;
    }

    public void setNextNode(Node nextNode) {
        this.nextNode = nextNode;
    }
}

Queue EnQueue Operation

Incase for the first insert operation, we simply assign that node as a front node. Else, we keep enqueuing the new node as a last node of the Queue as this is expected behavior of a queue.The last node of the queue becomes the rear node of the queue.

public void enqueue(int data){
        Node node = new Node(data);
        if(isEmpty()){
            front = node;
        }else {
            rear.setNextNode(node);
        }
        rear = node;
        length++;
    }

Queue DeQueue Operation

DeQueue operation is implemented by deleting an element from the beginning of the list. After this operation the next node of the front node becomes the front of the queue.

public int dequeue() throws Exception {
        if(isEmpty()){
            throw new Exception("Empty queue");
        }
        int result = front.getData();
        front = front.getNextNode();
        length--;
        if(isEmpty()){
            rear = null;
        }
        return result;
    }

Queue Front Operation

This operation returns the element at front without removing it.

public int first() throws Exception {
        if(isEmpty()){
            throw new Exception("Queue is empty");
        }
        return front.getData();
    }

Queue Time Complexity

Let n be the number of elements in the stack.

Space Complexity : O(n)
Time complexity of enQueue() : O(1)
Time complexity of deQueue() : O(1)
Time complexity of isEmpty() : O(1)
Time complexity of isFull() : O(1)

Other Queue Types

Priority Queue

Priority queue is a special type of Queue in Java in which all the elements are stored as per the priority of the elements. This priority is defined based on the natural ordering or based on a custom comparator defined at the time of creation of the queue.

The front element in the priority queue is the highest priority element and the rear element is the lowest priority element. Hence, it does not follow First In First Out(FIFO) principle rather the value is dequeued based on the priority of the element. Once, the highestt priority element is dequeued, the next element dequeued will be the highest priority element amongst the remaining elements.

This data structure is useful in CPU scheduling algorithms.

Blocking Queue

Blocking queue is a thread-safe implementation of Queue data structure. So, whenever a thread is trying to remove an element from an empty queue then the thread gets blocked untill the queue becomes non-empty. Similarly, a thread trying to add an element waits for space to become available in the queue.

This feature of blocking queue can be used for a custom thread pool implementation.

Conclusion

In this article, we created a custom implementation of Queue data structure in Java. In the course, we performed different queue operations such as enQueue(), deQueue(), etc. We also checked the time complexity of these different operations.