Dequeue Operation in DSA Typescript

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 with doors at both ends. People can enter or exit from either door, making it flexible and quick to add or remove from front or back.

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

Dry Run Walkthrough

Input: dequeue: 1 -> 2 -> 3, perform dequeue operation from front and then from back

Goal: Remove one item from the front and one from the back, showing how the structure changes

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 Typescript

class Node {
  value: number;
  next: Node | null = null;
  prev: Node | null = null;
  constructor(value: number) {
    this.value = value;
  }
}

class Dequeue {
  front: Node | null = null;
  back: Node | null = null;

  // Add to back
  enqueueBack(value: number) {
    const newNode = new Node(value);
    if (!this.back) {
      this.front = newNode;
      this.back = newNode;
    } else {
      this.back.next = newNode;
      newNode.prev = this.back;
      this.back = newNode;
    }
  }

  // Remove from front
  dequeueFront(): number | null {
    if (!this.front) return null;
    const value = this.front.value;
    this.front = this.front.next; // advance front pointer
    if (this.front) this.front.prev = null; // disconnect old front
    else this.back = null; // empty dequeue
    return value;
  }

  // Remove from back
  dequeueBack(): number | null {
    if (!this.back) return null;
    const value = this.back.value;
    this.back = this.back.prev; // move back pointer backward
    if (this.back) this.back.next = null; // disconnect old back
    else this.front = null; // empty dequeue
    return value;
  }

  // Print current dequeue
  print() {
    let curr = this.front;
    let result = '';
    while (curr) {
      result += curr.value + ' -> ';
      curr = curr.next;
    }
    result += 'null';
    console.log(result);
  }
}

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

console.log('After dequeueFront:');
dq.dequeueFront();
dq.print();

console.log('After dequeueBack:');
dq.dequeueBack();
dq.print();

this.front = this.front.next; // advance front pointer

advance front pointer to next node to remove front element

if (this.front) this.front.prev = null; // disconnect old front

disconnect previous link of new front to avoid stale pointer

this.back = this.back.prev; // move back pointer backward

move back pointer to previous node to remove back element

if (this.back) this.back.next = null; // disconnect old back

disconnect next link of new back to avoid stale pointer

Output

Initial dequeue:

1 -> 2 -> 3 -> null

After dequeueFront:

2 -> 3 -> null

After dequeueBack:

2 -> null

Complexity Analysis

Time: O(1) because removing from front or back just moves pointers without traversal

Space: O(n) for storing n elements in the dequeue nodes

vs Alternative: Compared to a simple queue that only removes from front, dequeue allows removal from both ends in constant time, making it more flexible.

Edge Cases

empty dequeue

dequeueFront or dequeueBack returns null without error

DSA Typescript

if (!this.front) return null;

single element dequeue

removing front or back empties the dequeue and sets both pointers to null

DSA Typescript

else this.back = null; // empty dequeue

When to Use This Pattern

When a problem needs adding or removing items from both ends efficiently, reach for the dequeue pattern because it supports O(1) operations at front and back.

Common Mistakes

Mistake: Not updating the opposite pointer (prev or next) after removing a node, leaving stale links
Fix: Always set the prev of new front to null and next of new back to null after removal

Summary

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

Use it when you need flexible removal from both ends of a list-like structure.

The key is updating pointers carefully to keep the structure connected and avoid stale links.

Practice

1. What is the main difference between a dequeue and a queue?

easy

A. A dequeue allows insertion and deletion from both ends.

B. A dequeue only allows insertion at the rear.

C. A dequeue only allows deletion from the front.

D. A dequeue is a fixed size data structure.

Solution

1. Step 1: Understand queue operations

   A queue allows insertion at the rear and deletion from the front only.

2. Step 2: Understand dequeue operations

   A dequeue allows insertion and deletion at both front and rear ends.

3. Final Answer:

   A dequeue allows insertion and deletion from both ends. -> Option A

4. Quick Check:

   Dequeue = Both ends operations [OK]

