How to Implement a Queue Using Arrays

Introduction

Queues are a fundamental data structure in computer science, often used in various applications such as scheduling processes and managing tasks. In this guide, you will learn how to implement a queue using arrays in Java. By the end of this article, you’ll understand how queues work, their core operations, and how to code them efficiently using arrays.

What is a Queue?

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means that the element that is added first will be removed first. Think of a queue as a line of people waiting to buy tickets; the person at the front of the line gets served first.

Key Operations of a Queue:

• Enqueue: Add an element to the end of the queue.
• Dequeue: Remove an element from the front of the queue.
• Peek/Front: Retrieve the front element without removing it.
• IsEmpty: Check if the queue is empty.
• IsFull: Check if the queue is full (for a fixed-size queue).

How to Implement a Queue Using Arrays in Java

Let’s dive into the implementation of a queue using arrays in Java. We’ll create a class called Queue that manages these operations.

Step 1: Define the Queue Class

Create a class named Queue and define variables for the array, front, rear, and size.

class Queue {
    int[] arr;
    int front;
    int rear;
    int size;
    int capacity;

    Queue(int capacity) {
        this.capacity = capacity;
        arr = new int[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }
}

Step 2: Enqueue Operation

The enqueue method adds an element to the end of the queue. Check if the queue is full before adding an element.

void enqueue(int value) {
    if (isFull()) {
        System.out.println("Queue is full. Cannot enqueue " + value);
        return;
    }
    rear = (rear + 1) % capacity;
    arr[rear] = value;
    size++;
    System.out.println(value + " enqueued to the queue.");
}

Step 3: Dequeue Operation

The dequeue method removes an element from the front of the queue. Check if the queue is empty before removing an element.

int dequeue() {
    if (isEmpty()) {
        System.out.println("Queue is empty. Cannot dequeue.");
        return Integer.MIN_VALUE;
    }
    int dequeuedValue = arr[front];
    front = (front + 1) % capacity;
    size--;
    System.out.println(dequeuedValue + " dequeued from the queue.");
    return dequeuedValue;
}

Step 4: Peek Operation

The peek method retrieves the front element without removing it.

int peek() {
    if (isEmpty()) {
        System.out.println("Queue is empty. No elements to peek.");
        return Integer.MIN_VALUE;
    }
    return arr[front];
}

Step 5: Utility Methods – isEmpty and isFull

These methods help to check if the queue is empty or full.

boolean isEmpty() {
    return size == 0;
}

boolean isFull() {
    return size == capacity;
}

Step 6: Main Method to Test the Queue

Now, let’s add a main method to test our queue implementation.

public class Main {
    public static void main(String[] args) {
        Queue queue = new Queue(5);

        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);
        queue.enqueue(50);

        System.out.println("Front element is: " + queue.peek());

        queue.dequeue();
        queue.dequeue();

        queue.enqueue(60);

        System.out.println("Front element is: " + queue.peek());
    }
}

Output:

10 enqueued to the queue.
20 enqueued to the queue.
30 enqueued to the queue.
40 enqueued to the queue.
50 enqueued to the queue.
Front element is: 10
10 dequeued from the queue.
20 dequeued from the queue.
60 enqueued to the queue.
Front element is: 30

Explanation of the Queue Operations

• Enqueue: Adds elements to the rear and adjusts the rear index in a circular manner using modulo arithmetic.
• Dequeue: Removes elements from the front and adjusts the front index similarly.
• Peek: Returns the element at the front without removing it.
• IsEmpty: Returns true if size is zero.
• IsFull: Returns true if size equals the queue’s capacity.

Benefits of Using Arrays for Queue Implementation

• Fixed Size: Using arrays allows for a fixed-size queue, which can be advantageous when memory constraints are known.
• Speed: Array-based implementations are fast, as they provide direct indexing for accessing elements.
• Simplicity: Array-based queues are simpler to implement compared to dynamic structures like linked lists.

Limitations of Array-Based Queues

• Fixed Capacity: Once the capacity is reached, you cannot add more elements unless you resize the array.
• Memory Wastage: If the queue is sparsely populated, memory can be wasted.

Conclusion

Implementing a queue using arrays in Java is a straightforward process once you understand the FIFO concept and core operations. By following this guide, you now have a working queue implementation that is suitable for small-scale applications. For more complex use cases, you might consider dynamic data structures like linked lists.