Double Ended Queue Deque in DSA Typescript - Execution Trace

Concept Flow - Double Ended Queue Deque

Start

↓

Check Operation Type

↓

Insert Front

↓

Create New Node

↓

Update Front Pointer

↓

Update Size

↓

Done

↓

Check Remove Operation

↓

Remove Front

↓

Update Front Pointer

↓

Update Size

↓

Done

This flow shows how a double ended queue (deque) handles insertions and removals from both front and rear ends, updating pointers and size accordingly.

Execution Sample

DSA Typescript

deque = new Deque()
deque.insertRear(10)
deque.insertFront(20)
deque.insertRear(30)
deque.removeFront()
deque.removeRear()
deque.removeFront()

This code creates a deque, inserts elements at both ends, then removes elements from both ends.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create empty deque	[]	front=null, rear=null	null
2	insertRear(10)	[10]	rear -> new node(10), front -> new node(10)	10 -> null
3	insertFront(20)	[20, 10]	front -> new node(20), new node(20).next = old front(10)	20 -> 10 -> null
4	insertRear(30)	[20, 10, 30]	rear -> new node(30), old rear(10).next = new node(30)	20 -> 10 -> 30 -> null
5	removeFront()	[10, 30]	front -> old front.next (10)	10 -> 30 -> null
6	removeRear()	[10]	rear -> node before old rear (10)	10 -> null
7	removeFront()	[]	front=null, rear=null	null

💡 Deque is empty after last removal; front and rear pointers are null.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7
front	null	node(10)	node(20)	node(20)	node(10)	node(10)	null
rear	null	node(10)	node(10)	node(30)	node(30)	node(10)	null
size	0	1	2	3	2	1	0

Key Moments - 3 Insights

Why does the front pointer change when we insert at the front but the rear pointer stays the same?

When inserting at the front (see Step 3), a new node is added before the current front, so the front pointer updates to this new node. The rear pointer remains unchanged because the end of the list does not change.

Why do both front and rear pointers become null after removing the last element?

After removing the last element (Step 7), the deque becomes empty. Both pointers must be set to null to indicate there are no nodes left.

When removing from the rear, how do we find the new rear node?

Since the deque is singly linked, to remove the rear (Step 6), we traverse from front to find the node just before the current rear, then update rear pointer to that node.

Visual Quiz - 3 Questions

Look at the execution table at Step 3. What is the visual state of the deque?

A 10 -> 20 -> null

B 20 -> 10 -> null

C 10 -> null

D 20 -> null

💡 Hint

Check the 'Visual State' column at Step 3 in the execution_table.

At which step does the deque become empty?

A Step 7

B Step 6

C Step 5

D Step 4

💡 Hint

Look at the 'Nodes in List' column to find when it becomes [].

If we insertFront(40) after Step 4, what will be the new front node's value?

A 10

B 20

C 40

D 30

💡 Hint

Inserting at front adds a new node before current front (see concept_flow).

Concept Snapshot

Double Ended Queue (Deque):
- Supports insertion/removal at both front and rear.
- Front and rear pointers track ends.
- InsertFront: new node becomes front.
- InsertRear: new node becomes rear.
- RemoveFront: front moves to next node.
- RemoveRear: rear moves to previous node.
- Empty deque: front and rear are null.

Full Transcript

A double ended queue, or deque, allows adding and removing items from both ends. We keep track of two pointers: front and rear. When we insert at the front, we create a new node and update the front pointer to it, linking it to the old front. When inserting at the rear, we add a new node after the current rear and update the rear pointer. Removing from front moves the front pointer to the next node. Removing from rear requires finding the node before the rear and updating the rear pointer. When the deque becomes empty, both pointers are set to null. This structure lets us efficiently add or remove items from either end.

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