In this article I’m going to show you how to create a self-made queue data structure – which is a fundamental part of programming – with an array (or list) representation in the inside.

Queue structure

Queue data structure is one of the most fundamental structures (alongside with stack) in programming. This is mainly because the functionality is very simple, you can only add/remove items and that’s all. Of course linked list is basically doing the same, so what is the difference?

The twist is how we add/remove items! If we insert a new item (which is called Enqueue; enqueuing) it goes to the end of the queue – just like how you enter the line in a supermarket waiting for the cashier to pay. When you remove an item (which is called Dequeue; dequeuing) you are also limited in terms of which item you can remove. Automatically only the first – but better to call it as the next – item can be removed. Again imagine that from the cashier the currently paying person can leave, and then you can enter that person’s place. On this image below you can see this concept represented with an array.

It is important to highlight that queue uses FIFO concept, which is an acronym for First In First Out princple. In the video #1 at the bottom you can better understand how FIFO works – if you are not familiar with it yet.

More detailed explanation with examples can be seen in video #1 at the bottom, where I talk about the fundamentals of Stack and Queue structures.

Coding the queue

Creating the queue class

Similarly how we did with the linked list, binary search tree, graph and hash tables, we again will be using generic type T. I already placed a TraversalHandler for later, if you are not familiar with this, read my other article about this concept here.

Please note that instead of array you can use the built-in List<T> as well (or even you can use your self-made linked list class), but in that case you do not need to specify the size with the paramter in the constructor.

1
2
3
4
5
6
7
8
9
10
11
12
13
class MyQueue <T>
{
    private T[] items;
    public int Count { get; private set; }

    public delegate void TraversalHandler(T content);

    public MyQueue(int size)
    {
        items = new T[size];
        Count = -1;
    }
}

Adding the methods

As I stated previously above, the “trick” here is about how to add and remove item to the inside array. Using a simple array wouldn’t be enough because an array has more functionality than what we need (eg. directly indexing the items inside – which we must avoid in a queue). So we create a class to hide those “problematic” parts with these dedicated methods:

• Peek: checking the next item without removing it
• Enqueue: adding a new item
• Dequeue: removing the next item
• Shift: after removed an item, we have to shift all the remained items in the queue
• Traverse: using the delegate we process each item in the queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public T Peek()
{
    if (Count >= 0)
        return items[0];
    throw new Exception("Queue is empty.");
}
public void Enqueue(T newItem)
{
    if ( Count < items.Length )
        items[++Count] = newItem;
    else
        throw new Exception("Queue is full.");
}
public T Dequeue()
{
    if (Count >= 0)
    {
        T toReturn = items[0];
        Shift();
        items[Count--] = default;
        return toReturn;
    }
    throw new Exception("Queue is empty.");
}
private void Shift()
{
    for (int i = 1; i <= Count; i++)
        items[i - 1] = items[i];
}
public void Traverse(TraversalHandler method)
{
    for (int i = 0; i <= Count; i++)
        method(items[i]);
}

Now we have a fully working queue class with generic type, with exceptions thrown if needed. For more details (when to use exceptions, when to use ++count or count-- etc.) check the video #2 at the bottom about the coding.

Videos

Video #1 - Theory of the queue (and stack) data structure

Video #2 - Coding the queue

Other advised readings

Based on queue data structure I created an “advanced” usage, where I store delegates inside the queue. You can read that here.

Downloadables

You can download the full solution by clicking here.

Or use CLI with these commands and then look for the QUEUE and STACK folder:

1
2
cd Desktop && mkdir Downloaded_Project && cd Downloaded_Project
git clone https://github.com/siposm/data-structures.git