Double Ended Queue Deque in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Double Ended Queue (Deque)?

A Double Ended Queue, or Deque, is a data structure where elements can be added or removed from both the front and the back ends.

beginner

Name two main operations you can perform on a Deque.

You can insert (add) and delete (remove) elements from both the front and the rear ends of the Deque.

intermediate

In C#, which collection class can be used to implement a Deque efficiently?

The <code>LinkedList&lt;T&gt;</code> class can be used to implement a Deque because it allows fast insertion and removal from both ends.

beginner

What is the difference between a Queue and a Deque?

A Queue allows insertion at the rear and removal from the front only (FIFO). A Deque allows insertion and removal from both front and rear.

beginner

Why is a Deque useful in real life? Give an example.

A Deque is useful when you need flexible access to both ends, like managing a line where people can join or leave from front or back, such as a double-ended waiting list.

Which operation is NOT possible in a Deque?

A Insert at front

B Remove from rear

C Insert in the middle

D Remove from front

Deques allow insertion and removal only at the front or rear ends, not in the middle.

What is the time complexity of adding or removing an element at either end of a Deque implemented with a linked list?

A O(1)

B O(n)

C O(log n)

D O(n^2)

Adding or removing at either end of a linked list is done in constant time O(1).

Which C# class is best suited for implementing a Deque?

A List<T>

B LinkedList<T>

C Queue<T>

D Stack<T>

LinkedList supports fast insertion and removal at both ends, ideal for Deque.

If you add elements 1, 2, 3 to the front of an empty Deque in that order, what is the order from front to rear?

A 3 -> 2 -> 1

B 1 -> 3 -> 2

C 1 -> 2 -> 3

D 2 -> 3 -> 1

Adding to the front means the last added element is at the front, so order is 3 -> 2 -> 1.

Which of these is a valid use case for a Deque?

A Binary search

B Simple FIFO queue for print jobs

C Sorting an array

D Undo feature in text editors

Undo features often use Deques to add and remove actions from both ends.

Explain how a Double Ended Queue (Deque) works and how it differs from a regular Queue.

Think about how people can join or leave a line from both ends.

Describe how you would implement a Deque in C# and what built-in class you would use.

LinkedList<T> supports operations at both ends efficiently.

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