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

Time Complexity: Queue Implementation Using Array

O(1)

Understanding Time Complexity

We want to understand how the time taken by queue operations changes as the number of elements grows.

Specifically, how fast can we add or remove items in a queue implemented with an array?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#define MAX 100
int queue[MAX];
int front = -1, rear = -1;

void enqueue(int x) {
  if (rear == MAX - 1) return; // queue full
  if (front == -1) front = 0;
  queue[++rear] = x;
}

int dequeue() {
  if (front == -1 || front > rear) return -1; // queue empty
  return queue[front++];
}
    

This code adds (enqueue) and removes (dequeue) elements from a queue using a fixed-size array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single-step insert or remove at array index.
• How many times: Each enqueue or dequeue does one operation regardless of queue size.

How Execution Grows With Input

Each operation takes the same small number of steps no matter how many items are in the queue.

Input Size (n)	Approx. Operations
10	1 operation per enqueue or dequeue
100	1 operation per enqueue or dequeue
1000	1 operation per enqueue or dequeue

Pattern observation: The time does not increase with more elements; it stays constant.

Final Time Complexity

Time Complexity: O(1)

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

Common Mistake

[X] Wrong: "Removing an item from the queue takes longer as the queue grows because we have to shift elements."

[OK] Correct: In this implementation, we do not shift elements; we just move the front index forward, so removal stays fast.

Interview Connect

Understanding how queue operations stay fast helps you explain efficient data handling in real systems.

Self-Check

"What if we changed the queue to shift all elements left on dequeue? How would the time complexity change?"