Queues in C#: Leveraging FIFO for Optimal Performance

A queue is a data structure that is designed to process temporary data. Just like a stack, it processes data but it a different order. Just like a stack, a queue is built from existing data structures; therefore, it is an abstract data type.

The best way to think of a queue is as a line for a movie theater. The first person in line is the first one to leave the line and enter the movies. With queues, the first item added to the queue is the first item to be removed. This is why Queues are sometimes referred to as “FIFO”: First In, First Out.

Like any line of people, a queue is depicted horizontally. The start of a queue is commonly called the front, and the end of the queue is the back.

A queue is just an array with three restrictions:

• Data is inserted only at the end of a queue. (Identical to a stack)
• Data can only be deleted from the front (Opposite to a stack)
• Only the element in the front of a queue can be read. (Opposite to a stack)

Enqueue

Just like stacks, Queues come with their own lingo. To insert into a Queue, it is called an “enqueue”.

Let’s enqueue the number 2.

Next, we enqueue a 6

Nest, we insert an 8:

Dequeue

If we want to remove data, we must start with the 2, since it’s at the front of the queue:

Next, we remove the 6:

Queue Implementation

Being that a queue is an abstract data type, we can implement it with either an array or a list. Using List<> tends to be far more efficient because it has nice methods we can use to access data like Add, RemoveAt, and Count.

public class Queue<T>
{
    private List<T> data;

    public Queue()
    {
        data = new List<T>();
    }

    public void Enqueue(T element)
    {
        data.Add(element);
    }

    public T Dequeue()
    {
        if (data.Count == 0)
        {
            throw new InvalidOperationException("Queue is empty.");
        }

        T firstElement = data[0];
        data.RemoveAt(0);
        return firstElement;
    }

    public T Read()
    {
        if (data.Count == 0)
        {
            throw new InvalidOperationException("Queue is empty.");
        }

        return data[0];
    }
}

Our newly created Queue wraps around the list with an interface that restricts our ability to manipulate the data. The enqueue method allows us to add data at the end of the list, while the dequeue removes the first item from the array. Finally, the read method allows us to peek at just the very first element of our list.