Hint: Dequeue = Double-ended queue, both ends allowed [OK]

Common Mistakes:

• Thinking dequeue is same as queue
• Assuming insertion only at rear
• Confusing dequeue with stack

2. Which of the following is the correct TypeScript method to add an element at the front of a dequeue implemented as an array?

easy

A. dequeue.pushFront(element);

B. dequeue.unshift(element);

C. dequeue.addFirst(element);

D. dequeue.insertFront(element);

Solution

1. Step 1: Recall array methods for front insertion

   In TypeScript/JavaScript, unshift() adds element at the front of an array.

2. Step 2: Check other options

   Methods like pushFront, addFirst, insertFront do not exist in standard arrays.

3. Final Answer:

   dequeue.unshift(element); -> Option B

4. Quick Check:

   Array front insert = unshift() [OK]

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

Common Mistakes:

• Using push() instead of unshift()
• Assuming pushFront() exists
• Confusing with linked list methods

3. Consider this TypeScript code using an array as a dequeue:

let dequeue = [10, 20, 30];
dequeue.pop();
dequeue.unshift(5);
console.log(dequeue);

What is the output?

medium

A. [5, 10, 20]

B. [5, 10, 20, 30]

C. [10, 20, 30, 5]

D. [10, 20]

Solution

1. Step 1: Execute pop()

   pop() removes last element 30, so array becomes [10, 20].

2. Step 2: Execute unshift(5)

   unshift(5) adds 5 at front, array becomes [5, 10, 20].

3. Final Answer:

   [5, 10, 20] -> Option A

4. Quick Check:

   pop removes last, unshift adds front [OK]

Hint: pop removes last, unshift adds front [OK]

Common Mistakes:

• Assuming pop removes front
• Thinking unshift adds at end
• Confusing array order after operations

4. The following TypeScript code tries to remove an element from the front of a dequeue implemented as an array:

let dequeue = [1, 2, 3];
dequeue.removeFront();
console.log(dequeue);

What is the issue and how to fix it?

medium

A. removeFront() works only on linked lists; convert array to linked list.

B. removeFront() removes last element; use pop() instead.

C. removeFront() is not a valid method; use shift() instead.

D. No issue; code runs correctly.

Solution

1. Step 1: Identify invalid method

   Arrays in TypeScript do not have removeFront() method; this causes a runtime error.

2. Step 2: Use correct method for front removal

   shift() removes the first element from an array correctly.

3. Final Answer:

   removeFront() is not a valid method; use shift() instead. -> Option C

4. Quick Check:

   Front removal in arrays = shift() [OK]

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

Common Mistakes:

• Using non-existent removeFront() method
• Confusing pop() with front removal
• Thinking arrays have linked list methods

5. You have a dequeue implemented as an array: let dq = [1, 2, 3, 4];. You perform these operations:

dq.pop();
dq.unshift(0);
dq.push(5);
dq.shift();
console.log(dq);

What is the final state of the dequeue?

hard

A. [0, 1, 2, 3, 5]

B. [2, 3, 4, 5]

C. [1, 2, 3, 4, 5]

D. [1, 2, 3, 5]

Solution

1. Step 1: Execute pop()

   pop() removes last element 4, dq becomes [1, 2, 3].

2. Step 2: Execute unshift(0)

   unshift(0) adds 0 at front, dq becomes [0, 1, 2, 3].

3. Step 3: Execute push(5)

   push(5) adds 5 at end, dq becomes [0, 1, 2, 3, 5].

4. Step 4: Execute shift()

   shift() removes first element 0, dq becomes [1, 2, 3, 5].

5. Final Answer:

   [1, 2, 3, 5] -> Option D

6. Quick Check:

   pop removes end, unshift adds front, push adds end, shift removes front [OK]

Hint: Track each operation stepwise on array [OK]

Common Mistakes:

• Forgetting shift removes front element
• Mixing order of operations
• Assuming unshift adds at end