Queue Implementation in Java

1. Introduction

A queue is a linear data structure that follows the First In First Out (FIFO) principle. This means that the first element added to the queue will be the first element to be removed. Queues are commonly used in algorithms, task scheduling, and for operations that require a first-come, first-served ordering.

2. Implementation Steps

1. Define a Queue class.

2. Within the class:

a. Declare an array of a fixed size or use an ArrayList to store the queue elements.

b. Declare variables front and rear to keep track of the beginning and end of the queue.

c. Provide methods like enqueue(), dequeue(), peek(), and isEmpty().

3. Create an instance of the queue class and perform operations to demonstrate its functionality.

3. Implementation in Java

public class Queue<T> {
    private int front;  // To keep track of the beginning of the queue
    private int rear;  // To keep track of the end of the queue
    private final int capacity = 100;  // Maximum size of the queue
    private Object[] queue;
    // Constructor
    public Queue() {
        front = -1;
        rear = -1;
        queue = new Object[capacity];
    }
    // Check if the queue is empty
    public boolean isEmpty() {
        return front == -1;
    }
    // Add element to the queue
    public void enqueue(T data) {
        if ((rear + 1) % capacity == front) {
            System.out.println("Queue is full. Can't enqueue the data.");
            return;
        }
        if (isEmpty()) {
            front = rear = 0;
        } else {
            rear = (rear + 1) % capacity;
        }
        queue[rear] = data;
    }
    // Remove and return front element from the queue
    public T dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Can't dequeue.");
            return null;
        }
        T data = (T) queue[front];
        if (front == rear) {
            front = rear = -1;
        } else {
            front = (front + 1) % capacity;
        }
        return data;
    }
    // View front element without removing it
    public T peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Nothing to peek.");
            return null;
        }
        return (T) queue[front];
    }
    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());  // Outputs 10
        System.out.println("Dequeued element: " + queue.dequeue());  // Outputs 10
        System.out.println("Front element after dequeue: " + queue.peek());  // Outputs 20
    }
}

Output:

Front element: 10
Dequeued element: 10
Front element after dequeue: 20

Explanation:

1. A generic Queue class is defined. This allows us to use the queue with any data type.

2. Arrays queue of Objects and variables front and rear are declared to store queue elements and track the beginning and end of the queue respectively.

3. The isEmpty() method checks whether the queue is empty by comparing the front variable with -1.

4. The enqueue() method adds an element to the end of the queue. It checks for overflow (when the queue is full) by ensuring that the next position of rear isn't the current front position. This helps in implementing a circular queue.

5. The dequeue() method removes and returns the frontmost element from the queue. It checks for underflow (when the queue is empty) using the isEmpty() method.

6. The peek() method returns the frontmost element without removing it.

7. In the main() method, we create a Queue of Integers, enqueue three elements onto it, and perform some operations to demonstrate its functionality.