Dictionary Hashset Stack Queue In C# Complete Guide

1. What is a Dictionary in C#?

Answer: A Dictionary<TKey, TValue> is a data structure that stores a collection of key/value pairs. It provides fast access to keys using a hash code generated by the hash function on the key type. Dictionaries are ideal for scenarios where you need to quickly retrieve, add, or remove elements based on a unique key.

Example Usage:

var dictionary = new Dictionary<string, int>();
dictionary.Add("Apple", 1);
dictionary.Add("Banana", 2);

// Access value using key
int appleCount = dictionary["Apple"];

// Check if key exists
bool hasOrange = dictionary.ContainsKey("Orange");

2. How do you iterate through a Dictionary?

Answer: You can iterate through a Dictionary using a foreach loop to access each key/value pair. The loop uses the KeyValuePair<TKey, TValue> class to hold each pair.

Example:

foreach (var kvp in dictionary)
{
    Console.WriteLine($"Key: {kvp.Key}, Value: {kvp.Value}");
}

Alternatively, you can iterate over just keys or values:

// Iterating over keys
foreach (var key in dictionary.Keys)
{
    Console.WriteLine($"Key: {key}");
}

// Iterating over values
foreach (var value in dictionary.Values)
{
    Console.WriteLine($"Value: {value}");
}

3. What is a HashSet in C#?

Answer: A HashSet<T> represents a set of values, which means it doesn’t allow duplicate elements. Similar to a dictionary, HashSet uses a hash table for storing its elements, providing efficient insertion, deletion, and lookup operations.

Usage:

var fruits = new HashSet<string>();
fruits.Add("Apple");
fruits.Add("Banana");
fruits.Add("Apple"); // Duplicate, will not be added

if (!fruits.Contains("Mango"))
{
    fruits.Add("Mango");
}

4. How does HashSet compare with List in C#?

Answer:

• HashSet<T>: Uses a hash table internally for storage. Provides O(1) average time complexity for insertions, deletions, and lookups but O(n) time complexity for iteration.

• List<T>: Stores elements in contiguous memory locations. Provides O(1) average time complexity for indexing and iteration but O(n) time complexity for insertions and deletions (unless at the end of the list).

When to Use:

• Use HashSet<T> when you need to ensure unique elements and perform frequent lookups, additions, or removals without caring about order.
• Use List<T> when you require ordered elements and infrequent lookups.

5. What is the difference between Stack and Queue in C#?

Answer:

• Stack<T>: Follows the Last In, First Out (LIFO) principle. Elements are added and removed from the same end, known as the top or head of the stack. Useful in scenarios like undo mechanisms, backtracking algorithms, parsing expressions (e.g., parentheses), etc.

• Queue<T>: Follows the First In, First Out (FIFO) principle. Elements are added to one end (the tail or rear) and removed from the other end (the head or front). Suitable for scheduling processes, breadth-first search algorithms, buffering data for processing, etc.

Usage Examples:

• Stack<T>:

  var books = new Stack<string>();
  books.Push("Book One");
  books.Push("Book Two");
  
  string lastInFirstOut = books.Pop(); // "Book Two"
  

• Queue<T>:

  var printQueue = new Queue<string>();
  printQueue.Enqueue("Document 1");
  printQueue.Enqueue("Document 2");
  
  string firstInFirstOut = printQueue.Dequeue(); // "Document 1"
  

6. How can you check if an element exists in a Queue or Stack?

Answer: While Queue<T> and Stack<T> don't have a direct Contains method, you can convert them to lists or use other collections temporarily to perform this check.

However, the recommended approach is to use a data structure like HashSet<T> if frequent membership testing is required.

Example:

if (!printQueue.Contains("Document 1"))
{
    printQueue.Enqueue("Document 1");
}

Conversion Method:

var queueList = printQueue.ToList();
bool existsInQueue = queueList.Contains("Document 1");

// Or using HashSet if performance is critical
var queueHashSet = new HashSet<string>(printQueue);
bool existsInHashSet = queueHashSet.Contains("Document 1");

For Stack: Converting a Stack<T> to a List<T> or HashSet<T> can achieve similar functionality.

7. Can a Dictionary have duplicate keys?

Answer: No, a Dictionary<TKey, TValue> cannot have duplicate keys. Each key must be unique within the dictionary. Attempting to add a duplicate key will throw a KeyNotFoundException if you try to modify the value using the indexer, or an ArgumentException from the Add method.

Handling Duplicate Keys: If you need to handle multiple values for the same key, consider using Dictionary<TKey, List<TValue>>.

Example:

