Double Ended Queue Deque in DSA C# - Execution Trace

Concept Flow - Double Ended Queue Deque

Start

↓

Check Operation Type

↓

Insert Front

↓

Create New Node

↓

Adjust Front Pointer

↓

Update Links

↓

Done

↓

Delete Front

↓

Check Empty?

↓

Remove Node

↓

Adjust Front Pointer

↓

Update Links

↓

Done

↓

End

This flow shows how a double ended queue (deque) handles insertions and deletions at both front and rear ends by adjusting pointers and links accordingly.

Execution Sample

DSA C#

Deque deque = new Deque();
deque.InsertRear(10);
deque.InsertFront(20);
deque.DeleteRear();
deque.InsertRear(30);

This code inserts 10 at rear, 20 at front, deletes rear element, then inserts 30 at rear in the deque.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	InsertRear(10)	10	front=null->node(10), rear=null->node(10)	10 -> null
2	InsertFront(20)	20 -> 10	front=node(10)->node(20), rear=node(10)	20 -> 10 -> null
3	DeleteRear()	20	rear=node(10)->node(20), node(10) removed	20 -> null
4	InsertRear(30)	20 -> 30	rear=node(20)->node(30)	20 -> 30 -> null
5	End	20 -> 30	No change	20 -> 30 -> null

💡 No more operations to perform; deque final state is 20 -> 30 -> null

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	Final
front	null	node(10)	node(20)	node(20)	node(20)	node(20)
rear	null	node(10)	node(10)	node(20)	node(30)	node(30)
size	0	1	2	1	2	2

Key Moments - 3 Insights

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

When inserting at the front (Step 2), the new node becomes the new front, so the front pointer updates. When inserting at the rear (Step 1 and 4), the rear pointer moves to the new node, but the front stays the same unless the deque was empty.

Why does deleting the rear (Step 3) update the rear pointer to the previous node?

Deleting the rear removes the last node, so the rear pointer must move to the node before it to keep track of the new end of the deque, as shown in Step 3.

What happens if we delete from an empty deque?

The operation would check if the deque is empty (not shown in this trace). If empty, deletion does nothing or signals underflow to avoid errors.

Visual Quiz - 3 Questions

Look at the execution table, what is the visual state after Step 2?

A 20 -> 10 -> null

B 10 -> 20 -> null

C 20 -> null

D 10 -> null

💡 Hint

Check the 'Visual State' column for Step 2 in the execution_table.

At which step does the rear pointer move from node(10) to node(30)?

A Step 1

B Step 2

C Step 4

D Step 3

💡 Hint

Look at the 'Pointer Changes' column for rear pointer updates in the execution_table.

If we delete the rear at Step 3, what happens to the size variable according to variable_tracker?

A Increases by 1

B Decreases by 1

C Remains the same

D Becomes zero

💡 Hint

Check the 'size' row in variable_tracker between After 2 and After 3.

Concept Snapshot

Double Ended Queue (Deque):
- Supports insertion and deletion at both front and rear.
- Front and rear pointers track ends.
- InsertFront: new node becomes front.
- InsertRear: new node becomes rear.
- DeleteFront/Rear: remove node and update pointers.
- Size updates with each operation.

Full Transcript

A double ended queue, or deque, allows adding and removing items from both ends. We start empty with front and rear pointers null. When inserting at rear, if empty, both front and rear point to the new node. Inserting at front moves front pointer to new node, linking to old front. Deleting rear removes last node and moves rear pointer to previous node. Size tracks number of nodes. This trace shows step-by-step how nodes and pointers change with each operation, ensuring the deque maintains correct order and accessibility from both ends.

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

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

D. A list that allows random access to elements

Solution

1. Step 1: Understand the definition of Deque

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

2. Step 2: Compare with other data structures

   Queue restricts insertion to rear and deletion from front; stack restricts both to 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 way to declare a Deque of integers in C# using System.Collections.Generic?

easy

A. LinkedList<int> dq = new LinkedList<int>();

B. Queue<int> dq = new Queue<int>();

C. Deque<int> dq = new Deque<int>();

D. List<int> dq = new List<int>();

Solution

