Double Ended Queue Deque in DSA C# - 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 C# code?

```csharp using System; using System.Collections.Generic; class Program { static void Main() { LinkedList deque = new LinkedList(); deque.AddLast(10); deque.AddFirst(20); deque.AddLast(30); deque.RemoveFirst(); deque.AddFirst(40); foreach(var item in deque) { Console.Write(item + " -> "); } Console.WriteLine("null"); } } ```

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        LinkedList<int> deque = new LinkedList<int>();
        deque.AddLast(10);
        deque.AddFirst(20);
        deque.AddLast(30);
        deque.RemoveFirst();
        deque.AddFirst(40);
        foreach(var item in deque) {
            Console.Write(item + " -> ");
        }
        Console.WriteLine("null");
    }
}

A 40 -> 20 -> 10 -> 30 -> null

B 20 -> 10 -> 30 -> null

C 40 -> 10 -> 30 -> null

D 10 -> 30 -> null

💡 Hint

Trace each operation step-by-step, noting how elements are added or removed from the front or back.

Initially, deque is empty. AddLast(10) makes it: 10. AddFirst(20) makes it: 20 -> 10. AddLast(30) makes it: 20 -> 10 -> 30. RemoveFirst() removes 20, so deque is: 10 -> 30. AddFirst(40) makes it: 40 -> 10 -> 30. The printed output matches option C.

🧠 Conceptual

intermediate

Deque Size After Mixed Operations

Consider a deque initially empty. We perform these operations in order:
1. AddFirst(5)
2. AddLast(10)
3. AddFirst(15)
4. RemoveLast()
5. RemoveFirst()

How many elements remain in the deque after these operations?

A 1

B 2

C 0

D 3

💡 Hint

Track the deque size after each operation carefully.

Start empty. AddFirst(5): size 1 (5). AddLast(10): size 2 (5,10). AddFirst(15): size 3 (15,5,10). RemoveLast(): removes 10, size 2 (15,5). RemoveFirst(): removes 15, size 1 (5). So 1 element remains.

🔧 Debug

advanced

Identify the Runtime Error in Deque Code

What error will this C# code produce when run?

```csharp using System; using System.Collections.Generic; class Program { static void Main() { LinkedList deque = new LinkedList(); deque.RemoveFirst(); deque.AddLast(1); Console.WriteLine(deque.First.Value); } } ```

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        LinkedList<int> deque = new LinkedList<int>();
        deque.RemoveFirst();
        deque.AddLast(1);
        Console.WriteLine(deque.First.Value);
    }
}

A NullReferenceException

B InvalidOperationException

C No error, prints 1

D ArgumentOutOfRangeException

💡 Hint

Removing from an empty LinkedList causes an exception.

Calling RemoveFirst() on an empty LinkedList throws InvalidOperationException because there is no element to remove. The code does not reach AddLast(1) or printing.

❓ Predict Output

advanced

Deque State After Complex Operations

What is the output of the following C# code?

```csharp using System; using System.Collections.Generic; class Program { static void Main() { LinkedList deque = new LinkedList(); deque.AddLast(1); deque.AddLast(2); deque.AddFirst(3); deque.RemoveLast(); deque.AddFirst(4); deque.RemoveFirst(); foreach(var item in deque) { Console.Write(item + " -> "); } Console.WriteLine("null"); } } ```

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        LinkedList<int> deque = new LinkedList<int>();
        deque.AddLast(1);
        deque.AddLast(2);
        deque.AddFirst(3);
        deque.RemoveLast();
        deque.AddFirst(4);
        deque.RemoveFirst();
        foreach(var item in deque) {
            Console.Write(item + " -> ");
        }
        Console.WriteLine("null");
    }
}

A 3 -> 1 -> null

B 4 -> 3 -> 1 -> null

C 3 -> 2 -> null

D 1 -> null

💡 Hint

Follow each operation carefully, especially the removes and adds at front and back.

Start empty. AddLast(1): 1. AddLast(2): 1 -> 2. AddFirst(3): 3 -> 1 -> 2. RemoveLast(): removes 2, now 3 -> 1. AddFirst(4): 4 -> 3 -> 1. RemoveFirst(): removes 4, now 3 -> 1. Output matches option A.

🧠 Conceptual

expert

Deque Behavior Under Concurrent Modifications

In a multi-threaded C# program using a LinkedList as a deque without locks, what is the most likely problem that can occur when two threads simultaneously call AddFirst() and RemoveLast()?

A Deadlock between the two threads

B Automatic thread-safe synchronization by LinkedList

C No problem, operations are atomic and safe

D Race condition causing corrupted internal state or exceptions

💡 Hint

Consider thread safety of LinkedList in .NET and what happens without synchronization.

LinkedList is not thread-safe. Concurrent modifications without locks can cause race conditions, corrupt internal pointers, or throw exceptions. It does not synchronize automatically, and deadlocks require locks which are not used here.

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