Queue Implementation Using Array in DSA Java - Time & Space Complexity

Time Complexity: Queue Implementation Using Array

O(1)

Understanding Time Complexity

We want to understand how the time to add or remove items from a queue using an array changes as the queue grows.

How does the number of steps grow when we enqueue or dequeue elements?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

    public void enqueue(int item) {
        if (size == capacity) return; // queue full
        rear = (rear + 1) % capacity;
        arr[rear] = item;
        size++;
    }

    public int dequeue() {
        if (size == 0) return -1; // queue empty
        int item = arr[front];
        front = (front + 1) % capacity;
        size--;
        return item;
    }
}
    

This code adds items to the rear and removes items from the front of a fixed-size array acting as a circular queue.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding or removing one item involves updating indexes and accessing one array element.
• How many times: Each enqueue or dequeue runs once per operation, no loops inside these methods.

How Execution Grows With Input

Each enqueue or dequeue does a fixed number of steps regardless of queue size.

Input Size (n)	Approx. Operations
10	5 steps per enqueue or dequeue
100	5 steps per enqueue or dequeue
1000	5 steps per enqueue or dequeue

Pattern observation: The number of steps stays the same no matter how many items are in the queue.

Final Time Complexity

Time Complexity: O(1)

This means adding or removing an item takes the same small amount of time no matter how big the queue is.

Common Mistake

[X] Wrong: "Enqueue or dequeue takes longer as the queue gets bigger because the array is large."

[OK] Correct: The code uses a circular array and only updates indexes and one element each time, so the size does not affect the steps needed.

Interview Connect

Knowing that queue operations using an array are constant time helps you explain efficient data handling in real applications.

Self-Check

"What if we used a simple array without circular indexing and shifted elements on dequeue? How would the time complexity change?"

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