1. Step 1: Recall C# standard library support for Deque

   C# does not have a built-in Deque class, but LinkedList can be used as a deque.

2. Step 2: Analyze options

   Deque<int> dq = new Deque<int>(); is invalid as Deque class does not exist; Queue<int> dq = new Queue<int>(); is a queue, not deque; List<int> dq = new List<int>(); is a list, not deque.

3. Final Answer:

   LinkedList<int> dq = new LinkedList<int>(); -> Option A

4. Quick Check:

   LinkedList supports deque operations [OK]

Hint: Use LinkedList for deque in C# as no built-in Deque [OK]

Common Mistakes:

• Trying to use non-existent Deque class
• Using Queue which is single-ended
• Using List which lacks efficient front operations

3. What will be the output of the following C# code snippet?

var dq = new LinkedList<int>();
dq.AddLast(10);
dq.AddFirst(20);
dq.AddLast(30);
dq.RemoveFirst();
foreach(var item in dq) Console.Write(item + " ");

medium

A. 20 10 30

B. 30 10

C. 20 30

D. 10 30

Solution

1. Step 1: Trace the additions to the deque

   Added 10 at last: [10]; Added 20 at first: [20, 10]; Added 30 at last: [20, 10, 30]

2. Step 2: Remove first element

   RemoveFirst removes 20; deque becomes [10, 30]

3. Step 3: Print elements

   Output is "10 30 "

4. Final Answer:

   10 30 -> Option D

5. Quick Check:

   After RemoveFirst, deque = 10 30 [OK]

Hint: AddFirst adds front, RemoveFirst removes front [OK]

Common Mistakes:

• Confusing AddFirst and AddLast positions
• Forgetting RemoveFirst removes front element
• Assuming RemoveFirst removes last element

4. Identify the error in the following C# code using LinkedList as a deque:

var dq = new LinkedList<int>();
dq.AddFirst(5);
dq.RemoveLast();
dq.RemoveLast();
Console.WriteLine(dq.Count);

medium

A. No error, output is 0

B. InvalidOperationException at second RemoveLast call

C. Compile-time error due to RemoveLast misuse

D. Output is 1

Solution

1. Step 1: Trace the operations on deque

   Added 5 at front: deque = [5]; RemoveLast removes 5: deque = []

2. Step 2: Second RemoveLast on empty deque

   Calling RemoveLast on empty LinkedList throws InvalidOperationException

3. Final Answer:

   InvalidOperationException at second RemoveLast call -> Option B

4. Quick Check:

   Removing from empty deque throws exception [OK]

Hint: Removing from empty deque causes exception [OK]

Common Mistakes:

• Assuming RemoveLast on empty deque does nothing
• Expecting output 0 instead of exception
• Confusing compile-time and runtime errors

5. You want to implement a task scheduler using a deque where urgent tasks are added to the front and normal tasks to the rear. Which sequence of operations correctly adds urgent task 1, normal task 2, urgent task 3, then removes one task from the front?

var dq = new LinkedList<int>();
// Fill in operations below

hard

A. dq.AddFirst(1); dq.AddFirst(2); dq.AddLast(3); dq.RemoveLast();

B. dq.AddLast(1); dq.AddFirst(2); dq.AddLast(3); dq.RemoveLast();

C. dq.AddFirst(1); dq.AddLast(2); dq.AddFirst(3); dq.RemoveFirst();

D. dq.AddLast(1); dq.AddLast(2); dq.AddFirst(3); dq.RemoveFirst();

Solution

1. Step 1: Add urgent tasks to front and normal tasks to rear

   Urgent task 1: AddFirst(1); Normal task 2: AddLast(2); Urgent task 3: AddFirst(3)

2. Step 2: Remove one task from front

   RemoveFirst removes the front urgent task 3

3. Final Answer:

   dq.AddFirst(1); dq.AddLast(2); dq.AddFirst(3); dq.RemoveFirst(); -> Option C

4. Quick Check:

   Urgent front, normal rear, remove front [OK]

Hint: Urgent = AddFirst, Normal = AddLast, Remove from front [OK]

Common Mistakes:

• Mixing AddFirst and AddLast for task priority
• Removing from wrong end
• Incorrect order of operations