Implementing a Queue in Java: A Step-by-Step Guide

A Queue is a fundamental data structure that follows the FIFO (First-In-First-Out) principle. It allows elements to be inserted at the end (rear) and removed from the front. In this guide, we will walk through the implementation of a Queue in Java using a linked list approach. We’ll cover how to create a Queue class and implement core operations such as enqueue, dequeue, peek, isEmpty, size, and demonstrate its usage with sample operations.

Understanding the Queue Structure

Node Class

First, we define a Node class to represent each element in the queue. Each node contains a data element and a reference to the next node in the queue.

class Node<T> {
    T data;
    Node<T> next;

    Node(T data) {
        this.data = data;
        this.next = null;
    }
}

Queue Class

Next, we implement the Queue class using the linked list structure provided by the Node class.

import java.util.NoSuchElementException;

public class Queue<T> {

    private Node<T> front;  // Front of the queue
    private Node<T> rear;   // Rear of the queue
    private int size;       // Size of the queue

    public Queue() {
        front = null;
        rear = null;
        size = 0;
    }

    // Method to add an element to the rear of the queue
    public void enqueue(T data) {
        Node<T> newNode = new Node<>(data);
        if (isEmpty()) {
            front = newNode;  // If queue is empty, new node is both front and rear
        } else {
            rear.next = newNode;  // Link the current rear to the new node
        }
        rear = newNode;  // Update the rear to be the new node
        size++;
    }

    // Method to remove and return the element from the front of the queue
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty. Cannot dequeue.");
        }
        T data = front.data;  // Retrieve data at the front
        front = front.next;  // Move front pointer to the next node
        if (front == null) {
            rear = null;  // If front becomes null, queue is empty
        }
        size--;
        return data;
    }

    // Method to return the element at the front of the queue without removing it
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty. Cannot peek.");
        }
        return front.data;  // Return data at the front
    }

    // Method to check if the queue is empty
    public boolean isEmpty() {
        return size == 0;
    }

    // Method to return the size of the queue
    public int size() {
        return size;
    }

    // Method to convert the queue to a string representation
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node<T> current = front;
        while (current != null) {
            sb.append(current.data).append(" ");
            current = current.next;
        }
        return sb.toString();
    }

    // Main method for testing the queue
    public static void main(String[] args) {
        Queue<Integer> queue = new Queue<>();

        // Enqueue elements
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        System.out.println("Queue after enqueues: " + queue);

        // Dequeue elements
        System.out.println("Dequeued: " + queue.dequeue());
        System.out.println("Queue after dequeue: " + queue);

        // Peek at the front element
        System.out.println("Front element: " + queue.peek());

        // Check if the queue is empty
        System.out.println("Is queue empty? " + queue.isEmpty());

        // Get the size of the queue
        System.out.println("Queue size: " + queue.size());

        // Dequeue remaining elements
        System.out.println("Dequeued: " + queue.dequeue());
        System.out.println("Dequeued: " + queue.dequeue());
        System.out.println("Is queue empty? " + queue.isEmpty());
    }
}

Explaining the Queue Implementation

Node Class

• Node: Represents a node in the linked list structure.
• data: Holds the actual data of type T.
• next: Points to the next node in the queue.

Queue Class

• front: Points to the front of the queue.
• rear: Points to the rear of the queue.
• size: Tracks the number of elements in the queue.

Constructor

• Initializes an empty queue with front and rear set to null, and size to 0.

Methods

1. enqueue(T data):

• Adds an element to the rear of the queue.
• Updates rear to point to the new node.
• If the queue is empty, updates front to the new node.

1. dequeue():

• Removes and returns the element from the front of the queue.
• Updates front to point to the next node.
• If front becomes null, updates rear to null indicating the queue is empty.

1. peek():

• Returns the element at the front of the queue without removing it.
• Throws NoSuchElementException if the queue is empty.

1. isEmpty():

• Checks if the queue is empty.
• Returns true if size is 0, otherwise false.

1. size():

• Returns the current size of the queue.

1. toString():

• Converts the queue to a string representation.
• Useful for debugging and displaying the contents of the queue.

Main Method

• Demonstrates various operations on the queue:
• Enqueueing elements.
• Dequeueing elements.
• Peeking at the front element.
• Checking if the queue is empty.
• Getting the size of the queue.

Running the Code

To run this code:

1. Copy the code into a file named Queue.java.
2. Compile it using javac Queue.java.
3. Run it using java Queue.

Output

The program demonstrates the queue operations and prints:

Queue after enqueues: 10 20 30 
Dequeued: 10
Queue after dequeue: 20 30 
Front element: 20
Is queue empty? false
Queue size: 2
Dequeued: 20
Dequeued: 30
Is queue empty? true

Conclusion

Implementing a queue from scratch helps in understanding the fundamental concepts of data structures and algorithms. This custom queue class provides all basic operations required for FIFO processing of elements. Whether you’re preparing for interviews or working on projects, mastering these foundational concepts is essential for efficient software development.

Feel free to modify the code, add more functionalities, or integrate it with other data structures. Experimenting with such implementations will enhance your understanding and problem-solving skills in programming.

---

I hope this guide helps you understand and implement a Queue in Java effectively! If you have any questions or suggestions, feel free to leave a comment below. Happy coding!