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

Time Complexity: Queue Concept and FIFO Principle

O(1) for enqueue, O(n) for dequeue

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 queue handle operations when more items are involved?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Queue {
  private items: number[] = [];

  enqueue(item: number) {
    this.items.push(item); // add to end
  }

  dequeue() {
    return this.items.shift(); // remove from front
  }
}
    

This code adds items to the end and removes items from the front of the queue, following FIFO.

Identify Repeating Operations

Look at the main repeated actions when using the queue.

• Primary operation: Adding with push and removing with shift.
• How many times: Each operation happens once per item added or removed.

How Execution Grows With Input

Adding items is quick no matter how many items are in the queue.

Removing items takes longer as the queue grows because all remaining items shift forward.

Input Size (n)	Approx. Operations for enqueue	Approx. Operations for dequeue
10	10 (simple add)	Up to 10 (shifting items)
100	100 (simple add)	Up to 100 (shifting items)
1000	1000 (simple add)	Up to 1000 (shifting items)

Pattern observation: Adding stays fast, removing slows down as queue grows.

Final Time Complexity

Time Complexity: O(1) for enqueue, O(n) for dequeue

Adding is always quick, but removing takes longer when the queue is bigger.

Common Mistake

[X] Wrong: "Both adding and removing items from a queue always take the same quick time."

[OK] Correct: Removing from the front requires moving all other items forward, which takes more time as the queue grows.

Interview Connect

Understanding how queue operations scale helps you explain data structure choices clearly and shows you know what happens behind the scenes.

Self-Check

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

Practice

1. What does the FIFO principle mean in the context of a queue?

easy

A. First In, First Out - the first element added is the first removed

B. First In, First Out - the last element added is the first removed

C. Last In, First Out - the first element added is the last removed

D. Last In, First Out - the last element added is the last removed

Solution

1. Step 1: Understand FIFO meaning

   FIFO means the first element that enters the queue is the first to leave.

2. Step 2: Match FIFO to queue behavior

   Queues follow FIFO, so the first added element is removed first.

3. Final Answer:

   First In, First Out - the first element added is the first removed -> Option A

4. Quick Check:

   FIFO = First In, First Out [OK]

Hint: Remember queue = line; first come, first served [OK]

Common Mistakes:

• Confusing FIFO with LIFO
• Thinking last added is removed first
• Mixing queue with stack behavior

2. Which of the following is the correct TypeScript syntax to create an empty queue using an array?

easy

A. let queue = {};

B. const queue: number[] = [];

C. const queue = new Queue();

D. queue = [];

Solution

1. Step 1: Identify TypeScript array syntax

   To create an empty array of numbers, use const queue: number[] = [];

2. Step 2: Check other options

   const queue = new Queue(); uses a class not defined here, A creates an object, D is missing declaration keyword.

3. Final Answer:

   const queue: number[] = []; -> Option B

4. Quick Check:

   Array declaration with type and empty brackets [OK]

Hint: Use const with type and empty brackets for empty array [OK]

Common Mistakes:

• Using object {} instead of array []
• Missing type annotation in TypeScript
• Omitting declaration keyword (const/let)

3. What will be the output of the following TypeScript code?

const queue: number[] = [];
queue.push(10);
queue.push(20);
queue.push(30);
const first = queue.shift();
console.log(queue);

medium

A. []

B. [10, 20, 30]

C. [30]

D. [20, 30]

Solution

1. Step 1: Add elements to queue

   Elements 10, 20, 30 are added to the queue in order.

2. Step 2: Remove first element using shift()

   shift() removes 10, so queue now contains [20, 30].

3. Final Answer:

   [20, 30] -> Option D

4. Quick Check:

   After shift(), queue = [20, 30] [OK]

Hint: shift() removes first element, push() adds last [OK]

Common Mistakes:

• Confusing shift() with pop()
• Expecting original array unchanged
• Thinking push() removes elements

4. Identify the error in this TypeScript queue code:

const queue: number[] = [];
queue.push(5);
queue.push(10);
const removed = queue.pop();
console.log(queue);

medium

A. Using pop() removes last, not first element in queue

B. push() is not valid for arrays

C. queue should be declared as object, not array

D. Missing type annotation for queue

Solution

1. Step 1: Understand queue removal method

   Queue removes elements in FIFO order, so first element should be removed.

2. Step 2: Check method used

   pop() removes last element, which breaks FIFO principle.

3. Final Answer:

   Using pop() removes last, not first element in queue -> Option A

4. Quick Check:

   Queue removal must use shift(), not pop() [OK]

Hint: Use shift() to remove first, pop() removes last [OK]

Common Mistakes:

• Using pop() instead of shift() for queue
• Thinking push() removes elements
• Confusing array with object declaration

5. You have a queue implemented as an array in TypeScript. You add elements 1, 2, 3, then remove two elements. What will be the state of the queue after these operations?

const queue: number[] = [];
queue.push(1);
queue.push(2);
queue.push(3);
queue.shift();
queue.shift();
console.log(queue);

hard

A. [2, 3]

B. [1, 2, 3]

C. [3]

D. []

Solution

1. Step 1: Add elements to queue

   Elements 1, 2, 3 are added in order: queue = [1, 2, 3]

2. Step 2: Remove two elements using shift()

   First shift() removes 1, second shift() removes 2, leaving [3]

3. Final Answer:

   [3] -> Option C

4. Quick Check:

   After two shifts, queue = [3] [OK]

Hint: Each shift() removes one from front [OK]

Common Mistakes:

• Removing elements with pop() instead of shift()
• Expecting queue to be empty after two removals
• Confusing order of elements after removals