Double Ended Queue Deque in DSA C# - Build from Scratch

Double Ended Queue (Deque) Implementation

📖 Scenario: Imagine you are managing a line of customers at a store where people can join or leave from both the front and the back of the line.

🎯 Goal: You will build a simple double ended queue (deque) using a list to add and remove customers from both ends.

📋 What You'll Learn

Create a list called deque with initial customers

Create a variable called newCustomer to add to the deque

Add newCustomer to the front of the deque

Remove a customer from the back of the deque

Print the final state of the deque

💡 Why This Matters

🌍 Real World

Deques are used in real life for managing lines where people can join or leave from both ends, like waiting lines or task scheduling.

💼 Career

Understanding deques helps in software development roles that require efficient data handling, such as game development, operating systems, and real-time applications.

1

Create the initial deque

Create a list called deque with these exact string values in order: "Alice", "Bob", "Charlie"

DSA C#

# Your code here

Hint

Use List<string> and initialize it with the three names inside curly braces.

2

Add a new customer variable

Create a string variable called newCustomer and set it to "Diana"

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List deque = new List { "Alice", "Bob", "Charlie" };
        // Your code here
    }
}

Hint

Use string newCustomer = "Diana"; to create the variable.

3

Add and remove customers from the deque

Use deque.Insert(0, newCustomer) to add newCustomer to the front of the deque, then use deque.RemoveAt(deque.Count - 1) to remove the customer at the back

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List deque = new List { "Alice", "Bob", "Charlie" };
        string newCustomer = "Diana";
        // Add newCustomer to front and remove last customer
        // Your code here
    }
}

Hint

Use Insert(0, newCustomer) to add at front and RemoveAt(deque.Count - 1) to remove from back.

4

Print the final deque

Use a foreach loop with variable customer to print each customer in deque on a separate line

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List deque = new List { "Alice", "Bob", "Charlie" };
        string newCustomer = "Diana";
        deque.Insert(0, newCustomer);
        deque.RemoveAt(deque.Count - 1);
        // Print each customer in deque
        // Your code here
    }
}

Hint

Use foreach (string customer in deque) and Console.WriteLine(customer); inside the loop.

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