Queue Implementation Using Array in DSA Java

Mental Model

A queue is like a line where the first person in is the first person out. We use an array to hold the people in order.

Analogy: Imagine a line at a ticket counter. People join at the end and leave from the front, just like a queue using an array.

front -> [ ] [ ] [ ] [ ] [ ] <- rear
indexes  0   1   2   3   4

Dry Run Walkthrough

Input: Start with empty queue of size 5, enqueue 10, enqueue 20, dequeue, enqueue 30

Goal: Show how elements enter at rear and leave from front using array indexes

Step 1: enqueue 10 at rear index 0

front=0, rear=0, array=[10, null, null, null, null]

Why: First element goes to start of array, front and rear point to it

Step 2: enqueue 20 at rear index 1

front=0, rear=1, array=[10, 20, null, null, null]

Why: Add new element at next rear position

Step 3: dequeue element at front index 0 (remove 10)

front=1, rear=1, array=[10, 20, null, null, null]

Why: Remove front element by moving front pointer forward

Step 4: enqueue 30 at rear index 2

front=1, rear=2, array=[10, 20, 30, null, null]

Why: Add new element at next rear position

Result:

front=1, rear=2, array=[10, 20, 30, null, null]
Queue elements from front to rear: 20 -> 30 -> null

Annotated Code

DSA Java

public class QueueUsingArray {
    private int[] arr;
    private int front, rear, size, capacity;

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

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

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

    public void enqueue(int value) {
        if (isFull()) {
            System.out.println("Queue is full");
            return;
        }
        rear = (rear + 1) % capacity; // advance rear circularly
        arr[rear] = value; // place new value at rear
        size++; // increase size
    }

    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }
        int result = arr[front]; // get front element
        front = (front + 1) % capacity; // advance front circularly
        size--; // decrease size
        return result;
    }

    public void printQueue() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }
        int count = size;
        int i = front;
        while (count > 0) {
            System.out.print(arr[i] + " -> ");
            i = (i + 1) % capacity; // move circularly
            count--;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        QueueUsingArray queue = new QueueUsingArray(5);
        queue.enqueue(10);
        queue.enqueue(20);
        queue.dequeue();
        queue.enqueue(30);
        queue.printQueue();
    }
}

rear = (rear + 1) % capacity; // advance rear circularly

move rear pointer forward in circular manner to add new element

arr[rear] = value; // place new value at rear

store new element at rear position

size++; // increase size

track number of elements in queue

int result = arr[front]; // get front element

retrieve element at front to remove

front = (front + 1) % capacity; // advance front circularly

move front pointer forward in circular manner to remove element

size--; // decrease size

reduce count of elements after removal

while (count > 0) { ... i = (i + 1) % capacity; }

iterate from front to rear circularly to print queue

Output

20 -> 30 -> null

Complexity Analysis

Time: O(1) for enqueue and dequeue because we use pointers to add or remove elements without shifting

Space: O(n) because we store up to n elements in the array

vs Alternative: Compared to linked list queue, array queue uses fixed size but faster indexing; linked list uses dynamic size but more memory per element

Edge Cases

enqueue when queue is full

prints 'Queue is full' and does not add element

DSA Java

if (isFull()) { System.out.println("Queue is full"); return; }

dequeue when queue is empty

prints 'Queue is empty' and returns -1

DSA Java

if (isEmpty()) { System.out.println("Queue is empty"); return -1; }

wrap around when rear or front reaches end of array

rear and front pointers wrap to start using modulo

DSA Java

rear = (rear + 1) % capacity; front = (front + 1) % capacity;

When to Use This Pattern

When you need a first-in-first-out order with fixed maximum size, use a queue with circular array to efficiently add and remove elements.

Common Mistakes

Mistake: Not using modulo to wrap rear and front pointers, causing index out of bounds
Fix: Use modulo operator (%) with capacity to wrap pointers circularly

Mistake: Not updating size correctly leading to wrong full or empty checks
Fix: Increment size on enqueue and decrement on dequeue properly

Summary

Implements a queue using a fixed-size array with front and rear pointers.

Use when you want a simple queue with known maximum size and fast operations.

The key is to move front and rear pointers circularly to reuse array space.

Practice

1. What is the main purpose of using an array in a queue implementation?

easy

A. To store elements in a fixed-size linear order

B. To allow random access to elements anywhere in the queue

C. To sort elements automatically when inserted

D. To store elements in a tree structure

Solution

1. Step 1: Understand queue storage

   A queue stores elements in order, so an array can hold them in a fixed linear sequence.

