Queues in C#

What are Queues?

A queue is a data structure that allows the FIFO (First In First Out) policy, which means the first item inserted is the first one that can be removed. In other words, the order in which the item gets into the queue dictates the order in which the item comes out. The operation of adding an item into a queue is called Enqueue and removing an item from the other end is referred to Dequeue.

Building a Queue

We want to implement a queue using an array to hold the items. We will implement the Enqueue() method to add items to the queue. Moreover, we need the Dequeue() method to take out an item from the queue. Our custom queue will hold any data type T.

We will declare an array of T to hold the items as well as two integers to point at the head and the tail of the queue. Furthermore, we need the _numElements to track the number of items in the queue. The underlying array is instantiated inside the constructor with the initial size. 

public class CustomQueue<T>
{
    private readonly T[] _data;
    private int _head;
    private int _tail;
    private int _numElements;

    public CustomQueue(int size)
    {
        if (size != 0)
        {
            _data = new T[size];
        }
        else
        {
            throw new ArgumentOutOfRangeException("size", "Must be greater than zero");
        }
    }

Now, we want a method to insert new data to the end of the queue. Inside Enqueue() method, first, we should check to see whether the queue is full. Then, add the new item to the queue and increment the _tail along with the _numElements. The runtime complexity of adding items to the queue is O(1). 

    public void Enqueue(T item)
    {
        if (_numElements == _data.Length)
        {
            throw new InvalidOperationException("The queue is full");
        }

        _data[_tail++] = item;
        _tail %= _data.Length;
        _numElements++;
    }

Next, we will implement the Dequeue() method to remove the item from the start of the queue. This method returns the removed item. When we want to remove the item from the queue, we should ensure that the queue is not empty. After removing the item, we want to increment the _head variable and decrement the _numElements. The runtime complexity of removing items from the queue is O(1). 

    public T Dequeue()
    {
        if (_numElements == 0)
        {
            throw new InvalidOperationException("The queue is empty");
        }

        T item = _data[_head];
        _data[_head++] = default;
        _head %= _data.Length;
        _numElements--;
        return item;
    }

When adding an item, it is inserted at the index, which follows the tail of queue. After that the _tail points at the newly added item. When removing an item, we take the item, which is pointed by the head of the queue. After that the _head starts to point at the next item. Thus the queue moves to the end of the array. When it reaches the end of the array, we conceptually want to connect the end of the array to its beginning. So, by adding a new item, it is inserted at the beginning of the array. This structure is called circular array. In C#, arrays begin with index 0. Therefore, we can implement circular array using remainder of the division of _tail in Enqueue() or _head in Dequeue() by the length of the array. The last thing we do is implementing the Peek() method to view the item at which _head points. 

    public T Peek()
    {
        if (_numElements == 0)
        {
            throw new InvalidOperationException("The queue is empty");
        }

        return _data[_head];
    }
}

You can download the source code on Github.