Queue in C#

Introduction

In this tutorial, we will explore how to implement a queue data structure in C#. A queue is a fundamental data structure that follows the First-In-First-Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. Queues are widely used in various applications such as task scheduling, breadth-first search algorithms, and more.

Concept

A queue can be visualized as a line of people waiting for their turn at a service desk. The person who arrives first is served first, and the last person to arrive will be served last. In terms of data structure operations:

• Enqueue: Add an element to the end of the queue.
• Dequeue: Remove an element from the front of the queue.
• Peek: Retrieve the element at the front of the queue without removing it.
• IsEmpty: Check if the queue is empty.

Examples

Let's start by implementing a simple queue using a list in C#.

Basic Queue Implementation

using System;
using System.Collections.Generic;

public class Queue<T>
{
    private List<T> items = new List<T>();

    public void Enqueue(T item)
    {
        items.Add(item);
    }

    public T Dequeue()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("Queue is empty");
        }
        T item = items[0];
        items.RemoveAt(0);
        return item;
    }

    public T Peek()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("Queue is empty");
        }
        return items[0];
    }

    public bool IsEmpty()
    {
        return items.Count == 0;
    }
}

### Using the Queue

Now, let's see how we can use this queue class.

```csharp
using System;

public class Program
{
    public static void Main()
    {
        Queue<string> queue = new Queue<string>();
        
        queue.Enqueue("Alice");
        queue.Enqueue("Bob");
        queue.Enqueue("Charlie");

        Console.WriteLine(queue.Peek()); // Output: Alice

        while (!queue.IsEmpty())
        {
            Console.WriteLine(queue.Dequeue());
        }
        // Output:
        // Alice
        // Bob
        // Charlie
    }
}

### Explanation

1. **Enqueue**: Adds "Alice", "Bob", and "Charlie" to the queue.
2. **Peek**: Retrieves the first element, which is "Alice".
3. **Dequeue**: Removes elements from the front of the queue one by one until it's empty.

### Optimized Queue Implementation

Using a list for a queue can be inefficient because removing an item from the beginning of a list requires shifting all other elements. A more efficient implementation would use a `LinkedList`.

```csharp
using System;
using System.Collections.Generic;

public class Queue<T>
{
    private LinkedList<T> items = new LinkedList<T>();

    public void Enqueue(T item)
    {
        items.AddLast(item);
    }

    public T Dequeue()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("Queue is empty");
        }
        T item = items.First.Value;
        items.RemoveFirst();
        return item;
    }

    public T Peek()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("Queue is empty");
        }
        return items.First.Value;
    }

    public bool IsEmpty()
    {
        return items.Count == 0;
    }
}

Using the Optimized Queue

The usage remains the same as before, but the performance is improved.

using System;

public class Program
{
    public static void Main()
    {
        Queue<string> queue = new Queue<string>();
        
        queue.Enqueue("Alice");
        queue.Enqueue("Bob");
        queue.Enqueue("Charlie");

        Console.WriteLine(queue.Peek()); // Output: Alice

        while (!queue.IsEmpty())
        {
            Console.WriteLine(queue.Dequeue());
        }
        // Output:
        // Alice
        // Bob
        // Charlie
    }
}

Explanation

1. Enqueue: Adds "Alice", "Bob", and "Charlie" to the end of the linked list.
2. Peek: Retrieves the first element, which is "Alice".
3. Dequeue: Removes elements from the front of the linked list one by one until it's empty.

What's Next?

In the next tutorial, we will explore another fundamental data structure: the stack. Stay tuned!