Hello there! Today, we will unveil Queues in coding, likening them to a line in a coffee shop or a queue of print requests. Queues in computer science are First-In, First-Out (FIFO) structures. Consider this example: you're at a theme park — the first person in line for the roller coaster gets on first. Today's lesson revolves around this straightforward yet powerful concept. So, let's dive in!

Let's explore the implementation of Queues in C#. An array is ideal for implementing a Queue. Let's define the Queue:

public class Queue {
    private int front, rear, size, capacity;
    private int[] array;

    public Queue(int capacity) {
        this.capacity = capacity; // Set the max size
        front = size = 0; // Initialize front and size
        rear = capacity - 1; // Initialize rear
        array = new int[this.capacity];
    }

    // Will return true if the Queue is full
    public bool IsFull() {
        return (size == capacity);
    }
}

In the Queue class above, the IsFull() method checks if our queue is already at maximum capacity.

Enqueue, a fancy term, denotes adding an item to the queue — the item lines up at the rear. Here's how it plays out in our Queue class:

public void Enqueue(int item) {
    if (IsFull()) // Check if the queue is full
        return;
    rear = (rear + 1) % capacity; // Move rear
    array[rear] = item; // Add item at rear position
    size = size + 1; // increment size
}

rear = (rear + 1) % capacity uses the modulo operator to calculate the new position for the rear pointer, ensuring it wraps around to the start of the queue when it surpasses the maximum index, thereby maintaining a circular behavior.

Just as Enqueue adds an element to our queue, Dequeue removes it. It extracts the element at the queue's front, reducing its size. However, we encounter an underflow condition if there are no elements to remove.

public int Dequeue() {
    if (IsEmpty()) // Check if the queue is empty
        return int.MinValue;

    int item = array[front]; // Item at front
    front = (front + 1) % capacity; // Move front
    size = size - 1; // decrement size
    return item; // return removed item
}

public bool IsEmpty() {
    return (size == 0);
}

The Dequeue() method checks for emptiness before dispatching the item.

The time complexity of enqueue and dequeue operations remains constant: O(1). However, the space complexity varies with the size of the queue, making it O(n).

While it is essential to understand the queue's inner structure, we won't implement it ourselves. Instead, we will use C#'s built-in Queue<T> class. Think of any system that needs to handle requests in a fair, first-come-first-served order. These are all excellent candidates for using a queue. Here's how you can declare, initialize, and utilize a Queue<T> using C#:

using System;
using System.Collections.Generic;

public class MainClass {
    public static void Main(string[] args) {
        // Create and initialize a Queue using a List
        Queue<int> queue = new Queue<int>();

        // Add elements {0, 1, 2, 3, 4} to queue 
        for (int i = 0; i < 5; i++)
            queue.Enqueue(i);

        // Display contents of the queue.
        Console.WriteLine("Elements of queue: " + String.Join(", ", queue));

        // To remove the head of queue. 
        int removedElement = queue.Dequeue(); 
        Console.WriteLine("Removed element: " + removedElement);

        Console.WriteLine("Queue after removal: " + String.Join(", ", queue));

        // To view the head of queue
        int head = queue.Peek(); 
        Console.WriteLine("Head of queue: " + head);

        // Rest all methods of collection interface
        int size = queue.Count; 
        Console.WriteLine("Size of queue: " + size);
    }
}

/* Output:
Elements of queue: 0, 1, 2, 3, 4
Removed element: 0
Queue after removal: 1, 2, 3, 4
Head of queue: 1
Size of queue: 4
*/

In the above example, we create an instance of Queue<int> using C#. Key Queue operations include:

• Enqueue(): Inserts the specified element into the Queue.
• Dequeue(): Removes and returns the head of the Queue.
• Peek(): Retrieves, but does not remove, the head of the Queue, returning null if the queue is empty.
• Count: Returns the number of elements in the Queue.

C#'s Queue<T> class is versatile and can accommodate diverse data types.

We've learned about the Queue, its operations, and its implementation in C#. Furthermore, these techniques are fundamental for smooth functioning in daily life. They are invaluable and versatile in various applications, from data buffering in hardware to process scheduling in operating systems.

With your newfound knowledge of the Queue data structure, it's time to level up! Next are some practice problems to enhance your understanding of these concepts. Let's dive in!