Dequeue Operation in DSA Javascript

Mental Model

A dequeue lets you add or remove items from both ends, like a line where people can enter or leave from front or back.

Analogy: Imagine a double-ended queue as a hallway where people can enter or exit from either door at the front or the back.

front -> [1] -> [2] -> [3] -> back
↑front pointer          ↑back pointer

Dry Run Walkthrough

Input: dequeue: 1 -> 2 -> 3, remove from front, then remove from back

Goal: Show how removing from front and back changes the dequeue step by step

Step 1: remove element from front (1)

front -> [2] -> [3] -> back
↑front pointer          ↑back pointer

Why: Removing from front updates front pointer to next element

Step 2: remove element from back (3)

front -> [2] -> back
↑front pointer  ↑back pointer

Why: Removing from back updates back pointer to previous element

Result:

front -> [2] -> back
↑front pointer  ↑back pointer

Annotated Code

DSA Javascript

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

  // Remove from front
  removeFront() {
    if (this.items.length === 0) return null; // empty check
    return this.items.shift(); // remove first element
  }

  // Remove from back
  removeBack() {
    if (this.items.length === 0) return null; // empty check
    return this.items.pop(); // remove last element
  }

  // Add to back (helper for setup)
  addBack(element) {
    this.items.push(element);
  }

  // Print current state
  print() {
    return this.items.join(' -> ') + ' -> null';
  }
}

// Driver code
const dq = new Dequeue();
dq.addBack(1);
dq.addBack(2);
dq.addBack(3);
console.log('Initial:', dq.print());

const frontRemoved = dq.removeFront();
console.log('After removeFront:', dq.print());

const backRemoved = dq.removeBack();
console.log('After removeBack:', dq.print());

if (this.items.length === 0) return null; // empty check

check if dequeue is empty before removing

return this.items.shift(); // remove first element

remove element from front and update front pointer

return this.items.pop(); // remove last element

remove element from back and update back pointer

Output

Initial: 1 -> 2 -> 3 -> null

After removeFront: 2 -> 3 -> null

After removeBack: 2 -> null

Complexity Analysis

Time: O(n) for removeFront because shift moves all elements; O(1) for removeBack because pop removes last element directly

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

vs Alternative: Using a linked list for dequeue can make removeFront O(1) instead of O(n) because no shifting is needed

Edge Cases

empty dequeue

removeFront and removeBack return null without error

DSA Javascript

if (this.items.length === 0) return null; // empty check

single element dequeue

removing front or back removes the only element, leaving dequeue empty

DSA Javascript

return this.items.shift(); // remove first element

When to Use This Pattern

When you need to add or remove items from both ends of a list efficiently, think of the dequeue operation because it supports front and back changes.

Common Mistakes

Mistake: Using array shift for removeFront without realizing it shifts all elements causing O(n) time
Fix: Use a linked list implementation for O(1) removeFront or accept O(n) cost for array-based dequeue

Mistake: Not checking if dequeue is empty before removing causing errors
Fix: Always check if the dequeue is empty before removing elements

Summary

It removes elements from either the front or back of a dequeue.

Use it when you want to efficiently remove items from both ends of a list.

Remember that removing from front in an array shifts elements, which can be slow.

Practice

1. What is a dequeue in data structures?

easy

A. A stack that allows only last-in, first-out operations

B. A queue where elements can only be added at the front

C. A list that only allows insertion at the middle

D. A double-ended queue where elements can be added or removed from both ends

Solution

1. Step 1: Understand the definition of dequeue

   A dequeue is a data structure that allows insertion and deletion from both front and rear ends.

2. Step 2: Compare options with definition

   A double-ended queue where elements can be added or removed from both ends correctly describes a dequeue. Options A, B, and D describe other structures or incorrect behaviors.

3. Final Answer:

   A double-ended queue where elements can be added or removed from both ends -> Option D

4. Quick Check:

   Dequeue = Double-ended queue [OK]

Hint: Dequeue means double-ended queue, both ends allowed [OK]

