Circular Queue Implementation Using Array in DSA C - Time & Space Complexity

Time Complexity: Circular Queue Implementation Using Array

O(1)

Understanding Time Complexity

We want to understand how the time needed to add or remove items changes as the queue grows.

How does the circular queue handle operations as more elements are added or removed?

Scenario Under Consideration

Analyze the time complexity of the following circular queue operations.

#define SIZE 5
int queue[SIZE];
int front = -1, rear = -1;

void enqueue(int value) {
    if ((rear + 1) % SIZE == front) return; // Queue full
    if (front == -1) front = 0;
    rear = (rear + 1) % SIZE;
    queue[rear] = value;
}

int dequeue() {
    if (front == -1) return -1; // Queue empty
    int val = queue[front];
    if (front == rear) front = rear = -1;
    else front = (front + 1) % SIZE;
    return val;
}
    

This code adds (enqueue) and removes (dequeue) elements in a circular queue using an array.

Identify Repeating Operations

Look for loops or repeated steps inside the operations.

• Primary operation: Single step index update and assignment in enqueue and dequeue.
• How many times: Each enqueue or dequeue runs once per call, no loops inside.

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-6 steps per operation
100	5-6 steps per operation
1000	5-6 steps per operation

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 each enqueue or dequeue operation takes the same short 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 circular queue uses index math to jump directly to the right spot, so it never scans the whole array.

Interview Connect

Understanding constant time operations in circular queues shows you can manage fixed-size buffers efficiently, a useful skill in many real-world systems.

Self-Check

"What if we changed the circular queue to a normal queue without wrapping? How would the time complexity of enqueue and dequeue change?"

Practice

1. What is the main advantage of using a circular queue over a simple linear queue when implemented using an array?

easy

A. It automatically sorts the elements in the queue

B. It allows storing different data types in the same queue

C. It increases the maximum size of the queue beyond the array length

D. It efficiently uses the array space by reusing freed slots

Solution

1. Step 1: Understand linear queue limitation

   In a linear queue using an array, once the rear reaches the end, no more elements can be added even if there are empty slots at the front.

2. Step 2: Circular queue advantage

   A circular queue connects the end of the array back to the front, allowing reuse of empty slots freed by dequeuing, thus using space efficiently.

3. Final Answer:

   It efficiently uses the array space by reusing freed slots -> Option D

4. Quick Check:

   Circular queue reuses space = Advantage [OK]

Hint: Circular queue reuses space freed by dequeue [OK]

Common Mistakes:

• Thinking circular queue increases array size
• Believing it sorts elements automatically
• Confusing data type flexibility with queue type

2. Which of the following is the correct condition to check if a circular queue is full when using an array of size n with front and rear indices?

easy

A. rear == (front + 1) % n

B. front == rear

C. front == (rear + 1) % n

D. rear == n - 1

Solution

1. Step 1: Recall circular queue full condition

   The queue is full when the next position of rear (circularly) is front, meaning no space to insert new element.

2. Step 2: Express condition mathematically

   This condition is: front == (rear + 1) % n, where % is modulo operator to wrap around.

3. Final Answer:

   front == (rear + 1) % n -> Option C

4. Quick Check:

   Full if front is next to rear circularly = Condition B [OK]

Hint: Full when front is just after rear modulo array size [OK]

Common Mistakes:

• Using rear == (front + 1) % n (wrong direction)
• Checking front == rear (means empty, not full)
• Checking rear == n - 1 (linear queue condition)

3. Consider a circular queue of size 5 (indices 0 to 4). Initially, front = -1 and rear = -1. After the following operations:
enqueue(10), enqueue(20), enqueue(30), dequeue(), enqueue(40), enqueue(50), enqueue(60)
What will be the values of front and rear?

medium

A. front = 1, rear = 0

B. front = 0, rear = 4

C. front = 1, rear = 3

D. front = 2, rear = 1

Solution

1. Step 1: Trace enqueue and dequeue operations

   Start: front = -1, rear = -1
   enqueue(10): front=0, rear=0
   enqueue(20): rear=1
   enqueue(30): rear=2
   dequeue(): front=1 (removed 10)
   enqueue(40): rear=3
   enqueue(50): rear=4
   enqueue(60): rear wraps to 0 (circular)

2. Step 2: Final front and rear values

   After last enqueue, front=1, rear=0

3. Final Answer:

   front = 1, rear = 0 -> Option A

4. Quick Check:

   After wrap, rear=0 and front moved to 1 [OK]

Hint: Track front/rear step-by-step with wrap-around [OK]

Common Mistakes:

• Not updating front after dequeue
• Forgetting rear wraps to 0 after reaching end
• Mixing front and rear indices

4. Given the following code snippet for dequeue operation in a circular queue, identify the error:

int dequeue() {
  if (front == -1) {
    printf("Queue is empty\n");
    return -1;
  }
  int data = queue[front];
  if (front == rear) {
    front = rear = -1;
  } else {
    front = front + 1;
  }
  return data;
}

medium

A. front should be updated as (front + 1) % size to wrap around

B. rear should be incremented instead of front

C. The check for empty queue is incorrect

D. Data should be returned after updating front

Solution

1. Step 1: Understand circular queue front update

   In circular queue, front index must wrap around using modulo when incremented to stay within array bounds.

2. Step 2: Identify error in front update

   Code uses front = front + 1; which can go beyond array size. Correct is front = (front + 1) % size.

3. Final Answer:

   front should be updated as (front + 1) % size to wrap around -> Option A

4. Quick Check:

   Use modulo for front increment in circular queue [OK]

Hint: Use modulo when incrementing front or rear [OK]

Common Mistakes:

• Incrementing front without modulo wrap
• Confusing front and rear updates
• Returning data before updating front

5. You have a circular queue of size 6. After performing these operations:
enqueue(5), enqueue(10), enqueue(15), dequeue(), dequeue(), enqueue(20), enqueue(25), enqueue(30), enqueue(35)
What will be the queue content from front to rear?

hard

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

B. 15 -> 20 -> 25 -> 30 -> 35 -> null

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

D. 20 -> 25 -> 30 -> 35 -> 5 -> null

Solution

1. Step 1: Trace each operation step-by-step

   Start front = -1, rear = -1
   enqueue(5): front=0, rear=0, queue=[5]
   enqueue(10): rear=1, queue=[5,10]
   enqueue(15): rear=2, queue=[5,10,15]
   dequeue(): front=1 (removed 5)
   dequeue(): front=2 (removed 10)
   enqueue(20): rear=3, queue=[5,10,15,20]
   enqueue(25): rear=4, queue=[5,10,15,20,25]
   enqueue(30): rear=5, queue=[5,10,15,20,25,30]
   enqueue(35): rear wraps to 0, queue=[35,10,15,20,25,30]

2. Step 2: Identify current front and rear and queue content

   front=2, rear=0
   Queue elements from front to rear circularly: 15 (index 2), 20 (3), 25 (4), 30 (5), 35 (0)

3. Final Answer:

   15 -> 20 -> 25 -> 30 -> 35 -> null -> Option B

4. Quick Check:

   Queue content from front to rear matches 15 -> 20 -> 25 -> 30 -> 35 -> null [OK]

Hint: Track front and rear indices carefully with wrap-around [OK]

Common Mistakes:

• Ignoring wrap-around when rear reaches end
• Listing elements linearly without circular order
• Forgetting to update front after dequeues