Double Ended Queue Deque in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this deque operation sequence?

Consider a deque initially empty. We perform these operations in order:
1. Add 10 to the front
2. Add 20 to the back
3. Remove from the front
4. Add 30 to the front
5. Remove from the back
What is the state of the deque after these operations?

DSA Javascript

const deque = [];
deque.unshift(10); // front
deque.push(20);   // back
deque.shift();    // remove front
deque.unshift(30); // front
deque.pop();      // remove back
console.log(deque);

A [20, 30]

B [10, 30]

C [30]

D []

💡 Hint

Track each operation step by step on paper or in your mind.

After adding 10 front and 20 back, deque is [10, 20]. Removing front removes 10, leaving [20]. Adding 30 front makes [30, 20]. Removing back removes 20, leaving [30].

🧠 Conceptual

intermediate

Which operation is NOT typical for a double ended queue (deque)?

A deque supports adding and removing elements from both ends. Which of these operations is NOT a standard deque operation?

A Add element to the middle

B Remove element from the back

C Add element to the front

D Remove element from the front

💡 Hint

Think about where elements can be added or removed in a deque.

Deques allow adding/removing only at front or back, not in the middle.

❓ Predict Output

advanced

What is the output after these deque operations?

Given an empty deque, perform:
pushBack(5), pushBack(10), pushFront(3), popBack(), pushFront(7), popFront()
What is the deque content after these?

DSA Javascript

class Deque {
  constructor() { this.items = []; }
  pushFront(x) { this.items.unshift(x); }
  pushBack(x) { this.items.push(x); }
  popFront() { return this.items.shift(); }
  popBack() { return this.items.pop(); }
}
const d = new Deque();
d.pushBack(5);
d.pushBack(10);
d.pushFront(3);
d.popBack();
d.pushFront(7);
d.popFront();
console.log(d.items);

A [5]

B [7, 3, 5]

C [3, 5, 10]

D [3, 5]

💡 Hint

Write down the deque after each operation.

Operations step by step:
pushBack(5) -> [5]
pushBack(10) -> [5,10]
pushFront(3) -> [3,5,10]
popBack() removes 10 -> [3,5]
pushFront(7) -> [7,3,5]
popFront() removes 7 -> [3,5]

🔧 Debug

advanced

Why does this deque implementation cause an error?

This code tries to implement a deque but throws an error. What is the cause?

DSA Javascript

class Deque {
  constructor() { this.items = {}; this.frontIndex = 0; this.backIndex = 0; }
  pushFront(x) {
    this.frontIndex--;
    this.items[this.frontIndex] = x;
  }
  pushBack(x) {
    this.items[this.backIndex] = x;
    this.backIndex++;
  }
  popFront() {
    if (this.frontIndex === this.backIndex) throw new Error('Empty');
    const val = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;
    return val;
  }
  popBack() {
    if (this.frontIndex === this.backIndex) throw new Error('Empty');
    this.backIndex--;
    const val = this.items[this.backIndex];
    delete this.items[this.backIndex];
    return val;
  }
}
const d = new Deque();
d.pushBack(1);
d.pushFront(2);
console.log(d.popFront());
console.log(d.popBack());

A The frontIndex starts at 0 and is decremented, causing negative keys which are invalid in objects.

B The popFront method deletes the wrong index causing undefined values.

C The backIndex is not incremented correctly after pushBack.

D The constructor does not initialize the items array properly.

💡 Hint

Think about how JavaScript object keys work with negative numbers.

JavaScript object keys are strings. Negative keys like -1 are valid strings but can cause confusion. The main issue is that frontIndex starts at 0 and is decremented, leading to negative keys which may cause unexpected behavior or errors in some implementations expecting positive indices.

🚀 Application

expert

How many elements remain after this deque operation sequence?

Start with an empty deque. Perform these operations:
pushBack(1), pushBack(2), pushFront(3), popBack(), popFront(), pushBack(4), pushFront(5), popFront(), popBack()
How many elements remain in the deque at the end?

DSA Javascript

const deque = [];
deque.push(1);
deque.push(2);
deque.unshift(3);
deque.pop();
deque.shift();
deque.push(4);
deque.unshift(5);
deque.shift();
deque.pop();
console.log(deque.length);

A 3

B 1

C 2

D 0

💡 Hint

Count elements after each operation carefully.

Step by step:
pushBack(1) -> [1]
pushBack(2) -> [1,2]
pushFront(3) -> [3,1,2]
popBack() removes 2 -> [3,1]
popFront() removes 3 -> [1]
pushBack(4) -> [1,4]
pushFront(5) -> [5,1,4]
popFront() removes 5 -> [1,4]
popBack() removes 4 -> [1]
Final deque has 1 element.

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