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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Deque Operations Sequence

What is the printed state of the deque after executing the following TypeScript code?

DSA Typescript

class Deque<T> {
  private items: T[] = [];
  addFront(element: T) { this.items.unshift(element); }
  addBack(element: T) { this.items.push(element); }
  removeFront(): T | undefined { return this.items.shift(); }
  removeBack(): T | undefined { return this.items.pop(); }
  print(): string { return this.items.join(' -> ') + ' -> null'; }
}

const deque = new Deque<number>();
deque.addBack(10);
deque.addFront(20);
deque.addBack(30);
deque.removeFront();
deque.addFront(40);
console.log(deque.print());

A 40 -> 10 -> 30 -> null

B 20 -> 10 -> 30 -> null

C 10 -> 20 -> 30 -> null

D 40 -> 20 -> 30 -> null

💡 Hint

Trace each operation step-by-step, especially the removeFront call.

The deque starts empty.

addBack(10) adds 10 at back: [10]

addFront(20) adds 20 at front: [20, 10]

addBack(30) adds 30 at back: [20, 10, 30]

removeFront() removes 20: [10, 30]

addFront(40) adds 40 at front: [40, 10, 30]

Printed state is "40 -> 10 -> 30 -> null".

🧠 Conceptual

intermediate

Deque Size After Mixed Operations

Given a deque initially empty, after performing these operations in order: addBack(5), addFront(3), removeBack(), addBack(7), removeFront(), what is the number of items in the deque?

A 2

B 1

C 3

D 0

💡 Hint

Count items after each operation carefully.

Start empty.

addBack(5): [5]

addFront(3): [3, 5]

removeBack(): removes 5, now [3]

addBack(7): [3, 7]

removeFront(): removes 3, now [7]

Only one item remains.

🔧 Debug

advanced

Identify the Error in Deque Implementation

What error will this TypeScript code raise when calling removeFront on an empty deque?

DSA Typescript

class Deque<T> {
  private items: T[] = [];
  removeFront(): T {
    return this.items.shift()!;
  }
}

const deque = new Deque<number>();
console.log(deque.removeFront());

A TypeError: Cannot read property of undefined

B Runtime error: Cannot read property 'shift' of undefined

C undefined is returned without error

D No error, prints undefined

💡 Hint

shift() on empty array returns undefined safely. The non-null assertion ! does not cause a runtime error.

Calling shift() on an empty array returns undefined.

The non-null assertion operator (!) only affects TypeScript's type checking and is erased at runtime.

Therefore, undefined is returned without error, and console.log prints 'undefined'.

❓ Predict Output

advanced

Deque State After Complex Operations

What is the printed state of the deque after this sequence of operations?

DSA Typescript

class Deque<T> {
  private items: T[] = [];
  addFront(element: T) { this.items.unshift(element); }
  addBack(element: T) { this.items.push(element); }
  removeFront(): T | undefined { return this.items.shift(); }
  removeBack(): T | undefined { return this.items.pop(); }
  print(): string { return this.items.join(' -> ') + ' -> null'; }
}

const deque = new Deque<string>();
deque.addBack('a');
deque.addBack('b');
deque.addFront('c');
deque.removeBack();
deque.addFront('d');
deque.removeFront();
console.log(deque.print());

A d -> c -> a -> null

B a -> null

C c -> a -> null

D c -> b -> null

💡 Hint

Track the deque contents after each operation carefully.

Start empty.

addBack('a'): [a]

addBack('b'): [a, b]

addFront('c'): [c, a, b]

removeBack(): removes 'b', now [c, a]

addFront('d'): [d, c, a]

removeFront(): removes 'd', now [c, a]

Printed state: "c -> a -> null".

🧠 Conceptual

expert

Deque Behavior Under Concurrent Operations

In a multi-threaded environment, which of the following issues is most likely when multiple threads perform addFront and removeBack operations on a shared deque without synchronization?

A Race condition causing inconsistent deque state

B Deadlock due to waiting on locks

C Memory leak from unremoved elements

D Stack overflow from recursive calls

💡 Hint

Think about what happens if two threads modify the deque at the same time.

