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

Time Complexity: Queue Implementation Using Array

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

Understanding Time Complexity

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

How does the queue's size affect the speed of its main operations?

Scenario Under Consideration

Analyze the time complexity of the following queue operations using an array.

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    return this.items.shift();
  }
}
    

This code adds items to the end and removes items from the front of an array to act like a queue.

Identify Repeating Operations

Look at the main actions that repeat when we add or remove items.

• Primary operation: Adding with push and removing with shift.
• How many times: Each enqueue adds once; each dequeue removes once and shifts remaining items.

How Execution Grows With Input

Adding items is quick no matter how big the queue is, but removing items takes longer as the queue grows.

Input Size (n)	Approx. Operations for dequeue()
10	9 shifts
100	99 shifts
1000	999 shifts

Pattern observation: Removing an item requires moving all other items forward, so work grows directly with queue size.

Final Time Complexity

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

This means adding is fast and steady, but removing gets slower as the queue grows.

Common Mistake

[X] Wrong: "Both enqueue and dequeue are always fast and take the same time."

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

Interview Connect

Understanding how array-based queues work helps you explain trade-offs and choose the right data structure in real projects.

Self-Check

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

Practice

1. What is the main characteristic of a queue data structure implemented using an array?

easy

A. It stores elements in sorted order

B. It follows Last-In-First-Out (LIFO) order

C. It follows First-In-First-Out (FIFO) order

D. It allows random access to elements

Solution

1. Step 1: Understand queue behavior

   A queue adds elements at the end and removes from the front, so the first element added is the first removed.

2. Step 2: Compare with options

   FIFO means First-In-First-Out, which matches queue behavior. LIFO is for stacks, random access is for arrays, and sorted order is unrelated.

3. Final Answer:

   It follows First-In-First-Out (FIFO) order -> Option C

4. Quick Check:

   Queue = FIFO [OK]

Hint: Queue always removes the oldest element first [OK]

Common Mistakes:

• Confusing queue with stack (LIFO)
• Thinking queue allows random access
• Assuming queue sorts elements automatically

2. Which of the following is the correct syntax to add an element `x` to the end of a queue implemented as an array named queue in JavaScript?

easy

A. queue.push(x);

B. queue.pop(x);

C. queue.shift(x);

D. queue.unshift(x);

Solution

1. Step 1: Identify method to add at end

   In JavaScript arrays, push() adds an element to the end of the array.

2. Step 2: Check other methods

   pop() removes from end, shift() removes from front, unshift() adds at front.

3. Final Answer:

   queue.push(x); -> Option A

4. Quick Check:

   push adds at end [OK]

Hint: Use push() to add at end of array [OK]

Common Mistakes:

• Using pop() which removes instead of adds
• Using shift() or unshift() incorrectly
• Confusing push() with unshift()

3. What will be the output of the following JavaScript code implementing a queue using an array?

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

medium

A. [10, 20, 30]

B. [20, 30]

C. [30, 20]

D. [10, 30]

Solution

1. Step 1: Trace queue operations

   Initially empty array. After push(10), queue = [10]. After push(20), queue = [10, 20].

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

   shift() removes 10, so queue = [20]. Then push(30), queue = [20, 30].

3. Final Answer:

   [20, 30] -> Option B

4. Quick Check:

   After shift and push, queue = [20, 30] [OK]

Hint: shift() removes front, push() adds end [OK]

Common Mistakes:

• Thinking shift() removes from end
• Confusing order of elements after operations
• Assuming push adds at front

4. Identify the error in the following queue implementation using an array and suggest the fix:

const queue = [];
queue.push(1);
queue.push(2);
const removed = queue.pop();
console.log(queue);

medium

A. pop() removes from end; use shift() to remove from front

B. push() should be replaced with unshift()

C. pop() should be replaced with push()

D. No error; code works correctly

Solution

1. Step 1: Understand queue removal operation

   Queue removes elements from the front, but pop() removes from the end.

2. Step 2: Correct removal method

   Use shift() to remove the first element to maintain FIFO order.

3. Final Answer:

   pop() removes from end; use shift() to remove from front -> Option A

4. Quick Check:

   Queue removal = shift() [OK]

Hint: Use shift() to remove front element in queue [OK]

Common Mistakes:

• Using pop() which removes last element
• Confusing push() and unshift() roles
• Thinking pop() removes front element

5. Given a queue implemented as an array, how can you efficiently check if the queue is empty before removing an element to avoid errors?

medium

A. Check if queue.length > 1 before calling shift()

B. Check if queue[0] === undefined before calling pop()

C. Call shift() directly without checking

D. Check if queue.length === 0 before calling shift()

Solution

1. Step 1: Understand empty queue condition

   An empty queue has length 0, so no elements to remove.

2. Step 2: Safe removal check

   Check queue.length === 0 before calling shift() to avoid removing from empty array.

3. Final Answer:

   Check if queue.length === 0 before calling shift() -> Option D

4. Quick Check:

   Empty queue check = length === 0 [OK]

Hint: Always check length === 0 before removing [OK]

Common Mistakes:

• Checking wrong index for emptiness
• Calling shift() without checking length
• Checking length > 1 instead of 0