Data structures in C# – Part 3 – Queues

Posts in this Series:

• Linked Lists
• Stacks
• Queues (this post)
• Trees

In the last post, I’ve talked about stacks, a LIFO (Last In – First out) data structure. In this post, I will talk about queues, a FIFO (First in – First out) data structure. A queue is like any box office queue, where the first in line are served first.

The queue has these operations:

• Enqueue – adds an item to the end of the queue
• Dequeue – Removes an item from the start of the queue

Like the stack, you can’t add or remove items from the middle of the queue. The node structure is the same as the nodes used in the linked list and in the stack. The Enqueue method is like this:

public void Enqueue(T obj)
{
    NodeList<T> node = new NodeList<T>() { Data = obj };
    _count++;
    if (_last == null)
    {
        _last = _top = node;
        return;
    }
    _last.Next = node;
    _last = node;
}

Note that there is a subtle change from the stack code: we are using an extra pointer for the last node, so we can get fast inserts and deletes in the queue.

The Dequeue method is:

public T Dequeue()
{
    if (_top != null)
    {
        NodeList<T> result = _top;
        _top = _top.Next;
        _count--;
        return result.Data;
    }
    throw (new InvalidOperationException("The queue is empty"));
}

We remove the top node from the queue. With these two operations, the queue is ready. We can also do the same way as the stack and use a linked list to implement it:

public class QueueAsList<T>
{
    private readonly LinkedList<T>_linkedList = new LinkedList<T>();

    public void Enqueue(T obj)
    {
        _linkedList.Insert(obj);
    }

    public T Dequeue()
    {
        if (_linkedList.Count == 0)
            throw (new InvalidOperationException("The queue is empty"));
        var result = _linkedList[0];
        _linkedList.Remove(result);
        return result;
    }

    public int Count => _linkedList.Count;

    public void Clear()
    {
        _linkedList.Clear();
    }
}

Now we have our implementations of the queue and we can move to the next article, the Tree.

The source code for this series of articles is in https://github.com/bsonnino/DataStructures