Common Mistakes:

• Confusing dequeue with stack or normal queue
• Thinking elements can only be added at one end
• Assuming dequeue is a type of list

2. Which of the following is the correct syntax to add an element 5 at the front of a dequeue named dq in JavaScript using an array?

easy

A. dq.pushFront(5);

B. dq.unshift(5);

C. dq.addFront(5);

D. dq.insertFront(5);

Solution

1. Step 1: Recall JavaScript array methods for front insertion

   JavaScript arrays use unshift() to add elements at the front.

2. Step 2: Match method with options

   Only dq.unshift(5); uses unshift(5), which is correct. Other options are invalid methods.

3. Final Answer:

   dq.unshift(5); -> Option B

4. Quick Check:

   Array front insert = unshift() [OK]

Hint: Use unshift() to add at front in JS arrays [OK]

Common Mistakes:

• Using pushFront which is not a JS array method
• Confusing push (adds at end) with front insertion
• Assuming addFront or insertFront exist in JS arrays

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

let dq = [];
dq.push(10);
dq.unshift(20);
dq.push(30);
dq.shift();
console.log(dq);

medium

A. [10, 30]

B. [20, 10, 30]

C. [20, 30]

D. [10, 20, 30]

Solution

1. Step 1: Trace each operation on the dequeue array

   Start with empty dq = []. push(10) adds 10 at end: [10]. unshift(20) adds 20 at front: [20, 10]. push(30) adds 30 at end: [20, 10, 30]. shift() removes front element (20): [10, 30].

2. Step 2: Determine final state of dq

   After all operations, dq is [10, 30].

3. Final Answer:

   [10, 30] -> Option A

4. Quick Check:

   After shift(), front removed, dq = [10, 30] [OK]

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

Common Mistakes:

• Confusing shift() with pop()
• Mixing order of unshift and push
• Forgetting shift() removes front element

4. Identify the error in the following dequeue operation code:

let dq = [];
dq.push(1);
dq.popFront();
console.log(dq);

medium

A. popFront() is not a valid JavaScript array method

B. push() cannot be used on empty arrays

C. popFront() should be pop() to remove last element

D. dq should be initialized as a Dequeue object, not array

Solution

1. Step 1: Check JavaScript array methods used

   JavaScript arrays do not have a method named popFront(). The correct method to remove front element is shift().

2. Step 2: Identify the error

   Using popFront() causes a runtime error as it is undefined.

3. Final Answer:

   popFront() is not a valid JavaScript array method -> Option A

4. Quick Check:

   popFront() invalid in JS arrays [OK]

Hint: Use shift() to remove front, pop() for end [OK]

Common Mistakes:

• Assuming popFront() exists like pop()
• Confusing pop() with front removal
• Not knowing shift() removes front element

5. You have a dequeue implemented as a JavaScript array dq with elements [5, 10, 15, 20]. You want to remove the element 5 from the front and add 25 at the rear, then remove the element 20 from the rear and add 30 at the front. What will be the final state of dq?

hard

A. [30, 5, 10, 15, 25]

B. [10, 15, 25, 30]

C. [30, 10, 15, 25]

D. [10, 15, 20, 25, 30]

Solution

1. Step 1: Remove front element

   Start dq = [5, 10, 15, 20]. Remove front element 5 using shift(): dq = [10, 15, 20]. Rear is now 20.

2. Step 2: Remove rear, add rear, add front

   Remove rear element 20 using pop(): dq = [10, 15]. Add 25 at rear using push(): dq = [10, 15, 25]. Add 30 at front using unshift(): dq = [30, 10, 15, 25].

3. Final Answer:

   [30, 10, 15, 25] -> Option C

4. Quick Check:

   Front removed 5, rear removed 20, added 30 front, 25 rear [OK]

Hint: Use shift/pop for removal, unshift/push for addition [OK]

Common Mistakes:

• Removing wrong elements from front or rear
• Mixing order of operations
• Using pop() instead of shift() for front removal