How to implement a queue data structure in Java

We will implement the following six operations for our queue:

enqueue(): This operation adds an element to the end of the queue, much like adding someone to the back of a line.
dequeue(): When this operation is called, it removes and give us the element from the front of the queue, just like the first person leaving the line.
peek(): Using this operation, we can see the element at the front of the queue without actually removing it, similar to looking at the person standing first in the line without asking them to step out.
isEmpty(): This operation checks if the queue is empty. If there’s no one in the line, it returns TRUE, and if there are people, it returns FALSE.
isFull(): This operation checks if the queue is full or has reached its limit. If it’s full, it returns TRUE, and if there’s still space, it returns FALSE.
size(): It tells us how many elements are currently in the queue, giving us the count of people in our line.
clear(): This operation removes all elements from the queue, essentially emptying the line completely.

These operations help manage our queue efficiently.

Implementation

Below is the implementation of the queue data structure to perform the above-mentioned operations. We will use an array data structure to implement the queue.

class Queue {
    // Private members to represent the queue
    private int capacity;
    private int[] queue;
    private int front;
    private int rear;
    private int currentSize;
    // Constructor to initialize the queue with a given capacity
    public Queue(int size) {
        capacity = size;
        queue = new int[capacity];
        front = 0;
        rear = -1;
        currentSize = 0;
    }
    // Method to enqueue an element into the queue
    public void enqueue(int item) {
        if (isFull()) {
            System.out.println("Queue is full. Cannot enqueue element.");
        } else {
            rear++;
            queue[rear] = item;
            currentSize++;
        }
    }
    // Method to dequeue an element from the queue
    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Cannot dequeue element.");
            return Integer.MAX_VALUE; // Returning a sentinel value in case of an empty queue
        }
        int dequeuedItem = queue[front];
        front++;
        currentSize--;
        return dequeuedItem;
    }
    // Method to loos at the front element of the queue
    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Cannot peek element.");
            return Integer.MAX_VALUE; // Returning a sentinel value in case of an empty queue
        }
        return queue[front];
    }
    // Method to check if the queue is empty
    public boolean isEmpty() {
        return currentSize == 0;
    }
    // Method to check if the queue is full
    public boolean isFull() {
        return currentSize == capacity;
    }
    // Method to get the current size of the queue
    public int size() {
        return currentSize;
    }
    // Method to clear the queue
    public void clear() {
        front = 0;
        rear = -1;
        currentSize = 0;
    }
    // Main method for testing the queue class
    
    public static void main(String[] args) {
        System.out.println("Creating a new queue instance...");
        Queue myQueue = new Queue(5);
        System.out.println("Is the queue empty? " + myQueue.isEmpty());
        System.out.println("Adding elements to the queue:");
        myQueue.enqueue(15);
        myQueue.enqueue(25);
        myQueue.enqueue(35);
        System.out.println("Peek at the front element: " + myQueue.peek());
        System.out.println("Current size of the queue: " + myQueue.size());
        System.out.println("Removing elements from the queue:");
        System.out.println("Dequeued: " + myQueue.dequeue());
        System.out.println("Dequeued: " + myQueue.dequeue());
        System.out.println("Is the queue empty? " + myQueue.isEmpty());
        System.out.println("Clearing the queue...");
        myQueue.clear();
        System.out.println("Current size of the queue: " + myQueue.size());
    }
}

Code explanation

We created a Queue class to implement the queue data structure, which contains the following functions:

Lines 11–17: The constructor of Queue class sets all necessary variables, i.e., capacity to set the capacity of the queue, two pointers, front and rare to keep track of both ends of the queue and currentSize to store the current number of elements in the queue. It then creates a queue of size capacity.
Lines 20–28: The enqueue() function takes an element, adds it to the rear position in the array, and increments the currentSize.
Lines 31–41: The dequeue() function returns the element at the front of the queue and reduces the currentSize.
Lines 44–50: The peek() function retrieves the element at the front of the queue without removing it.
Lines 53–55: The isEmpty() function returns TRUE if the queue is empty; otherwise, it returns FALSE.
Lines 58–60: The isFull() function returns TRUE if the queue is full; otherwise, it returns FALSE.
Lines 63–65: The size() function returns the current size of the queue.
Lines 68–72: The clear() function cleans the array by setting pointers to its initial states and currentSize to 0.

Applications of a queue

There are several real-world use cases:

Task scheduling:: Operating systems use queues to schedule and manage processes.
Print queue:: This helps manage print jobs, ensuring they are processed in the order received.
Breadth-first search (BFS) in graphs: It is fundamental for graph traversal, exploring nodes level by level.
Order processing in e-commerce: It manages orders, processing them in the order received.
Buffer in networking: It temporarily stores data packets to manage the data flow in networking.
Task management in multithreading: It efficiently manages tasks in multithreading environments.

Queues provide an efficient and organized way to handle tasks, ensuring they are processed in a structured order. Whether managing processes in an operating system, handling print jobs, exploring graphs, or processing orders in e-commerce, queues’ versatility makes them indispensable in various domains.

Conclusion

Understanding the implementation of a queue and recognizing its diverse applications is crucial for developers. With their simplicity and efficiency, Queues play a vital role in numerous computing scenarios. Whether dealing with process scheduling, network communication, or algorithmic problem-solving, a solid grasp of queue implementations is invaluable. As we explore more complex data structures and algorithms, the principles learned from implementing a queue will undoubtedly contribute to our proficiency as developers.

Free Resources