Delegates inside queue data structure

delegate data structure on YouTube

In this article I’m going to show you how to create a self-made queue data structure and how you can use it to store method references inside, which then can be invoked one-by-one, creating a call sequence.

Introduction

The idea came to my mind based on the message queues like RabbitMQ. Message queues can be described as this: “Message queues provide an asynchronous communications protocol, meaning that the sender and receiver of the message do not need to interact with the message queue at the same time. Messages placed onto the queue are stored until the recipient retrieves them. Message queues have implicit or explicit limits on the size of data that may be transmitted in a single message and the number of messages that may remain outstanding on the queue.” – according to Wikipedia.

My idea is a slightly different thing, but the queue concept remained the same – which is the key point of this whole article. So basically what I want to create is some form of data strucutre (which will be a queue for this time, but could be linked list, graph or stack as well) which is capable of storing method references. Later these methods can be invoked on demand, forming some kind of method calling sequence for example.

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.

queue representation

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.

Creating method queue

Next step will be to use the queue to store methods inside. Now we can see why using generic type is great, because we not only can store string, int, bool types but also can store delegate types as well! For this, I created a sample delegate and the queue object as well.

1
2

public delegate void SomeDelegate(ref int _number);
MyQueue<SomeDelegate> methodQueue = new MyQueue<SomeDelegate>(5);

After this we can create as many methods as we want or need to, with one restriction: it should use the same method signature (return type, number and type of parameters must match). In this small example I created a variable which will be used by the methods as a common source (like a database). The methods are simple, each of them is responsible for a small task.

1
2
3
4
5
6
7
8
9
10
11
12

static void CalculateNumber(ref int _number) {
    _number = 230;
}
static void MultiplyNumber(ref int _number) {
    _number *= 3;
}
static void AddingRandomBitsToNumber(ref int _number) {
    _number += new Random().Next(1, 15);
}
static void WriteOutNumber(ref int _number) {
    File.WriteAllLines("_OUTPUT.txt", new[] { _number.ToString() });
}

After this we can enqueue these methods, and invoke them.

1
2
3
4
5
6
7
8

methodQueue.Enqueue(CalculateNumber);
methodQueue.Enqueue(MultiplyNumber);
methodQueue.Enqueue(AddingRandomBitsToNumber);
methodQueue.Enqueue(WriteOutNumber);
int _number = 0;
int limit = methodQueue.Count; // .Count changes as we take items out...
for (int i = 0; i <= limit; i++)
    methodQueue.Dequeue()?.Invoke(ref _number);

Result

Now we have a queue data structure which can store methods (or whatever type we want), and the order we invoke the methods can represent eg. a “chain reaction”. With this, you can create applications where you can run methods in a forced order. Imagine a module in your application where users can log in. This log in process can be divided up into smaller parts, like:

  • Part 1: requestion username,
  • Part 2: requesting password,
  • Part 3: checking if username is valid,
  • Part 4: checking if password is valid and matching what is stored,
  • Part 5: redirect the user.

These methods can be stored in a queue, iterating through it, dequeuing item by item and invoking them can result in a correct calling sequence. Note: dequeuing items result that nothing will be left in the queue, which can be a problem (or not)… but you get the point about the sequence.

Videos

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

Video #2 - Coding the queue

Downloadables

You can download the full solution by clicking here.

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

1
2

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