Without synchronization, concurrent modifications can overlap.

This causes race conditions where the deque's internal state becomes inconsistent or corrupted.

Deadlocks require locks, which are not mentioned here.

Memory leaks or stack overflow are unrelated to concurrent unsynchronized access.

Practice

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

easy

A. A data structure where elements can be added or removed from both ends

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

C. A stack where elements can only be added or removed from the top

D. A list that allows random access to elements

Solution

1. Step 1: Understand the definition of a deque

   A deque allows insertion and deletion from both front and rear ends, unlike a queue or stack.

2. Step 2: Compare with other data structures

   Queue allows operations only at one end for insertion and the other for deletion; stack only at one end.

3. Final Answer:

   A data structure where elements can be added or removed from both ends -> Option A

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 queue
• Thinking deque allows random access
• Assuming insertion only at one end

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

easy

A. deque.shift(element);

B. deque.push(element);

C. deque.pop(element);

D. deque.unshift(element);

Solution

1. Step 1: Recall array methods for front insertion

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

2. Step 2: Verify other methods

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

3. Final Answer:

   deque.unshift(element); -> Option D

4. Quick Check:

   unshift() adds front [OK]

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

Common Mistakes:

• Using push() instead of unshift() for front
• Confusing pop() and shift() as insertion
• Passing arguments to pop() or shift()

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

const deque: number[] = [];
deque.push(10);
deque.unshift(20);
deque.push(30);
deque.shift();
console.log(deque);

medium

A. [20, 10, 30]

B. [20, 30]

C. [10, 30]

D. [30, 20]

Solution

1. Step 1: Trace each operation on deque

   Start: []
   push(10) -> [10]
   unshift(20) -> [20, 10]
   push(30) -> [20, 10, 30]
   shift() removes front -> removes 20 -> [10, 30]

2. Step 2: Final state of deque

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

3. Final Answer:

   [10, 30] -> Option C

4. Quick Check:

   After shift(), front removed -> [10, 30] [OK]

Hint: Remember shift() removes front element [OK]

Common Mistakes:

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

4. Identify the error in the following TypeScript code that implements a deque using an array:

const deque: number[] = [];
deque.push(5);
deque.unshift(10);
deque.pop(5);
console.log(deque);

medium

A. push() cannot be used on arrays

B. pop() should not have any arguments

C. unshift() removes elements, not adds

D. console.log syntax is incorrect

Solution

1. Step 1: Check usage of pop() method

   pop() removes the last element and does not take any arguments. Passing 5 is incorrect.

2. Step 2: Verify other methods and syntax

   push() adds element at end, unshift() adds at front, console.log syntax is correct.

3. Final Answer:

   pop() should not have any arguments -> Option B

4. Quick Check:

   pop() takes no arguments [OK]

Hint: pop() never takes arguments [OK]

Common Mistakes:

• Passing argument to pop()
• Confusing unshift() as removal
• Thinking push() is invalid on arrays

5. You want to implement a deque that supports adding and removing elements from both ends efficiently. Which data structure is best suited for this in TypeScript, and why?

hard

A. Use a linked list because it allows O(1) insertion and deletion at both ends

B. Use an array because it provides O(1) insertion and deletion at both ends

C. Use a binary tree because it supports fast search and insertion

D. Use a stack because it supports adding/removing from both ends

Solution

1. Step 1: Analyze efficiency of array for deque operations

   Arrays have O(1) insertion/deletion at the end but O(n) at the front due to shifting elements.

2. Step 2: Consider linked list advantages

   Linked lists allow O(1) insertion and deletion at both front and rear by adjusting pointers.

3. Step 3: Evaluate other options

   Binary trees are for search, not efficient deque operations; stacks only allow one end operations.

4. Final Answer:

   Use a linked list because it allows O(1) insertion and deletion at both ends -> Option A

5. Quick Check:

   Linked list = efficient deque [OK]

Hint: Linked list supports fast front and rear operations [OK]

Common Mistakes:

• Assuming arrays are efficient at front insertion
• Confusing stack with deque
• Choosing binary tree for deque operations