Implementing Generic Queues in Java using Linked List

Last updated on 13th April 2021

In data structures, a queue is a collection of elements arranged in a sequence where each element is linked to its previous and next element. Elements are added to one end of the queue, also known as the back of the queue, and come out through the other end, which is the front (or top) of the queue. This method of adding and removing elements is known as First In First Out (FIFO). You can implement a Queue data structure in Java either using arrays or using linked lists. This article explains implementing a generic queue in Java using a linked list. A generic queue can hold elements of any non-primitive data type such as Strings, Arrays, classes and interfaces.

Queue

Features & Characteristics of a Linked Queue

The following are the key feature and characteristics of a queue that is implemented using linked list.

  • The elements of a queue are stored in Nodes. A node consists of a value and a pointer to the next node in the queue.
  • The queue maintains two pointers - front and rear. The front pointer points to the first element in the queue and rear pointer points to the last element of the queue.
  • When a queue is empty, the front and rear pointers point to null.
  • Elements are removed from the front of the queue and inserted to the rear of the queue.

  • Some of the basic operations you can perform on a queue are:

    • Enqueue - Insert elements to the back of the queue.
    • Dequeue - Remove elements from the front of the queue
    • Peak - Get the first element of the queue without removing it.
    • Size - Return the number of elements in the queue.
    • isEmpty - To check if queue is empty.

    Generic Type Implementation of a Queue

    The following LinkedQueue class is a generic class implemention of a queue that holds elements of type E.

    The LinkedQueue class contains a sub class Node which represents each element or node of the queue. A node contains the data and a pointer to the next node/element in the queue.

    The following private variables are defined in the LinkedQueue class.

    • count - maintains the count of elements in the queue.
    • front - contains the first element of the queue.
    • rear - contains the last element of the queue

    When the queue is empty, front and rear are null. To add an element to the empty queue, you create a new node and then set the front and rear variables to that new node. When you add elements to a queue that is not empty, first you have to set the next node pointer of the last element in the queue(i.e, rear.next) to point to the new node and then change the rear variable to contain the new node.

    The steps for dequeue operation are.

    • Check if the queue is not empty.
    • Get the value of the front node.
    • Change the front node to the next node in the queue ( front = front.next).
    • If the next node in the queue is null, i.e, you have dequeued the last element, then set rear to null.

    The count variable in incremented or decremented for enqueue and dequeue operations respectively and the size method returns the count.

    Peak method returns the value of the front node.

    LinkedQueue.java 
    public class LinkedQueue<E> {

  private class Node<E> {
    E value;
    Node<E> next;

    Node(E value, Node<E> next) {
      this.value = value;
      this.next = next;
    }
  }
 
  private int count;
  private Node<E> front;
  private Node<E> rear;

  public LinkedQueue() {
     front = rear = null;
     count = 0;
  }

   public void enqueue(E value) {
        if (rear != null) {
            rear.next = new Node(value, null);
            rear = rear.next;
        } else {
            rear = new Node(value, null);
            front = rear;
        }
        count++;
    }
    
     public E dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Cannot dequeue - Queue is empty");
        }

        E value = front.value;
        front = front.next;
        count--;

        if (front == null) {
            rear = null;
        }

        return value;
    }
    

public boolean isEmpty() {
        return front == null;
    }
   
public E peek() {
        return front.value;
    }

 public int size() {
        return count;
    }
    
}

    Invoking and Instantiating the Generic Queue

    The LinkedQueue can hold elements of any non-primitive data type. For example, you can create a queue of Strings as below.

    LinkedQueue linkedQueue = new LinkedQueue();

    Below is an example that shows various operations you can perform on the queue.

    public class Main {

    public static void main(String[] args) {
       try {
            // Create a queue of strings.
            LinkedQueue linkedQueue = new LinkedQueue();
            
            // Add two strings to the queue.
            linkedQueue.enqueue("A");
            linkedQueue.enqueue("B");
            
            // Print the size of the queue, which is 2.
            System.out.println(linkedQueue.size());
            
            //Remove an element fron the queue. This will print the first element which is A.
            System.out.println(linkedQueue.dequeue());
            
            //Check the next element in the queue without removing. Prints B.
            System.out.println(linkedQueue.peek());
            
            // Print the size of the queue. Prints 1 as the queue contains one string - B.
            System.out.println(linkedQueue.size());
      }
    }
}

    The purpose of this program is to understand the concepts of Queue data structure and some of the basic operations you can perform on a queue. Normally, when you require a queue, it is convenient to use the Queue interface from java.util package.


Post a comment

Comments

Nothing yet..be the first to share wisdom.