1. Introduction

A Queue is a First In First Out (FIFO) data structure, which ensures that the element added first is the first one to be removed. The primary operations associated with a queue are enqueue (adding an item) and dequeue (removing the foremost item). Using a linked list to implement a queue provides the advantage of dynamic size adjustments. In this blog post, we will showcase how to implement a queue using a linked list in Java.

2. Program Steps

1. Define a Node class that will represent each element in the linked list.

2. Create a Queue class that will utilize the Node class to store elements.

3. Implement the following main queue operations:

– enqueue: Add an element to the end of the queue.

– dequeue: Remove and return the front element from the queue.

– peek: View the front element without removing it.

– isEmpty: Check if the queue is empty.

4. Demonstrate the queue operations in the main function.

3. Code Program

class Queue<T> {

    private Node<T> front;
    private Node<T> rear;

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

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

    public void enqueue(T data) {
        Node<T> newNode = new Node<>(data);
        if (rear != null) {
            rear.next = newNode;
        }
        rear = newNode;
        if (front == null) {
            front = rear;
        }
    }

    public T dequeue() {
        if (front == null) {
            System.out.println("Queue is empty. Cannot dequeue.");
            return null;
        }
        T item = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return item;
    }

    public T peek() {
        if (front == null) {
            System.out.println("Queue is empty. Nothing to peek.");
            return null;
        }
        return front.data;
    }

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

    public static void main(String[] args) {
        Queue<Integer> queue = new Queue<>();
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        System.out.println("Front element: " + queue.peek());
        System.out.println("Dequeued element: " + queue.dequeue());
        System.out.println("Is queue empty? " + queue.isEmpty());
    }
}

Output:

Front element: 10
Dequeued element: 10
Is queue empty? false

4. Step By Step Explanation

1. We start by defining a Node class that holds the data of the node and a reference to the next node.

2. The Queue class maintains two references: front and rear, which point to the first and last elements of the queue, respectively.

3. The enqueue method creates a new node and adds it to the end of the queue. It also checks and updates the front reference if the queue was previously empty.

4. The dequeue method removes the node at the front of the queue and returns its data. It updates both front and rear references as needed.

5. The peek method returns the data of the foremost element without removing it.

6. The isEmpty method checks if the queue has any nodes or not.

7. In the main function, we illustrate the queue's functionality by adding three integers, peeking the frontmost one, dequeuing it, and finally verifying if the queue is empty.