Double Ended Queue Deque in DSA Javascript

Mental Model

A deque lets you add or remove items from both ends easily. It's like a line where you can join or leave from front or back.

Analogy: Imagine a train with doors at both front and back. Passengers can get on or off from either door, making it flexible and fast.

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

Dry Run Walkthrough

Input: Start with empty deque, then add 1 at front, add 2 at back, add 3 at front, remove from back

Goal: Show how items are added and removed from both ends of the deque

Step 1: Add 1 at front

front -> [1] -> back

Why: We add 1 at the front because deque allows insertion at front

Step 2: Add 2 at back

front -> [1] -> [2] -> back

Why: We add 2 at the back to show insertion at the other end

Step 3: Add 3 at front

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

Why: Adding 3 at front pushes existing items back

Step 4: Remove from back

front -> [3] -> [1] -> back

Why: Removing from back deletes the last item, which is 2

Result:

front -> [3] -> [1] -> back

Annotated Code

DSA Javascript

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

  addFront(element) {
    // Insert element at the start of the array
    this.items.unshift(element);
  }

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

  removeFront() {
    // Remove and return the first element
    if (this.isEmpty()) return null;
    return this.items.shift();
  }

  removeBack() {
    // Remove and return the last element
    if (this.isEmpty()) return null;
    return this.items.pop();
  }

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

  print() {
    // Print deque elements from front to back
    if (this.isEmpty()) {
      console.log('Deque is empty');
    } else {
      console.log(this.items.join(' -> '));
    }
  }
}

// Driver code using dry_run input
const deque = new Deque();
deque.addFront(1); // Step 1
deque.addBack(2);  // Step 2
deque.addFront(3); // Step 3
deque.removeBack(); // Step 4

deque.print();

this.items.unshift(element);

insert element at front -- shifts existing elements right

this.items.push(element);

insert element at back -- adds to end

if (this.isEmpty()) return null;

check if deque is empty before removing

return this.items.shift();

remove and return front element -- shifts elements left

return this.items.pop();

remove and return back element -- removes last

Output

3 -> 1

Complexity Analysis

Time: O(n) for addFront and removeFront because unshift and shift move elements; O(1) for addBack and removeBack because push and pop operate at the end

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

vs Alternative: Compared to linked list deque, array-based deque has slower front operations due to shifting, but faster back operations and simpler implementation

Edge Cases

Removing from empty deque

Returns null safely without error

DSA Javascript

if (this.isEmpty()) return null;

Adding and removing single element

Deque correctly updates to empty after removal

DSA Javascript

this.items.shift(); and this.items.pop(); handle single element removal

When to Use This Pattern

When a problem needs adding or removing items from both ends efficiently, use a deque because it supports front and back operations flexibly.

Common Mistakes

Mistake: Using push/pop for front operations which only work at the back
Fix: Use unshift/shift for front insertions and removals

Mistake: Not checking if deque is empty before removing, causing errors
Fix: Always check isEmpty() before removing elements

Summary

A deque lets you add or remove items from both front and back ends.

Use it when you need flexible insertion and deletion at both ends of a list.

Remember: front operations shift elements in an array, back operations do not.

Practice

1. What is a Double Ended Queue (Deque)?

easy

A. A stack where elements are added and removed only from the top.

B. A queue where elements can only be added at the rear and removed from the front.

C. A data structure where elements can be added or removed from both front and rear ends.

D. A list that allows random access to elements by index.

Solution

1. Step 1: Understand the definition of Deque

   A Deque allows insertion and deletion at both ends, unlike a queue or stack which restrict operations to one end.

2. Step 2: Compare with other data structures

   Queue allows operations only at front and rear separately; stack only at one end; list allows random access but not double-ended insertion/removal.

3. Final Answer:

   A data structure where elements can be added or removed from both front and rear ends. -> Option C

4. Quick Check:

   Deque = double-ended queue [OK]

Hint: Deque means double-ended queue, both ends usable [OK]

Common Mistakes:

• Confusing deque with stack or simple queue
• Thinking deque allows random access by index
• Assuming deque operations only at one end

2. Which of the following is the correct way to add an element to the front of a deque named dq in JavaScript using an array?

easy

A. dq.unshift(element);

B. dq.pop(element);

C. dq.push(element);

D. dq.shift(element);

Solution

1. Step 1: Identify array methods for front insertion

   In JavaScript, unshift() adds an element to the start (front) of an array.

2. Step 2: Check other methods

   push() adds to the end, pop() removes from end, shift() removes from front.

3. Final Answer:

   dq.unshift(element); -> Option A

4. Quick Check:

   unshift adds front element [OK]

Hint: Use unshift() to add front element in JS array [OK]

Common Mistakes:

• Using push() instead of unshift() for front insertion
• Confusing pop() and shift() as insertion methods
• Passing argument to pop() or shift() which don't take any

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

const 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 deque

   Start with empty array [].
   push(10) => [10]
   unshift(20) => [20, 10]
   push(30) => [20, 10, 30]
   shift() removes front element 20 => [10, 30]

2. Step 2: Final state of dq

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

3. Final Answer:

   [10, 30] -> Option A

4. Quick Check:

   After shift(), front 20 removed, left [10, 30] [OK]

Hint: Track each push/unshift/shift step carefully [OK]

Common Mistakes:

• Forgetting shift() removes front element
• Mixing order of push and unshift effects
• Assuming shift() removes last element

4. Identify the error in the following code snippet that tries to remove an element from the rear of a deque implemented as an array named dq:

dq.removeLast();

medium

A. dq.pop() should be used instead of removeLast().

B. removeLast() is not a valid JavaScript array method.

C. removeLast() requires an argument to specify the element.

D. dq should be a linked list to use removeLast().

Solution

1. Step 1: Check JavaScript array methods for removing last element

   JavaScript arrays do not have a method named removeLast(). The correct method to remove the last element is pop().

2. Step 2: Analyze other options

   Linked list is unrelated here; removeLast() does not take arguments; pop() is the correct method.

3. Final Answer:

   removeLast() is not a valid JavaScript array method. -> Option B

4. Quick Check:

   pop() removes last element, removeLast() invalid [OK]

Hint: Use pop() to remove last element in JS array [OK]

Common Mistakes:

• Assuming removeLast() exists in JS arrays
• Trying to pass arguments to pop() or removeLast()
• Confusing linked list methods with array methods

5. You want to implement a deque that supports the following operations efficiently: addFront, addRear, removeFront, removeRear. Which data structure is best suited for this and why?

hard

A. Array, because it allows fast insertion and deletion at both ends.

B. Stack, because it supports adding and removing elements efficiently.

C. Singly linked list, because it allows fast insertion and deletion at both ends.

D. Doubly linked list, because it allows fast insertion and deletion at both ends without shifting elements.

Solution

1. Step 1: Analyze operation requirements

   We need fast insertion and deletion at both front and rear ends.

2. Step 2: Compare data structures

   Array requires shifting elements for front operations, making it inefficient.
   Singly linked list allows fast insertion/removal only at one end efficiently.
   Doubly linked list allows fast insertion/removal at both ends without shifting.
   Stack supports operations only at one end.

3. Final Answer:

   Doubly linked list, because it allows fast insertion and deletion at both ends without shifting elements. -> Option D

4. Quick Check:

   Doubly linked list = best for deque operations [OK]

Hint: Use doubly linked list for efficient double-ended ops [OK]

Common Mistakes:

• Choosing array ignoring shifting cost
• Assuming singly linked list supports both ends efficiently
• Confusing stack with deque