Java Program to Implement a Queue Using Linked List

Introduction

A queue is a linear data structure that follows the First In, First Out (FIFO) principle, where elements are added (enqueued) to the rear of the queue and removed (dequeued) from the front. Unlike an array-based implementation, a linked list-based queue dynamically adjusts its size as elements are added or removed. This guide will walk you through writing a Java program that implements a queue using a singly linked list.

Problem Statement

Create a Java program that:

• Implements a queue using a linked list.
• Provides methods to perform standard queue operations: enqueue, dequeue, peek, and isEmpty.
• Displays the queue contents after various operations.

Example:

• Input: Enqueue elements: 10, 20, 30
• Operations: enqueue(40), dequeue(), peek()
• Output:
  • After enqueuing 40: 10 -> 20 -> 30 -> 40 -> null
  • After dequeuing: 20 -> 30 -> 40 -> null
  • Peeked element: 20

Solution Steps

1. Create the Node Structure: Define a Node class to represent each element in the queue.
2. Create the Queue Structure: Define a Queue class to manage the queue using a linked list, including methods for standard queue operations.
3. Implement Queue Operations: Implement methods to enqueue elements into the queue, dequeue elements from the queue, peek at the front element, and check if the queue is empty.
4. Display the Queue: Output the queue’s contents after performing various operations.

Java Program

// Java Program to Implement a Queue Using Linked List
// Author: https://www.rameshfadatare.com/

// Step 1: Define the Node class to represent each element in the queue
class Node {
    int data;
    Node next;

    // Constructor to initialize the node
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// Step 2: Define the Queue class to manage the queue operations using a linked list
class Queue {
    private Node front, rear;

    // Constructor to initialize the queue (initially empty)
    public Queue() {
        this.front = this.rear = null;
    }

    // Step 3: Method to enqueue an element into the queue
    public void enqueue(int value) {
        // Create a new node with the given value
        Node newNode = new Node(value);

        // If the queue is empty, both front and rear point to the new node
        if (this.rear == null) {
            this.front = this.rear = newNode;
            System.out.println("Enqueued " + value + " into the queue.");
            return;
        }

        // Otherwise, add the new node at the end of the queue and change the rear
        this.rear.next = newNode;
        this.rear = newNode;
        System.out.println("Enqueued " + value + " into the queue.");
    }

    // Step 4: Method to dequeue an element from the queue
    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Unable to dequeue.");
            return -1; // Return a sentinel value indicating the queue is empty
        }

        // Move the front pointer to the next node
        int dequeuedValue = this.front.data;
        this.front = this.front.next;

        // If the front becomes null, then the queue is empty, so set rear to null
        if (this.front == null) {
            this.rear = null;
        }

        System.out.println("Dequeued " + dequeuedValue + " from the queue.");
        return dequeuedValue;
    }

    // Step 5: Method to peek at the front element of the queue
    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Nothing to peek.");
            return -1; // Return a sentinel value indicating the queue is empty
        } else {
            System.out.println("Peeked at the front element: " + this.front.data);
            return this.front.data;
        }
    }

    // Step 6: Method to check if the queue is empty
    public boolean isEmpty() {
        return (this.front == null);
    }

    // Step 7: Method to display the contents of the queue
    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is empty.");
        } else {
            System.out.print("Queue contents: ");
            Node current = front;
            while (current != null) {
                System.out.print(current.data + " -> ");
                current = current.next;
            }
            System.out.println("null");
        }
    }
}

public class QueueDemo {
    public static void main(String[] args) {
        Queue queue = new Queue(); // Create a queue

        // Enqueue elements into the queue
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.display();

        // Enqueue another element
        queue.enqueue(40);
        queue.display();

        // Dequeue an element from the queue
        queue.dequeue();
        queue.display();

        // Peek at the front element
        queue.peek();
        queue.display();

        // Dequeue all elements to test underflow
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue(); // This dequeue should trigger an underflow condition
        queue.display();
    }
}

Explanation

Step 1: Define the Node Class

• The Node class represents a single element in the queue. Each node contains data and a reference to the next node (next).
• The constructor initializes the node with data and sets the next pointer to null.

Step 2: Define the Queue Class

• The Queue class manages the queue operations using a linked list. The class contains two pointers, front and rear, which point to the first and last nodes in the queue, respectively.
• The queue is initialized as empty, with both front and rear set to null.

Step 3: Enqueue an Element into the Queue

• The enqueue() method adds a new node to the rear of the queue:
  • A new node is created with the given value.
  • If the queue is empty, both front and rear point to the new node.
  • Otherwise, the next pointer of the rear node is updated to point to the new node, and rear is updated to the new node.

Step 4: Dequeue an Element from the Queue

• The dequeue() method removes and returns the front element of the queue:
  • If the queue is empty, an underflow message is displayed.
  • Otherwise, the front pointer is updated to point to the next node, and the data of the dequeued node is returned.
  • If the queue becomes empty after the dequeue operation, rear is set to null.

Step 5: Peek at the Front Element of the Queue

• The peek() method returns the front element without removing it:
  • If the queue is empty, an appropriate message is displayed.
  • Otherwise, the front element’s data is returned.

Step 6: Check if the Queue is Empty

• The isEmpty() method checks if the queue is empty by verifying if front is null.

Step 7: Display the Queue Contents

• The display() method prints all elements currently in the queue:
  • The queue is traversed from the front to the rear, printing each element’s data.

Output Example

Enqueued 10 into the queue.
Enqueued 20 into the queue.
Enqueued 30 into the queue.
Queue contents: 10 -> 20 -> 30 -> null
Enqueued 40 into the queue.
Queue contents: 10 -> 20 -> 30 -> 40 -> null
Dequeued 10 from the queue.
Queue contents: 20 -> 30 -> 40 -> null
Peeked at the front element: 20
Queue contents: 20 -> 30 -> 40 -> null
Dequeued 20 from the queue.
Dequeued 30 from the queue.
Dequeued 40 from the queue.
Queue is empty. Unable to dequeue.
Queue is empty.

Conclusion

This Java program demonstrates how to implement a queue using a linked list, including handling underflow conditions when attempting to dequeue from an empty queue. The program efficiently manages queue operations, providing dynamic growth and shrinkage, unlike array-based queues. This exercise is valuable for understanding how to implement and manipulate queues using linked lists in Java programming.