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

Time Complexity: Queue Concept and FIFO Principle

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

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 it has more or fewer items?

Scenario Under Consideration

Analyze the time complexity of the following queue operations.

class Queue {
  constructor() {
    this.items = [];
  }
  enqueue(element) {
    this.items.push(element); // add to end
  }
  dequeue() {
    return this.items.shift(); // remove from front
  }
}
    

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

Identify Repeating Operations

Look at what repeats when we add or remove items.

• Primary operation: Adding with push is simple and fast.
• Primary operation: Removing with shift requires moving all other items forward.
• How many times: Each dequeue shifts all remaining items, so it depends on queue size.

How Execution Grows With Input

Adding items stays quick no matter how big the queue is.

Removing items takes longer as the queue grows because items must move forward.

Input Size (n)	Approx. Operations for dequeue()
10	10 moves
100	100 moves
1000	1000 moves

Pattern observation: Removing items takes more steps as the queue gets bigger, while adding stays fast.

Final Time Complexity

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

This means adding is always quick, but removing takes longer as the queue grows.

Common Mistake

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

[OK] Correct: Removing from the front with shift moves all other items, so it takes longer when the queue is big.

Interview Connect

Understanding how queue operations scale helps you explain data structure choices clearly and confidently.

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 FIFO stand for in the context of a queue?

easy

A. First In, First Out

B. First In, Final Out

C. Fast Input, Fast Output

D. First Input, First Output

Solution

1. Step 1: Understand FIFO meaning

   FIFO means the first element added is the first one to be removed.

2. Step 2: Match the acronym

   First In, First Out exactly matches FIFO.

3. Final Answer:

   First In, First Out -> Option A

4. Quick Check:

   FIFO = First In, First Out [OK]

Hint: Remember queue removes in order added, first comes out first [OK]

Common Mistakes:

• Confusing FIFO with LIFO (stack)
• Thinking FIFO means last in first out
• Mixing up acronym words

2. Which of the following is the correct way to add an element 5 to a queue named q in JavaScript using an array?

easy

A. q.unshift(5)

B. q.pop(5)

C. q.shift(5)

D. q.push(5)

Solution

1. Step 1: Understand queue insertion

   In a queue implemented with an array, new elements are added at the end.

2. Step 2: Identify correct method

   Array method push adds element at the end, so q.push(5) is correct.

3. Final Answer:

   q.push(5) -> Option D

4. Quick Check:

   Use push to add at queue end [OK]

Hint: Use push to add, shift to remove in JS queue [OK]

Common Mistakes:

• Using pop to add (pop removes last)
• Using shift to add (shift removes first)
• Using unshift adds at front, not end

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

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

medium

A. [30, 20]

B. [10, 20, 30]

C. [20, 30]

D. [10, 30]

Solution

1. Step 1: Add elements to queue

   Elements 10, 20, 30 are added in order using push, so queue = [10, 20, 30].

2. Step 2: Remove first element

   Using shift removes the first element (10), so queue becomes [20, 30].

3. Final Answer:

   [20, 30] -> Option C

4. Quick Check:

   Shift removes first, queue left with [20, 30] [OK]

Hint: Shift removes first element, push adds at end [OK]

Common Mistakes:

• Thinking pop removes first element
• Confusing order of elements after shift
• Expecting original array unchanged

4. The following code is intended to remove the first element from a queue implemented as an array. What is the error?

const queue = [1, 2, 3];
queue.pop();
console.log(queue);

medium

A. pop() removes the last element, not the first

B. pop() is not a valid array method

C. pop() adds an element instead of removing

D. pop() removes all elements

Solution

1. Step 1: Understand pop() behavior

   pop() removes the last element from an array, not the first.

2. Step 2: Identify correct method for first element removal

   To remove the first element in a queue, shift() should be used instead of pop().

3. Final Answer:

   pop() removes the last element, not the first -> Option A

4. Quick Check:

   pop removes last, shift removes first [OK]

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

Common Mistakes:

• Using pop() to remove first element
• Confusing pop() with shift()
• Expecting pop() to remove all elements

5. You have a queue implemented as an array: let q = [];. You perform these operations:

q.push(1);
q.push(2);
q.shift();
q.push(3);
q.shift();
q.push(4);
console.log(q);

What is the final state of the queue?

hard

A. [2, 3, 4]

B. [3, 4]

C. [1, 2, 3, 4]

D. [4]

Solution

1. Step 1: Trace each operation on queue

   Start with empty q = [].
   push(1) -> [1]
   push(2) -> [1, 2]
   shift() removes 1 -> [2]
   push(3) -> [2, 3]
   shift() removes 2 -> [3]
   push(4) -> [3, 4]

2. Step 2: Confirm final queue state

   After all operations, queue contains [3, 4].

3. Final Answer:

   [3, 4] -> Option B

4. Quick Check:

   FIFO order maintained, final queue is [3, 4] [OK]

Hint: Track push adds end, shift removes front step-by-step [OK]

Common Mistakes:

• Not removing elements with shift correctly
• Assuming push adds at front
• Mixing order of elements after shifts