Java Data Structures and Algorithms for Beginners

Queue Data Structure

Definition and Concepts

A queue is a linear data structure that operates on the First In, First Out (FIFO) principle. This means that the first element added to the queue is the first one to be removed. You can visualize a queue as a line of people waiting at a ticket counter, where the person who arrives first is served first. The primary operations of a queue include enqueue, which adds an element to the rear of the queue, and dequeue, which removes and returns the element at the front. Additional operations include peek, which views the front element without removing it, and isEmpty, which checks if the queue is empty. Queues are essential for managing data in a sequential, order-preserving manner.

Why Use It?

A queue is useful when you need to process data in the order it was received. It ensures fairness by maintaining the sequence of elements, making it ideal for tasks that require sequential processing or scheduling. Queues are efficient because they restrict operations to two ends: the front for removal and the rear for addition, simplifying data management.

Where to Use? (Real-Life Examples)

• Task Scheduling in Operating Systems: Operating systems use queues to manage processes waiting for CPU time, ensuring each process is executed in the order it was submitted.
• Print Job Management: Printers use queues to handle multiple print jobs, processing them in the order they were received.
• Customer Service Systems: Call centers or ticket counters use queues to serve customers in the order of their arrival.
• Breadth-First Search (BFS) in Graphs: Queues are used in algorithms like BFS to explore nodes level by level in a graph or tree.

Explain Operations

• Enqueue: This operation adds an element to the rear of the queue. It has a time complexity of O(1).
• Dequeue: This operation removes and returns the front element of the queue. If the queue is empty, it may throw an exception or return null. It has a time complexity of O(1).
• Peek: This operation returns the front element without removing it. It has a time complexity of O(1).
• isEmpty: This operation checks whether the queue is empty. It has a time complexity of O(1).
• Size: This operation returns the number of elements currently in the queue. It has a time complexity of O(1).

Java Implementation

The following Java code implements a queue using an array with a fixed size.

public class Queue {
    private int maxSize; // Represents the maximum size of the queue
    private int[] queueArray; // Array to store the queue elements
    private int front; // Index of the front element
    private int rear; // Index where the next element will be added
    private int currentSize; // Number of elements in the queue

    // Constructor to initialize the queue with a given size
    public Queue(int size) {
        maxSize = size;
        queueArray = new int[size];
        front = 0; // Front starts at index 0
        rear = -1; // Rear starts before the first element
        currentSize = 0; // Queue is initially empty
    }

    // Enqueue: Adds an element to the rear of the queue
    public void enqueue(int value) {
        if (currentSize < maxSize) { // Checks if the queue is not full
            rear = (rear + 1) % maxSize; // Increments rear (circularly)
            queueArray[rear] = value; // Adds the value at rear
            currentSize++; // Increments the size
        } else {
            throw new IllegalStateException("The queue is full.");
        }
    }

    // Dequeue: Removes and returns the front element
    public int dequeue() {
        if (isEmpty()) { // Checks if the queue is empty
            throw new IllegalStateException("The queue is empty.");
        }
        int value = queueArray[front]; // Retrieves the front element
        front = (front + 1) % maxSize; // Moves front to the next element (circularly)
        currentSize--; // Decrements the size
        return value;
    }

    // Peek: Returns the front element without removing it
    public int peek() {
        if (isEmpty()) { // Checks if the queue is empty
            throw new IllegalStateException("The queue is empty.");
        }
        return queueArray[front];
    }

    // isEmpty: Checks if the queue is empty
    public boolean isEmpty() {
        return (currentSize == 0);
    }

    // Size: Returns the number of elements in the queue
    public int size() {
        return currentSize;
    }
}

How It Works

1. Initialization: The constructor initializes an array of size maxSize, sets front to 0, rear to -1, and currentSize to 0, indicating an empty queue.
2. Enqueue Operation:
   • The method checks if the queue is not full by comparing currentSize to maxSize.
   • It increments rear using modulo (% maxSize) to support a circular queue, adds the value to queueArray[rear], and increments currentSize.
   • If the queue is full, it throws an exception.
3. Dequeue Operation:
   • The method verifies that the queue is not empty using isEmpty().
   • It retrieves the value at queueArray[front], moves front to the next position using modulo, decrements currentSize, and returns the value.
   • If the queue is empty, it throws an exception.
4. Peek Operation: The method returns the value at queueArray[front] without modifying front or currentSize.
5. isEmpty Operation: The method returns true if currentSize equals 0, indicating an empty queue, and false otherwise.
6. Size Operation: The method returns currentSize, which represents the number of elements in the queue.

Complexity Analysis Table

Key Differences / Notes

• Array-Based vs. Linked List-Based Queue:
  • The array-based queue, as implemented above, has a fixed size and offers O(1) access but is limited by its maximum size.
  • A linked list-based queue supports dynamic sizing but may involve additional overhead for node creation and deletion.
• Circular Queue: The implementation above uses a circular queue to optimize space usage, allowing the array to wrap around when rear or front reaches the end.
• Thread Safety: The provided implementation is not thread-safe. For concurrent applications, consider using Java’s ConcurrentLinkedQueue or ArrayBlockingQueue.
• Java’s Built-in Options: Java provides Queue as an interface in java.util, with implementations like LinkedList and ArrayDeque. The ArrayDeque is recommended for better performance in most cases.

✅ Tip: Use a circular queue, as shown in the implementation, to make efficient use of array space and avoid wasting memory when elements are dequeued.

⚠ Warning: An array-based queue can overflow if you exceed its maxSize. Ensure the queue size is sufficient for your application, or consider a linked list-based queue for dynamic sizing.

Exercises

1. Print Job Simulator: Write a Java program that simulates a printer queue using the queue implementation above. Allow users to enqueue print jobs (represented as strings) and dequeue them in order, printing each job as it is processed.
2. Queue Reversal: Create a program that reverses the elements of a queue using a stack. Enqueue a set of numbers, reverse them, and print the reversed queue.
3. Circular Queue Test: Extend the queue implementation to handle edge cases, such as enqueueing and dequeuing in a loop, and test it with a sequence of operations to verify circular behavior.
4. Queue-Based BFS: Implement a simple Breadth-First Search (BFS) algorithm for a graph using the queue. Represent the graph as an adjacency list and print the nodes visited in BFS order.
5. Ticket Counter Simulation: Simulate a ticket counter system where customers (represented by names) join a queue and are served in order. Allow users to enqueue customers, dequeue them, and display the current queue size.