Queue Implementation Using Array in DSA Javascript

Mental Model

A queue is like a line where the first person in is the first person out. We use an array to keep track of this line.

Analogy: Imagine a queue at a ticket counter. People join at the end and leave from the front, just like adding to the end of an array and removing from the front.

front -> [ ] [ ] [ ] [ ] [ ] ← rear
Initially empty queue with front and rear pointers.

Dry Run Walkthrough

Input: Start with empty queue, enqueue 10, enqueue 20, dequeue once, enqueue 30

Goal: Show how elements enter at the rear and leave from the front using an array

Step 1: enqueue 10 at rear

front -> [10] ← rear

Why: Add first element, front and rear both point to it

Step 2: enqueue 20 at rear

front -> [10, 20] ← rear

Why: Add second element at the end, rear moves forward

Step 3: dequeue from front

front -> [20] ← rear

Why: Remove first element, front moves forward

Step 4: enqueue 30 at rear

front -> [20, 30] ← rear

Why: Add new element at the end, rear moves forward

Result:

front -> [20, 30] ← rear

Annotated Code

DSA Javascript

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

  enqueue(element) {
    // Add element at the end of the array
    this.items.push(element);
  }

  dequeue() {
    // Remove element from the front of the array
    if (this.isEmpty()) {
      return 'Queue is empty';
    }
    return this.items.shift();
  }

  isEmpty() {
    return this.items.length === 0;
  }

  printQueue() {
    if (this.isEmpty()) {
      console.log('Queue is empty');
      return;
    }
    console.log(this.items.join(' -> ') + ' -> null');
  }
}

// Driver code
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.dequeue();
queue.enqueue(30);
queue.printQueue();

this.items.push(element);

Add element at the rear of the queue

if (this.isEmpty()) { return 'Queue is empty'; }

Check if queue is empty before dequeue

return this.items.shift();

Remove element from the front of the queue

console.log(this.items.join(' -> ') + ' -> null');

Print queue elements in order from front to rear

Output

20 -> 30 -> null

Complexity Analysis

Time: O(n) for dequeue because removing from front shifts all elements; O(1) for enqueue because adding at end is direct

Space: O(n) because we store all elements in an array

vs Alternative: Compared to linked list queue, array dequeue is slower due to shifting elements, but enqueue is similarly fast

Edge Cases

dequeue from empty queue

Returns 'Queue is empty' message to avoid errors

DSA Javascript

if (this.isEmpty()) { return 'Queue is empty'; }

enqueue into empty queue

Adds element and queue updates correctly

DSA Javascript

this.items.push(element);

When to Use This Pattern

When you see a problem requiring first-in-first-out order, think of a queue implemented with an array for simple enqueue and dequeue operations.

Common Mistakes

Mistake: Using array pop() for dequeue which removes from the end instead of the front
Fix: Use shift() to remove from the front to maintain queue order

Mistake: Not checking if queue is empty before dequeue causing errors
Fix: Add a check for empty queue before removing elements

Summary

Implements a queue using an array where elements enter at the rear and leave from the front.

Use when you need a simple queue structure and can tolerate O(n) dequeue time due to shifting.

Remember that enqueue adds at the end and dequeue removes from the front, shifting elements in the array.

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