2. Step 2: Compare other options

   Random access and sorting are not queue properties; tree structure is unrelated.

3. Final Answer:

   To store elements in a fixed-size linear order -> Option A

4. Quick Check:

   Queue uses array for linear storage [OK]

Hint: Queue uses array for fixed linear storage [OK]

Common Mistakes:

• Thinking queue allows random access
• Assuming array sorts elements automatically
• Confusing queue with tree structures

2. Which of the following is the correct way to check if a queue implemented using an array is empty?

easy

A. if (front == rear) return true;

B. if (rear == size) return true;

C. if (front == -1) return true;

D. if (front > rear) return true;

Solution

1. Step 1: Understand empty queue condition

   In array queue, front = -1 means no elements have been enqueued yet.

2. Step 2: Analyze other conditions

   front == rear means queue is full or empty depending on implementation; rear == size means full; front > rear is invalid.

3. Final Answer:

   if (front == -1) return true; -> Option C

4. Quick Check:

   Empty queue check uses front == -1 [OK]

Hint: Empty queue usually has front at -1 [OK]

Common Mistakes:

• Using front == rear to check empty (can be full)
• Checking rear == size for empty instead of full
• Using front > rear which is invalid

3. What will be the output after the following operations on a queue of size 5 implemented using an array?

enqueue(10); enqueue(20); dequeue(); enqueue(30); enqueue(40); dequeue(); enqueue(50); display();

medium

A. 30 -> 40 -> 50 -> null

B. 20 -> 30 -> 40 -> 50 -> null

C. 10 -> 20 -> 30 -> 40 -> 50 -> null

D. 40 -> 50 -> null

Solution

1. Step 1: Trace enqueue and dequeue operations

   enqueue(10), enqueue(20) adds 10,20; dequeue removes 10; enqueue(30), enqueue(40) adds 30,40; dequeue removes 20; enqueue(50) adds 50.

2. Step 2: Determine queue content after operations

   Remaining elements are 30, 40, 50 in order.

3. Final Answer:

   30 -> 40 -> 50 -> null -> Option A

4. Quick Check:

   Queue after operations = 30,40,50 [OK]

Hint: Track enqueue/dequeue stepwise to find queue content [OK]

Common Mistakes:

• Not removing correct elements on dequeue
• Assuming queue resets after full
• Confusing order of elements after operations

4. Identify the error in this queue implementation snippet using an array:

if (rear == size) {
  System.out.println("Queue is full");
} else {
  rear++;
  queue[rear] = value;
}

medium

A. rear should be incremented after assigning value

B. queue array size is not checked before insertion

C. front pointer is not updated when queue is empty

D. Condition should be rear == size - 1 to check full

Solution

1. Step 1: Analyze full queue condition

   Array index goes from 0 to size-1, so rear == size means out of bounds; full condition is rear == size - 1.

2. Step 2: Check rear increment and assignment

   Incrementing rear before assignment is correct if rear starts at -1.

3. Final Answer:

   Condition should be rear == size - 1 to check full -> Option D

4. Quick Check:

   Full queue check uses rear == size - 1 [OK]

Hint: Array index max is size - 1, not size [OK]

Common Mistakes:

• Checking rear == size instead of size - 1
• Incrementing rear after assignment causing overwrite
• Ignoring front pointer update on empty queue

5. Given a queue implemented using an array of size 4, initially empty, what will be the state of the queue after these operations?

enqueue(5); enqueue(10); dequeue(); enqueue(15); enqueue(20); enqueue(25); dequeue(); enqueue(30); display();

Assume the queue does not support circular wrapping and front and rear start at -1.

hard

A. 10 -> 15 -> 20 -> 25 -> null

B. Queue Overflow error occurs

C. 20 -> 25 -> 30 -> null

D. 15 -> 20 -> 25 -> null

Solution

1. Step 1: Trace each operation stepwise

   enqueue(5) adds 5; enqueue(10) adds 10; dequeue removes 5; enqueue(15) adds 15; enqueue(20) adds 20; enqueue(25) attempts to add but queue size is 4 and rear is at last index.

2. Step 2: Check for overflow due to no circular wrap

   Since queue is full at rear index 3, enqueue(25) causes overflow; subsequent operations cannot proceed.

3. Final Answer:

   Queue Overflow error occurs -> Option B

4. Quick Check:

   No circular wrap causes overflow at full array [OK]

Hint: Without circular queue, overflow occurs when rear reaches end [OK]

Common Mistakes:

• Assuming queue wraps around without circular logic
• Ignoring overflow condition on enqueue
• Miscounting elements after dequeue