var phoneBook = new Dictionary<string, List<string>>();
phoneBook.Add("John", new List<string> { "123-4567", "987-6543" });
phoneBook["Jane"] = new List<string> { "555-5555" };

phoneBook["John"].Add("555-1234"); // Adding another phone number for John

8. How do the performance characteristics of these collections differ?

Answer: Dictionary<TKey, TValue>:

• Insertion/Deletion: Average O(1).
• Lookup/ContainsKey: Average O(1).
• Iteration: O(n).

HashSet:

• Insertion/Deletion: Average O(1).
• Lookup/Contains: Average O(1).
• Iteration: O(n).

Stack:

• Push/Pop: Average O(1).
• Peek: O(1).
• Iteration: O(n).

Queue:

• Enqueue/Dequeue: Average O(1).
• Peek: O(1).
• Iteration: O(n).

Factors Affecting Performance:

• Load Factor: For dictionaries and hash sets, the load factor determines when the hash table resizes. Setting a lower load factor reduces collision chances but increases memory usage.
• Hash Function Quality: A well-designed hash function minimizes collisions, ensuring O(1) operations.

9. What are some common use cases for each collection?

Answer:

• Dictionary<TKey, TValue>:

  • Associative arrays (mapping unique identifiers to values).
  • Fast lookups, additions, and deletions based on keys.
  • Implementing caches or any scenario requiring quick access to data via keys.

• HashSet<T>:

  • Ensuring unique elements in a collection.
  • Membership testing (checking if an element exists).
  • Implementing union, intersection, and other set operations efficiently.

• Stack<T>:

  • Undo mechanisms in applications.
  • Function call stacks (used implicitly by the language runtime).
  • Syntax parsing (matching opening and closing braces or tags).
  • Depth-first search (DFS) algorithms in graph theory.

• Queue<T>:

  • Task scheduling and managing print jobs.
  • Breadth-first search (BFS) algorithms in graph theory.
  • Message processing systems.
  • First-come, first-served workflows.

10. How can you implement your own custom stack or queue using an array or linked list in C#?

Answer: Implementing custom stacks and queues can help you understand their underlying mechanics and optimize specific aspects like memory management or resizing strategies.

Custom Stack Using Array:

public class CustomStack<T>
{
    private T[] _array;
    private int _currentIndex;

    public CustomStack(int capacity = 4)
    {
        _array = new T[capacity];
        _currentIndex = -1;
    }

    public void Push(T value)
    {
        if (_currentIndex + 1 >= _array.Length)
            ResizeArray(_array.Length * 2);

        _array[++_currentIndex] = value;
    }

    public T Pop()
    {
        if (_currentIndex < 0)
            throw new InvalidOperationException("The stack is empty.");

        T result = _array[_currentIndex];

        // Optionally resize array for better memory efficiency
        if (_currentIndex < _array.Length / 4)
            ResizeArray(_array.Length / 2);

        _array[_currentIndex--] = default; // Remove reference
        return result;
    }

    public T Peek()
    {
        if (_currentIndex < 0)
            throw new InvalidOperationException("The stack is empty.");

        return _array[_currentIndex];
    }

    private void ResizeArray(int newSize)
    {
        Array.Resize(ref _array, newSize);
    }
}

Custom Queue Using Linked List:

public class Node<T>
{
    public T Data { get; set; }
    public Node<T> Next { get; set; }

    public Node(T data)
    {
        Data = data;
        Next = null;
    }
}

public class CustomQueue<T>
{
    private Node<T> _head;
    private Node<T> _tail;

    public CustomQueue()
    {
        _head = null;
        _tail = null;
    }

    public void Enqueue(T value)
    {
        var newNode = new Node<T>(value);
        if (_tail != null)
            _tail.Next = newNode;

        _tail = newNode;

        if (_head == null)
            _head = newNode;
    }

    public T Dequeue()
    {
        if (_head == null)
            throw new InvalidOperationException("The queue is empty.");

        T result = _head.Data;
        _head = _head.Next;

        // If the queue becomes empty after dequeuing, clean up tail pointer
        if (_head == null)
            _tail = null;

        return result;
    }

    public T Peek()
    {
        if (_head == null)
            throw new InvalidOperationException("The queue is empty.");

        return _head.Data;
    }
}

Key Points:

• Custom Stack: Manages a fixed-size array, doubling its size when necessary and halving it for efficient memory use.
• Custom Queue: Utilizes a linked list, where each node points to the next, allowing dynamic sizing.

Advantages:

• Custom implementations offer flexibility to tailor behavior to specific needs.
• Helps in understanding data structures at a deeper level.