Queues: Concepts and Implementation in C#

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.