Queue Concept and FIFO Principle in DSA C - Time & Space Complexity

Time Complexity: Queue Concept and FIFO Principle

O(1)

Understanding Time Complexity

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

How does the number of steps change when the queue gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Simple queue using array
#define MAX 100
int queue[MAX];
int front = 0, rear = -1;

void enqueue(int x) {
  if (rear < MAX - 1) {
    queue[++rear] = x;
  }
}

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

This code adds items to the end and removes from the front, following FIFO (First In First Out).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding or removing one item involves a simple index move and assignment.
• How many times: Each enqueue or dequeue runs once per call, no loops inside.

How Execution Grows With Input

Each enqueue or dequeue takes the same small number of steps, no matter how big the queue is.

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

Pattern observation: The time 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 a constant amount of time, regardless of queue size.

Common Mistake

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

[OK] Correct: In this queue, we just move the front index forward without shifting items, so time stays constant.

Interview Connect

Understanding that queue operations run in constant time shows you know how to use data structures efficiently, a key skill in coding interviews.

Self-Check

"What if we used a linked list instead of an array for the queue? How would the time complexity change?"